Bounding shapes and label point
Three constructions that hosts need for maps and layouts: MinimumRotatedRectangle (the tightest rectangle around a geometry, at any angle), MinimumBoundingCircle (the smallest circle around it) and Polylabel (the best place for a label inside a polygon). ConcaveHull came later, together with the Delaunay triangulation it needs (ADR 0029).
German version: 0026-huellformen-und-beschriftungspunkt.de.md
Consequences
- Placement: all three in the new static class
ShapesinSpatialNET.Extensions, namespaceSpatialNET, together with the small value typeCircle(Coordinate Centre, double Radius). For the package validation this is an addition only. None of them runs the overlay core. MinimumRotatedRectangle(geometry, factory?)returnsIGeometry2D: a counter-clockwise polygon, without Z and M. It is the rectangle of least area; one of its sides lies on a side of the convex hull (a known property), so the algorithm goes through the hull edges with rotating calipers in linear time. Among rectangles of equal area the one of the first hull edge wins, so the result is deterministic. A degenerate input gives, asConvexHulldoes, a point or the line between the two extreme points, and an empty polygon for an empty geometry. Note that JTS offersMinimumDiameter.GetMinimumRectangle, which is the rectangle of least width, a different one; the tests compare with it only as an upper bound.MinimumBoundingCircle(geometry)returnsCircle?,nullfor an empty geometry, radius 0 for a single point. It uses the algorithm of Welzl (move-to-front, iterative) on the vertices of the convex hull, in a fixed pseudo-random order, so the result is deterministic. The radius is finally set to the largest distance from the centre to any vertex, so every vertex lies inside whatever rounding did to the circumcentre.Circle.ToPolygon(factory?, quadrantSegments = 8)gives4 * quadrantSegmentsvertices on the circle, counter-clockwise, as an inscribed polygon (it lies inside the circle; the points on the circle are its vertices); a circle without radius gives an empty polygon.Polylabel(polygon, tolerance?)returnsCoordinate?,nullfor an empty polygon: the pole of inaccessibility, the point inside that is farthest from the boundary, holes included. The algorithm is the polylabel of Mapbox: a priority queue of square cells ordered by the best distance a cell could still contain, refined until no cell can beat the best point by more than thetolerance. The result is withintoleranceof the optimum in its distance to the boundary. The default tolerance is a thousandth of the larger side of the envelope. A polygon of several parts gives the pole of the part with the largest circle. The signed distance uses an exact point-in-ring test and aSpatialIndexover the segments for the nearest segment. A sliver that has no inside point falls back toPointOnSurface. It is a point only, without Z and M. (JTS calls thisMaximumInscribedCircle; the radius isDistanceof the point to the boundary.)- Exceptions (ADR 0012):
ArgumentNullExceptionfornull,NotSupportedExceptionfor an unknown geometry kind,ArgumentOutOfRangeExceptionfor atolerancethat is not finite or not greater than 0 and aquadrantSegmentsbelow 1,InvalidOperationExceptionwithout a factory (for the methods that create geometries). Empty input never throws. - Tests (ADR 0008):
[Covers]tests instead of fixtures (the topological edge cases of the tag catalog do not apply), with hand-written cases and property tests: the rectangle equals a brute-force search over all hull edges in area (also for long hulls of up to 400 points) and is never larger than the NTS minimum-width rectangle; the circle equals the NTSMinimumBoundingCirclein radius and contains every vertex; the label point is inside and within twice the tolerance of the NTSMaximumInscribedCircle. - Playground and documentation: descriptors for the three (ADR 0011; the circle is shown as a polygon, the label as a point), a section in the concept page for the measures and constructions, glossary entries.
Considered Options
- Rectangle of least width instead of least area (rejected: what a layout needs is the tightest box; the width is a different question and can be asked later as
MinimumWidth) - The rectangle by trying every angle (rejected: calipers over the hull edges are exact and linear)
- Returning the circle only as a polygon (rejected: the centre and radius are what most callers want;
ToPolygonis one call away) - Polylabel on a grid of fixed resolution (rejected: the adaptive cells give a guaranteed tolerance with few distance evaluations)
ConcaveHullnow (rejected then, no single definition; done later in ADR 0029 with the edge-length variant of JTS)