Take the 2-minute tour ×

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 ?

share|improve this question

2 Answers 2

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/

share|improve this answer
This is exactly what i am looking for, but i am wondering is Quadtree the best approach ? –  peter Oct 27 '12 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 ;) –  c69 Oct 27 '12 at 5:13
Of interest: going up one dimension and you then have Binary Spacial Partitioning Trees (BSP Tree). –  Steve Evers Oct 27 '12 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).

share|improve this answer

Your Answer


