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

In the geographic domain this is romantically termed 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*

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

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.

There are some useful enhancements that can be made:

**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

## No comments:

Post a Comment