Maximum Inscribed Circle and Largest Empty Circle in JTS

There is often a need to find a point which is guaranteed to lie in the interior of a polygon.  Uses include placing cartographic labels, and using the point as a proxy for polygon containment or overlap (such as in polygon overlay).

There are several ways to compute a "centre point" for a polygon.  The simplest is the polygon centroid, which is the Center of Mass of the polygon area.  This has a straightforward O(N) algorithm, but it has the significant downside of not always lying inside the polygon!  (For instance, the centroid of a "U" shape lies outside the shape).  This makes it non-useful as an interior point algorithm.

JTS provides the InteriorPoint algorithm, which is guaranteed to return a point in the interior of a polygon.  This works as follows:

• Determine a horizontal scan line on which the interior point will be located. To increase the chance of the scan line having non-zero-width intersection with the polygon the scan line Y ordinate is chosen to be near the centre of the polygon's Y extent but distinct from all of vertex Y ordinates.
• Compute the sections of the scan line which lie in the interior of the polygon.
• Choose the widest interior section and take its midpoint as the interior point.

This works perfectly for finding proxy points, and usually produces reasonable results as a label point.  

However, there are polygons for which the above algorithm finds points which lie too close to the boundary for a label point.  A better choice would be the point that lies farthest from the edges of the polygon.  The geometric term for this construction is the Maximum Inscribed Circle. The farthest point is the center of the circle. 

Comparison of center points for a not-so-typical polygon

In the geographic domain this is romantically termed the Pole of Inaccessibility.  

Pole Of Inaccessibility in Canada

This point occurs at a node of the medial axis of the polygon, so in theory all that is needed is to compute the medial axis and test the set of node points.  However, medial axis algorithms are notoriously difficult to implement, and can be expensive to compute.  So it's appealing to look for a simple and fast way to compute a good approximation to the Maximum Inner Circle center.  There have been various approaches to this, including a geodetic grid-based approach by Garcia-Castellanos & Lombardo, and one by Martinez using random point distributions.  Recently Mapbox released a clever implementation which uses successive refinement of a grid along with a branch-and-bound technique to reduce the amount of searching needed.  

JTS now has a version of this algorithm, called MaximumInscribedCircle.  It significantly improves performance by using spatial indexing techniques for both polygon interior testing and distance computation.  This makes it very fast to find the MIC even for large, complex polygons.  Performance is key for computing label points, since it is likely to be used for many polygons on a typical map.

Grid refinement to find Maximum Inscribed Circle

An interesting property of the MIC is that its radius is the distance at which the negative buffer of the polygon disappears (becomes empty).  Thus the MIC radius length is a measure of the "narrowness" of a polygon.   This is often useful for purposes of simplification or data cleaning, to remove narrow polygonal artifacts in data.

Sequence of negative buffers containing the Maximum Inscribed Circle center

And, as the infomercials say, that's not all!  If you act today you also get a free implementation of  the Largest Empty Circle !  The Largest Empty Circle is defined for a set of geometric obstacles.  It is the largest circle that can be constructed whose interior does not intersect any obstacle and whose center lies in the convex hull of the obstacles.  The obstacles can be points, lines or polygons (although only the first two are currently implemented in JTS).  Classic use cases for the Largest Empty Circle are in logistics to find a location for a new chain store in a set of store locations; or to find the largest roadless area in environmental planning.

It turns out that the LEC can be computed by essentially the same algorithm as the MIC, with a few small changes.  And of course it also uses spatial indexing to provide excellent performance.

Largest Empty Circles for point and line obstacles

Maximum Inscribed Circle and Largest Empty Circle are now in JTS master, and will be released in the upcoming version 1.17.

Further Improvements

There are some useful enhancements that can be made:

• For Maximum Inscribed Circle, allow a second polygonal constraint.  This supports finding a label point within a view window rectangle.
• For Largest Empty Circle, allow a client-defined boundary polygon.  This allows restricting the circle to lie within a tighter bound than the convex hull
• For both algorithms, it should be feasible to automatically determine a termination tolerance