I have an object which consist of loosely packed, non-overlapping circles, of radius r.

Part of such an object is seen below, the object consist of the bold blue circles, and it extends further than shown on the figure.

The dashed blue circles of radius 2r (concentric with the bold blue circles) make up a unique piecewise circular curve around the object. The curve consist of all the dashed pieces of arc not overlapped by any bold blue circle or dashed blue circle. It is marked in green on the figure.

That green curve is what I want to find.

Example object made of circles.

Inputs and constraints

Given a point P on the green curve, and the centers (x,y) of all circles, I want to find the green curve shown on the figure.

I don't need to find the curve surrounding the whole object, which is very large (10k-10M circles), just part of it. If the green curve is a parametric curve with parameter t, I just need to find it for p < t < q centered on the point P.

The object constantly grows as more circles are added to it, and each time a circle is added I need the green curve centered on the point P, which is the location of the newly added circle.

A complexity of O(n^2), for finding the green curve, where n is the number of circles, would kill the simulation, for which this is needed.

I am hoping to find something which is O(p-q), i.e. linear in the length of arc I want to find.

Current suggestions for algorithms

First of all, most problems with O(n^2) complexity can be reduced to O(1) by utilizing lookup grids, which keep a list of circles currently residing in a given square region.

Intersections from scratch Circles close by the point P are found via the lookup grids, and all intersections between all circles are calculated. All intersections which lie inside a bold or dashed circle are invalidated/removed (e.g. the red intersections on the figure) since these can never be the intersections lying on the green curve. All intersections belonging to circles with only one intersection left are discarded as well, since circles with only one intersection on the perimeter contribute with zero arc length. Finally the remaining intersections (e.g. the green intersections on the figure) are used to construct the parametric green curve.

Maintaining a list of perimeter circles If an ordered list of the circles sitting in the perimeter is kept (i.e. --15-13-2-0-7-8-6-5-9-12-- for the figure) one could from the point P find circle #8, and from circle #8 find the the sequences 7-0-2-13-14 and 6-5-9-12. From these two sequences one could easily compute the parametric curve by calculating the intersections between neighboring circles, and discarding interior intersections. The challenge with this algorithm is to update the perimeter list each time a new circle is added. As an example of the challenge imagine a circle added between #5 and #12, touching one of them. This circle would remove #9 from the perimeter list changing it from -6-5-9-12- to -6-5-P-12-, and this is just a very simple example. The number of cases needing to be covered quickly gets out of hand.

Any other suggestions?

Do you have any suggestions other that the two mentioned, or do you have an improvements to the two methods?


Your Answer

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

Browse other questions tagged or ask your own question.