Search code examples
algorithmsortinggeometry2dplane

Making a list of outermost circles on a plane

I have a big rectangle filled with circles. The circles might overlap each other, but they all have the same diameter. I need to find the "borderline" circles. If there are gaps between these borderline circles - and the gap is bigger than a circle diameter - the one inside should also be included. Here are some examples: enter image description here

enter image description here

enter image description here

What I need to do in is to make these outer circles immovable, so that when the inner circles move - they never exit the rectangle. How can it be made, are there any known algorithms for such a thing? I'm doing it in TypeScript, but I guess, any imperative language solution can be applied

Solution

  • This is perhaps too conservative but certainly won't let any disks out.

    1. Compute a Delaunay triangulation on the centers of the circles. A high-quality library is best because the degenerate cases and floating-point tests are tricky to get right.

    2. Using depth-first search on the planar dual, find all of the faces that are reachable from the infinite face crossing only edges longer than (or equal to? depends on whether these are closed or open disks) two times the diameter.

    3. All of the points incident to these faces correspond to the exterior disks.