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 ?
Add a comment
|
2 Answers
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/
-
This is exactly what i am looking for, but i am wondering is Quadtree the best approach ?– peterCommented Oct 27, 2012 at 5:04
-
best? depends on your requirements.good enough? - probably yes. Check: stackoverflow.com/a/88924/946789 You can try Sweep and Prune, from this link, but that's far beyond my expertise in 2D geometry - so from that point you'll be on your own ;)– c69Commented Oct 27, 2012 at 5:13 -
Of interest: going up one dimension and you then have Binary Spacial Partitioning Trees (BSP Tree). Commented Oct 27, 2012 at 7:55
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).
answered Oct 27, 2012 at 6:28
