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/

  • 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). 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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.