Hi,

I have a set of circles stored in a quadtree and I want to find and store all intersections that occur.

I currently do a simple cull against the quadtree for each circle, but I'm thinking there might be a faster way to this since I want to do it for all circles (some kind of group calculation I guess). The method is called quite often so it's important that it runs fast.

I've looked around for a suitable algorithm without success, so I figured I'd see if anyone here has any ideas on how to improve the runtime.

Use a sort-and-sweep algorithm on the axis-aligned bounding boxes of the circles. You say this is "called quite often". If you mean the circles are moving each frame and you need to know intersections after the motion, then the sort-and-sweep algorithm is effectively constant time per frame (relies on space and time coherency). I have a sample application for the AABB sort-and-sweep.

Thanks for the reply. I've been busy with a few other things, but I'll take a look at it shortly and come back with feedback when I've tried it out!