4
$\begingroup$

I have a collection of N circles in the plane with various position and radius. Circles move around according to one force and become bound to each other once they overlap. I need a fast way to determine if a circle is overlapped/overlaps another, to determine the circle's equations of motion during a time step. Once circles have overlapped, they are bound, so it's easy to remember that relationship. The problem is to evaluate when circles overlap for the first time. Think of cheerios floating on milk.

Obviously I have thought of using a KDTree or a Delaunay Triangulation, but these only take into account the circle centers, not their radius, so the closest circle in a DT Trianle isn't necessarily overlapping, while another might be.

I've read somewhere that a MWVD might work, but I don't understand how that would work. D Eppstein has a couple of papers out on Mobius Transformations, and that too is over my head, but it looks like it's related. Can anyone point me in the right direction ?

Thanks.

$\endgroup$
  • 2
    $\begingroup$ Can you tell us more about what you want to do with these circles? How dense the intersection graph is, and whether or not it is dynamic? If the graph is dense and dynamic, you may as well just test your $N$ circles when you need the list of circles intersecting a given circle, as you can do this in constant time per circle pair anyway. $\endgroup$ – Andrew D. King Mar 19 '13 at 17:32
  • $\begingroup$ Sure. The circles move around according to one gravity-like 'force' as long as they don't overlap. Once they overlap, a second rigid spring-like relationship takes over. Once they have overlapped, I can keep track of these relationships, so I don't need to re-discover those overlaps, but I want to discover the new ones. Because of the spring-like behavior, the graph is not quite dynamic, not sparse, but also never a complete graph. $\endgroup$ – jdbertron Mar 20 '13 at 3:19
  • $\begingroup$ Why never a complete graph, if they are attracted by a gravity-like force? And do you mean that once they touch, they remain touching, as might balloons with static electricity? It seems to me that either you should go for a $k$-d tree or resign yourself to a quadratic method, and have the "force" reflect whether or not the distance between the centres is greater than the sum of the two radii. $\endgroup$ – Andrew D. King Mar 20 '13 at 17:04
  • $\begingroup$ Because in a complete graph the nodes are all connected, but in this case, the repulsion limits the possible overlaps, and therefore the number of connections. I think it is in fact a planar graph but I wouldn't venture to prove it. $\endgroup$ – jdbertron Mar 21 '13 at 0:30
  • 1
    $\begingroup$ Please modify the original problem statement to take the motion of the circles into account. Also: What does "visited" mean? $\endgroup$ – Jeffε Mar 22 '13 at 3:46
3
$\begingroup$

A modified Bentley-Ottmann sweep algorithm (here, for example) will find all line segment intersections in $O((n+k)\log n + k)$ time, where $k$ is the number of intersections. It's fairly straightforward to extend the algorithm to handle circles. A good walkthrough is here under "finding intersections".

$k$ can be $\Omega(n^2)$ in theory (in which case pairwise checking is faster), but it seems difficult to avoid the $k$ term, and in any case you seem to say $k$ will be small in your question.

Granted, this recomputes the intersections from scratch each time you run the algorithm, which may be inefficient for your purposes. You may be able to get around this a bit by maintaining the list of circles sorted by $x$ coordinate, and modifying this list online as the circles move. This won't help your asymptotic running time, but it avoids sorting each circle every time. If the circles stay relatively sparse (few cross the same vertical line), the binary search tree on the $y$-coordinates will be cheap to maintain.

The other issue is that knowing two circles intersect already does not improve the running time at all. Once two circles attach to each other, you will calculate their intersection every single time, which is a waste.

$\endgroup$
0
$\begingroup$

You could use something like a PKTree (or other spatial index), even though they do not take into account the radius of the circle. How? By using the range search algorithms over these data structures. Put the centres of the circles into the data structure, then do a range search for a circle (or even bounding box, if that's easier on the structure you choose) of a radius twice the radius of your largest circle. Then do a simple search within the results to find "actual" intersections.

This only works well if you don't have one circle that is significantly larger than most others.

Your worst case will be within n * (<range search of datastructure> + n), which is terrible, but that second n will in practise (that is, in the non-worst-case) not be n and will be small (if you choose an appropriate data structure).

$\endgroup$

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.