Hüllformen und Beschriftungspunkt
Drei Konstruktionen, die Hosts für Karten und Layouts brauchen: MinimumRotatedRectangle (das engste Rechteck um eine Geometrie, in beliebigem Winkel), MinimumBoundingCircle (der kleinste Kreis darum) und Polylabel (der beste Ort für eine Beschriftung in einem Polygon). ConcaveHull kam später, zusammen mit der Delaunay-Triangulierung, die es braucht (ADR 0029).
English version: 0026-huellformen-und-beschriftungspunkt.md
Consequences
- Platzierung: alle drei in der neuen statischen Klasse
ShapesinSpatialNET.Extensions, NamespaceSpatialNET, zusammen mit dem kleinen WerttypCircle(Coordinate Centre, double Radius). Für die Paketvalidierung ist das nur eine Ergänzung. Keine davon läuft über den Overlay-Kern. MinimumRotatedRectangle(geometry, factory?)liefertIGeometry2D: ein Polygon gegen den Uhrzeigersinn, ohne Z und M. Es ist das Rechteck mit der kleinsten Fläche; eine seiner Seiten liegt auf einer Seite der konvexen Hülle (eine bekannte Eigenschaft), also geht der Algorithmus mit Rotating Calipers in linearer Zeit die Hüllkanten durch. Bei gleicher Fläche gewinnt das Rechteck der ersten Hüllkante, das Ergebnis ist also deterministisch. Eine entartete Eingabe liefert wieConvexHulleinen Punkt oder die Linie zwischen den beiden äußersten Punkten und für eine leere Geometrie ein leeres Polygon. Hinweis: JTS bietetMinimumDiameter.GetMinimumRectangle, das Rechteck mit der kleinsten Breite, ein anderes; die Tests vergleichen nur als obere Schranke damit.MinimumBoundingCircle(geometry)liefertCircle?,nullfür eine leere Geometrie, Radius 0 für einen einzelnen Punkt. Es nutzt den Algorithmus von Welzl (Move-to-Front, iterativ) auf den Stützpunkten der konvexen Hülle in fester Pseudo-Zufallsreihenfolge, das Ergebnis ist also deterministisch. Der Radius wird am Ende auf den größten Abstand der Mitte zu einem Stützpunkt gesetzt, sodass jeder Stützpunkt innen liegt, was Rundung auch am Umkreismittelpunkt anrichtet.Circle.ToPolygon(factory?, quadrantSegments = 8)liefert4 * quadrantSegmentsStützpunkte auf dem Kreis, gegen den Uhrzeigersinn, als einbeschriebenes Polygon (es liegt im Kreis; die Punkte auf dem Kreis sind seine Stützpunkte); ein Kreis ohne Radius ergibt ein leeres Polygon.Polylabel(polygon, tolerance?)liefertCoordinate?,nullfür ein leeres Polygon: den Pol der Unzugänglichkeit, den Punkt im Inneren mit dem größten Abstand zum Rand, Löcher eingeschlossen. Der Algorithmus ist das Polylabel von Mapbox: eine Prioritätswarteschlange quadratischer Zellen, geordnet nach dem besten Abstand, den eine Zelle noch enthalten könnte, verfeinert, bis keine Zelle den besten Punkt um mehr als dietoleranceschlagen kann. Das Ergebnis liegt im Abstand zum Rand innerhalb vontoleranceam Optimum. Die Standardtoleranz ist ein Tausendstel der größeren Seite der Envelope. Ein Polygon aus mehreren Teilen liefert den Pol des Teils mit dem größten Kreis. Der vorzeichenbehaftete Abstand nutzt einen exakten Punkt-in-Ring-Test und einenSpatialIndexüber die Segmente für das nächste Segment. Ein Splitter ohne Innenpunkt fällt aufPointOnSurfacezurück. Es ist nur ein Punkt, ohne Z und M. (JTS nennt dasMaximumInscribedCircle; der Radius istDistancedes Punkts zum Rand.)- Exceptions (ADR 0012):
ArgumentNullExceptionbeinull,NotSupportedExceptionbei unbekannter Geometrieart,ArgumentOutOfRangeExceptionbei einertolerance, die nicht endlich oder nicht größer als 0 ist, und beiquadrantSegmentsunter 1,InvalidOperationExceptionohne Factory (bei den Methoden, die Geometrien erzeugen). Leere Eingaben werfen nie. - Tests (ADR 0008):
[Covers]-Tests statt Fixtures (die topologischen Randfälle des Tag-Katalogs passen nicht), mit handgeschriebenen Fällen und Property-Tests: Das Rechteck hat dieselbe Fläche wie eine Brute-Force-Suche über alle Hüllkanten (auch für lange Hüllen mit bis zu 400 Punkten) und ist nie größer als das Rechteck kleinster Breite von NTS; der Kreis stimmt im Radius mit dem NTS-MinimumBoundingCircleüberein und enthält jeden Stützpunkt; der Beschriftungspunkt liegt innen und innerhalb der doppelten Toleranz am NTS-MaximumInscribedCircle. - Playground und Dokumentation: Deskriptoren für die drei (ADR 0011; der Kreis wird als Polygon gezeigt, die Beschriftung als Punkt), ein Abschnitt in der Konzeptseite zu Maßen und Konstruktionen, Glossareinträge.
Considered Options
- Rechteck kleinster Breite statt kleinster Fläche (verworfen: Ein Layout braucht den engsten Kasten; die Breite ist eine andere Frage und kann später als
MinimumWidthgestellt werden) - Das Rechteck durch Ausprobieren aller Winkel (verworfen: Calipers über die Hüllkanten sind exakt und linear)
- Den Kreis nur als Polygon liefern (verworfen: Mitte und Radius sind, was die meisten Aufrufer wollen;
ToPolygonist ein Aufruf entfernt) - Polylabel auf einem Raster fester Auflösung (verworfen: Die adaptiven Zellen geben eine garantierte Toleranz mit wenigen Abstandsberechnungen)
ConcaveHulljetzt (damals verworfen, keine einheitliche Definition; später in ADR 0029 mit der Kantenlängen-Variante von JTS umgesetzt)