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 ?
Quadtree is a brother of Binary tree, for 2D.
Here is a good explanation with live example in Javascript:
http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/
3
If you have a modest number of them, and since they are circles, you can compare the distance between the mid-points of each circle to all the others. If the distance is less than the sum of the two radii, they overlap.
This approach isnt terribly efficient, but should suffice for numbers in the dozens without any noticable performance impact. And there’s a couple ways to speed this up (comparing squared values rather than doing an expensive sqrt in the distance calc, and checking if the difference in x or y coords of the midpoints are greater than the sum of radii, for example).