How to find the largest circle that lies within a sampled boundary?

Given sets of 2D points which are the boundaries of an irregular shape, a shape which may not be convex and may have internal holes, is there an algorithm to find the开发者_开发百科 largest circle that fits within the boundaries?

I've done a good bit of searching, and I do find algorithms that are close, such as the largest empty circle problem, but none that I have found so far match the constraints I have.

---

Problem is not good defined since set of points don't bound any area. Boundary you mention should be some curve, probably polygon. Without that you can't say that there are internal holes, and also can't ask for circle to be within boundary. With this definition, you can create circle of any size on "outside" that touches few set points.

If you use polygon to specify boundary, Aioobe's link is good one. If you redefine problem to find maximal radius circle touching at least 3 points of given set, than it is same as checking for circumcircles of Dalaunay triangulation.

---

Motivation. Shapes given by points that sample the shape first reminds me of the concept of alpha shapes and their relation to persistent topology. See these slides for related pictures.

Anyhow, alpha shapes have an intimate relation to the Voronoi diagram of points, which is the dual (as a planar graph) to the Delaunay triangulation.

Solution. What I suggest is to consider all Voronoi nodes and take the node with the largest clearance radius (distance to its defining points) as the point you look for:

In the dual setting of Delaunay triangulations this node corresponds to the Delaunay triangle with the largest circumcircle.

This solution is also motivated by the maximum inscribed circle problem in computational geometry.

Another way to look at it is the grass-fire interpretation of Voronoi diagrams: Consider a grass fire starting at each input point. The fire grows in each direction at unit speed. The red point in the middle is the latest to be reached within the convex hull.

Analysis & implementation. The time complexity of the algorithm is O(n log n) for the Voronoi diagram and O(n) to find the Voronoi node with the largest clearance. A classic implementation is qhull. There seems to be an C++ implementation in boost that does that for you. But any Delaunay triangulation code would be fine, too.

Possible issues. If the shape is similar to an Omega letter – which possesses a large pocket – then the Voronoi node with the largest clearance is "outside" the Omega shape. Hence, one would need to get a better grip on the notion of "inside" and "outside" of a sampled shape. Here again the initially mentioned alpha shape may help, c.f. a survey by Edelsbrunner, who invented alpha shapes.

---

A very dumb algorithm :) (likely something faster is possible)

The largest circle should touch at least 3 objects (object is either vertex or line).

So you can count all combinations O(n^3), build a circle for each one, check that it lies inside of the area (O(n)) and select the largest one. Totally - O(n^4).