Making a list of outermost circles on a plane

user_3426308 0
Viewed 72

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

plane 2d sorting geometry algorithm
2 Answers

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.

user_21446690

I'm not quite sure that I have the answer to your question, but I put together two quick examples using the Tinfour Delaunay Triangulation library (which is written in Java). I had to digitize your points by hand, so I didn't quite hit the center in all cases.

The first picture shows that the boundary of a Delaunay Triangulation is a convex polygon. This is easy to build, simply add the vertices (circle centers) to Tinfour's IncrementalTin class and then ask it for the bounding polygon. Pretty much any Delaunay library will support this. So you wouldn't necessarily need Tinfour.

enter image description here

The problem is that this may include areas that are not valid for your interior circles. I played a little with ways to introduce concavities to the bounding polygon. As you can see below, the vertices in the lower-right corner had to be lopped off entirely (if I understand what you are looking for). I then iterated over the perimeter edges and introduced concavities where the vertex opposite each exterior edge was a "guard" vertex.

enter image description here

The code I wrote to do this is pretty messy. But if this is what you are looking for, I'll try to get it cleaned up and post it here.

user_126646680
Related