Table of Contents

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 Shapes in SpatialNET.Extensions, Namespace SpatialNET, zusammen mit dem kleinen Werttyp Circle(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?) liefert IGeometry2D: 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 wie ConvexHull einen Punkt oder die Linie zwischen den beiden äußersten Punkten und für eine leere Geometrie ein leeres Polygon. Hinweis: JTS bietet MinimumDiameter.GetMinimumRectangle, das Rechteck mit der kleinsten Breite, ein anderes; die Tests vergleichen nur als obere Schranke damit.
  • MinimumBoundingCircle(geometry) liefert Circle?, null fü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) liefert 4 * quadrantSegments Stü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?) liefert Coordinate?, null fü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 die tolerance schlagen kann. Das Ergebnis liegt im Abstand zum Rand innerhalb von tolerance am 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 einen SpatialIndex über die Segmente für das nächste Segment. Ein Splitter ohne Innenpunkt fällt auf PointOnSurface zurück. Es ist nur ein Punkt, ohne Z und M. (JTS nennt das MaximumInscribedCircle; der Radius ist Distance des Punkts zum Rand.)
  • Exceptions (ADR 0012): ArgumentNullException bei null, NotSupportedException bei unbekannter Geometrieart, ArgumentOutOfRangeException bei einer tolerance, die nicht endlich oder nicht größer als 0 ist, und bei quadrantSegments unter 1, InvalidOperationException ohne 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 MinimumWidth gestellt 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; ToPolygon ist ein Aufruf entfernt)
  • Polylabel auf einem Raster fester Auflösung (verworfen: Die adaptiven Zellen geben eine garantierte Toleranz mit wenigen Abstandsberechnungen)
  • ConcaveHull jetzt (damals verworfen, keine einheitliche Definition; später in ADR 0029 mit der Kantenlängen-Variante von JTS umgesetzt)