Table of Contents

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 Shapes in SpatialNET.Extensions, namespace SpatialNET, together with the small value type Circle(Coordinate Centre, double Radius). For the package validation this is an addition only. None of them runs the overlay core.
  • MinimumRotatedRectangle(geometry, factory?) returns IGeometry2D: 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, as ConvexHull does, a point or the line between the two extreme points, and an empty polygon for an empty geometry. Note that JTS offers MinimumDiameter.GetMinimumRectangle, which is the rectangle of least width, a different one; the tests compare with it only as an upper bound.
  • MinimumBoundingCircle(geometry) returns Circle?, null for 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) gives 4 * quadrantSegments vertices 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?) returns Coordinate?, null for 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 the tolerance. The result is within tolerance of 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 a SpatialIndex over the segments for the nearest segment. A sliver that has no inside point falls back to PointOnSurface. It is a point only, without Z and M. (JTS calls this MaximumInscribedCircle; the radius is Distance of the point to the boundary.)
  • Exceptions (ADR 0012): ArgumentNullException for null, NotSupportedException for an unknown geometry kind, ArgumentOutOfRangeException for a tolerance that is not finite or not greater than 0 and a quadrantSegments below 1, InvalidOperationException without 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 NTS MinimumBoundingCircle in radius and contains every vertex; the label point is inside and within twice the tolerance of the NTS MaximumInscribedCircle.
  • 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; ToPolygon is one call away)
  • Polylabel on a grid of fixed resolution (rejected: the adaptive cells give a guaranteed tolerance with few distance evaluations)
  • ConcaveHull now (rejected then, no single definition; done later in ADR 0029 with the edge-length variant of JTS)