How to detect two moving shapes overlapped ? (Algorithm)

Question

Given a list of circles with its coordinates (x and y) that are moving every second in different direction (South-East, South-West, North-East and North-West), and the circle will change direction if it hits the wall sort of like bouncing, so how do we detect if any of them collide or overlap with each other ? I am not sure if we can use some data structures like a Binary Search Tree because since all the coordinates vary every seconds, so the tree will have to re-build accordingly. Or can we use Vertical Sweep Line Algorithm each time ? Any ideas on how to do this in a efficient way ?

Answer 1

Your shapes are only circles, so:

• A circle will touch a border of your rectangle if its distance to the border is inferior to its radius.
• Two circles will touch each other if the distance between their center is inferior to the sum of their radius.

Suppose your rectangle's boundaries are X1 and X2 on the horizontal axis and Y1 and Y2 on the vertical axis (with X1 < X2 and Y1 < Y2). In the first case, if the center of your circle is (x, y) and its radius is r you have to check if :

• x-r < X1 ?
• x+r > X2 ?
• y-r < Y1 ?
• y+r > Y2 ?

If any of these is true, your circle touches the boundary of the rectangle.

In the second case, suppose your circles are defined by (x1, y1, r1) and (x2, y2, r2) respectively. You have to check if (x1 - x2)^2 + (y1 - y2)^2 < (r1 + r2)^2. If this is true, your circles touch each other.

Answer 2

Given the provided assumptions that:

• Your moving shapes are only circles.
• Walls are only vertical or horizontal walls that form a box.
• Circles do not collide with each other (although this isn't difficult to implement)

You can implement the following simple algorithm:

• For each circle, keep track of 4 coordinates as offset from its current origin (center):
  • Top, bottom, left, right (or north, south, west, east)
  • Note that these are the only points of contact the circles with the walls are with these 4 exact places.
• Each time right after a circle moves, check each of its 4 coordinates from the origin to see if it overlaps with a wall boundary (A simple / lazy way can be just to make walls as rectangles that are as thick as your FPS / ball speed requires)
• How to implement overlap detection:
  • Suppose you just implemented the walls as RectangleWall.
  • In RectangleWall, add a public member function called public boolean isPointInside(Point pt) (or signature can be (int x, int y)) and add the logic for checking whether the point being passed in falls within the boundaries of the rectangle: this should be simple for you ;)
• Implement the corresponding logic for collision when you detect an overlap:
  • If the ball's left or right spot overlaps with something, reverse its x-velocity.
  • If the ball's top or bottom spot overlaps with something, reverse its y-velocity.