Table of Contents

Schnelle Beschriftungspunkte, und ein Außenlauf des Clip-Vorfilters als sein Netto-Weg am Rand

Ein Kartenserver beschriftet hunderte Karten pro Sekunde, und für eine Beschriftung zählt ein billiger Punkt im Inneren mehr als der beste. Polylabel (ADR 0026) liefert den schönsten Punkt, kostet aber etwa 130 ms für ein Polygon mit 100.000 Stützpunkten, und der Schwerpunkt mit Locate allokiert Megabytes. Zwei neue Methoden liefern einen Innenpunkt in zwei Durchläufen über die Stützpunkte ohne Allokation und weitere Punkte lazy, wenn der erste mit einer anderen Beschriftung kollidiert. Im selben Schritt hat Clip eines großen, verrauschten Polygons seine fast quadratischen Kosten verloren (2,1 s und 930 MB bei 100.000 Stützpunkten, bis zur OutOfMemoryException).

English version: 0053-schnelle-beschriftungspunkte-und-clip-vorfilter.md

Konsequenzen

  • Shapes.FastPolygonLabel(polygon) liefert Coordinate?, null bei leerem Polygon oder einem ohne Fläche. Durchlauf eins: der Flächenschwerpunkt; Ringe, die wie der größte Ring orientiert sind, addieren, die anderen subtrahieren, Ringe müssen also nicht als Schale oder Loch typisiert sein. Durchlauf zwei: die Schnittpunkte der waagerechten Linie durch den Schwerpunkt mit allen Ringen. Liegt der Schwerpunkt zwischen Schnittpunkt 2k und 2k+1 (Even-Odd), ist er der Punkt, sonst die Mitte des breitesten Innenstücks dieser Linie. Trifft die Linie nichts, die Linie durch die Mitte der Envelope, dann PointOnSurface, dann Polylabel. Nur Puffer aus dem Pool; ohne Z und M.
  • Shapes.FastAlternativePolygonLabelsLazy(polygon, seed, options) liefert Innenpunkte lazy: Vor der Frage nach dem ersten wird nichts berechnet. Die Punkte liegen auf waagerechten Scanlinien, zuerst die Linie durch den Seed, dann Linien, die die Envelope immer weiter halbieren (½, ¼, ¾, ⅛, …, van der Corput); auf jeder Linie kommen die Punkte nächst dem Seed zuerst, bei Gleichstand nach x. Jede Scanlinie ist ein Durchlauf über die Stützpunkte; es gibt keinen Index.
  • AlternativeLabelOptions (ein Sealed Record mit Init-Properties, zum Aufheben und Wiederverwenden): Separation (zum Seed und zu jedem Punkt davor), MinClearance (zum Rand, Löcher eingeschlossen, ein exakter Abstand je Kandidat), MaxCount (Standard 16), MaxScanlines (das Arbeitsbudget, Standard 32), CancellationToken (beendet die Folge ohne Exception). Ungültige Optionen werfen ArgumentOutOfRangeException beim Aufruf, nicht während der Aufzählung.
  • Zusagen: Jeder Punkt liegt nach Even-Odd über alle Ringe echt im Inneren, mit derselben Schnittformel für Scanlinien und Innentest; die Reihenfolge ist deterministisch; ein leeres oder entartetes Polygon gibt eine leere Folge.
  • Clip-Vorfilter: Der Envelope-Vorfilter von Clip, Intersection und Difference (RingClipper) ersetzte jeden Stützpunkt eines Ringteils außerhalb des Rechtecks durch seine Projektion auf den Rand. Ein verrauschter Außenlauf wurde so zu zehntausenden übereinanderliegenden Segmenten auf einer Randlinie, und der Snap-Rounding-Noder führte jedes durch jedes Hot Pixel darauf. Ein Außenlauf wird jetzt durch seinen Netto-Weg am Rand ersetzt: sein Anfang, die Ecken, die er in seiner abgewickelten Umfangsposition passiert, sein Ende. Beide Wege sind auf dem Rand homotop, die Umlaufzahl jedes inneren Punkts bleibt also gleich und die Ergebnisse auch. Der Noder sucht die Hot Pixel eines Segments außerdem in x- oder y-Ordnung, je nachdem, welcher Bereich kürzer ist.
  • Gemessen (BenchmarkDotNet, glattes konkaves Polygon mit 5 km Radius und feinem Rauschen): Clip mit 100.000 Stützpunkten 2.160 ms / 930 MB → 107 ms / 66 MB; FastPolygonLabel 3,5 / 44 / 405 µs bei 1.000 / 12.000 / 100.000 Stützpunkten ohne Allokation; die erste Alternative 1,4 / 15 / 128 µs mit etwa 300 Byte.

Betrachtete Optionen

  • Best-First-Suche über Quadtree-Zellen nach Randabstand, wie Polylabel, aber lazy und mit Sperrkreisen (abgelehnt: Jede Zelle braucht den Randabstand, ohne Index ein Durchlauf je Zelle, mit Index eine Allokation von O(n); Polylabel als Stellvertreter ist etwa 300-mal langsamer als eine Scanlinie)
  • Ein Kreis von Punkten um den Schwerpunkt, jeder per Jordan geprüft, wie die klassische gView-Beschriftung (abgelehnt: ein Durchlauf je Kandidat, eine Scanlinie liefert viele Kandidaten je Durchlauf)
  • Ein eigener Rechteck-Clip (Sutherland–Hodgman oder Weiler–Atherton) statt des Overlays (vorerst abgelehnt: ADR 0022 hat Brücken am Rand abgelehnt, Ergebnisse, wo der Rand schneidet, liegen auf dem Gitter, und er bräuchte einen Rückfall für Stützpunkte auf dem Rand; für die verbleibende Allokation bleibt er möglich)
  • Nur den Noder verbessern (abgelehnt: Er halbiert die Zeit, aber die übereinanderliegenden Segmente bleiben und mit ihnen der Speicher)