1

There are N red balls and a white ball, all with the same radius. The white ball moves from position p1 to p2.

My objective is to predict all red balls the white ball will hit in its path and turn them yellow.

I tried iterating through all balls and taking the distance to the line formed by p1 and p2, but the balls that are behind the white turned yellow too, but they shouldn't. How should I approach this task? Is there a fast way to do it?

You can suppose that the white follows its path ignoring all collisions, the only objective is to predict what balls are in its way.

enter image description here

Daniel
  • 7,357
  • 7
  • 32
  • 84
  • 2
    The drawing is misleading, because the white ball will change direction with every collision. – trincot May 17 '20 at 17:57
  • No, it doesn't. You can suppose it's just a prediction and it keeps moving forward. – Daniel May 17 '20 at 18:03
  • Then what is this about? Not balls? What if the red balls hit each other and make them move away from the path of the white ball? Can you explain what the background story is? – trincot May 17 '20 at 18:12
  • Suppose the white ball moves through the reds and all reds are static. I just wanna predict which of them would be hit. – Daniel May 17 '20 at 18:32
  • 1
    Show the code please. – user58697 May 17 '20 at 18:41

2 Answers2

3

You should color the balls whose centres lie within this rectangle:

enter image description here

The short sides of that rectangle are perpendicular to the line through P1-P2, going through the centres of P1 and P2 respectively. Their length is 4 x radius, with P1/P2 at the middle of the line segment.

The long sides are parallel with the line through P1-P2.

Now you only need to check whether a red ball's centre point is on the right side of each of these four lines.

Check "How to tell whether a point is to the right or left side of a line?" on how you can do that.

trincot
  • 317,000
  • 35
  • 244
  • 286
0

I assume you are using Ax+By+C = 0 to describe the line.

In this case you can get perpendicular lines using Bx -Ay +C = 0. A and B have to match but C can vary. Figure out C1 and C2 corresponding to the start and end position. Now we are looking for points that lie between these two. More specifically the signs of the two equation, results have to be oposite. That is (Bx -Ay +C1) * (Bx -Ay +C2) <=0. This will filter the red balls that would collide outside the segment you are interested in. You may have to move the start/end points along the line if you want to catch collisions at the start and end point.

To speed things up you can do few tricks. Remember that divisions and square root are expensive operations. For distance since you need to divide by sqrt(A*A + B*B) store it's inverse and multiply by it instead of recomputing for each point.

If you need to compute many such collisions over a static set of balls you can consider some space partitioning. Regular grid or more fancy BSP or quad trees will allow you to remove large number of tests easily, at the expense of a more complex implementation and some static setup time.

Sorin
  • 11,863
  • 22
  • 26