Table of Contents

Natürliche Nachbarn, Qualitätsnetze und Fragen an ganze Flächen

Die Geländemethoden aus ADR 0037 und ADR 0039 beantworten, was eine Triangulierung in ihren Dreiecken sagt: die Höhe an einem Punkt, die Neigung eines Dreiecks, das Volumen über einer Ebene. Vier Fragen gehen darüber hinaus und kommen in der Praxis vor: eine glatte Höhe statt der Knicke der linearen, ein feineres Netz ohne spitze Dreiecke als Eingabe für eine Berechnung, wie viel Erde zwischen zwei Flächen liegt (vor und nach einem Aushub) und wo es steil ist und was von wo aus zu sehen ist. Dieser ADR fügt sie Triangulation hinzu.

English version: 0041-natuerliche-nachbarn-qualitaetsnetze-und-flaechenfragen.md

Consequences

  • Ort: Mitglieder der Klasse Triangulation, in drei partiellen Dateien in SpatialNET.Extensions (Triangulation.Interpolation.cs, Triangulation.Refine.cs, Triangulation.Surfaces.cs). Für die Paketvalidierung und die API-Verfolgung ist das nur eine Ergänzung (ADR 0028).

  • API:

    double InterpolateNaturalNeighbour(Coordinate point)
    Triangulation Refine(double minAngle = 20, double? maxArea = null, int maxSteinerPoints = 100_000)
    double MinAngle(int triangle)
    double MinAngle()
    (double Above, double Below) Volume(Triangulation other)
    IReadOnlyList<IPolygon2D> SlopeZones(IReadOnlyList<double> limits, IGeometryFactory? factory = null)
    bool LineOfSight(Coordinate from, Coordinate to, double observerHeight = 0, double targetHeight = 0)
    
  • InterpolateNaturalNeighbour ist die Interpolation nach Sibson. Die Höhe an einem Punkt ist das Mittel der Höhen der Eckpunkte, mit denen er verbunden würde, wenn man ihn einfügte, gewichtet mit der Fläche von deren Voronoi-Zellen, die der neue Punkt übernähme. Sie ist stetig, außer an den Eckpunkten glatt, gibt eine Ebene exakt wieder und bleibt im Bereich der Höhen um den Punkt (ein Polynom kann überschwingen, die lineare Interpolation hat Knicke an jeder Kante). Wie sie mit der vorhandenen Struktur berechnet wird:

    • Die Dreiecke, deren Umkreis den Punkt enthält (exaktes InCircle, ADR 0005), sind die Höhle, die der Punkt ausschneiden würde; sie werden vom Dreieck, das ihn enthält, über die Nachbarn gefunden.
    • Der Rand der Höhle ist der Ring der Nachbarn. Die neuen Voronoi-Ecken sind die Umkreismittelpunkte des Punkts mit jeder Randkante, die alten die der Dreiecke der Höhle, beide aus dem Umkreismittelpunkt des Voronoi-Diagramms (ADR 0036), der für Splitter exakt ist. Der Teil, den die neue Zelle einem Nachbarn nimmt, ist das Polygon aus zwei neuen Ecken und den alten Ecken dazwischen; seine Fläche ist das Gewicht.
    • Die Delaunay-Eigenschaft ist Voraussetzung. Eine Triangulierung mit Zwangskanten (Bruchkante, Polygon) liefert die lineare InterpolateZ, was dort die richtige Antwort ist, wo eine Fläche einen Knick haben muss. Dasselbe gilt für einen Punkt auf der Hülle (seine Zelle ist unbeschränkt) und als Sicherung, wenn eine Fläche nicht berechnet werden kann (ein Umkreismittelpunkt jenseits der Genauigkeit von double). Ein Punkt auf einem Eckpunkt gibt dessen Höhe, ein Punkt außerhalb der Dreiecke und ein Nachbar ohne Z geben NaN, wie bei InterpolateZ.
    • Tests: die Definition selbst als Orakel (die Flächen, die jede Zelle beim Einfügen des Punkts verliert, berechnet mit dem unabhängigen Halbebenen-Schnitt der Voronoi-Tests), eine Ebene, der Bereich der Höhen und die Stresstests für schmutzige Punkte.
  • Refine ist die Delaunay-Verfeinerung nach Ruppert. Sie fügt Punkte hinzu, bis kein Dreieck einen Winkel unter minAngle (Grad) oder eine Fläche über maxArea hat. Die Fläche bleibt, was sie war:

    • Der Rand und die Zwangskanten bleiben, wo sie sind; eine Kante, die einem neuen Punkt im Weg ist (der Punkt liegt in ihrem Thaleskreis), wird in der Mitte geteilt, sodass Zwangskanten zu Ketten kürzerer Zwangskanten werden (IsConstrained bleibt dort wahr, eine Randkante eines Polygons bleibt Zwangskante). Eine Triangulierung aus FromPolygon bleibt innerhalb ihrer Ringe, mit ihren Löchern.
    • Die neuen Punkte bekommen ihre Höhe aus der Triangulierung, die verfeinert wird, linear auf einer geteilten Kante, im Dreieck interpoliert bei einem Umkreismittelpunkt, sodass sie auf der ursprünglichen Fläche liegen.
    • Ein schlechtes Dreieck wird durch seinen Umkreismittelpunkt behoben, außer dieser bedrängt eine Kante, die dann stattdessen geteilt wird. Die Kanten kommen zuerst. Das schlechteste Dreieck wird zuerst behoben, ein Punkt nach dem anderen, in einem Netz, das an Ort und Stelle verändert wird (ADR 0045: ein Dreieck wird geteilt, die Kanten um den neuen Eckpunkt werden zurück zu Delaunay umgelegt, und die Kanten des Rands und der Zwangskanten werden nie umgelegt, nur geteilt); die Arbeit ist proportional zur Zahl der hinzugefügten Punkte, nicht zur Größe des Netzes. (Eine erste Fassung baute die Triangulierung nach jeder Runde von Einfügungen mit der Constrained-Delaunay-Maschinerie aus ADR 0038 neu, was für 100.000 Punkte 28 Sekunden brauchte; von der Messung gefunden.)
    • Abbruch. Das Verfahren von Ruppert hält nachweislich für minAngle bis etwa 20,7 Grad an, wenn sich keine zwei Zwangskanten unter einem kleineren Winkel treffen; in der Praxis hält es bis etwa 30 an. Über 34 Grad wird der Aufruf abgelehnt. Wo die Eingabe einen kleineren Winkel hat (die Spitze eines dünnen Keils), sind die spitzen Dreiecke dort nicht zu vermeiden, und ein Dreieck, dessen Umkreis kleiner als 1e-7 der Ausdehnung ist, bleibt, wie es ist. maxSteinerPoints beendet die Arbeit in jedem Fall; das Ergebnis ist dann eine gültige Triangulierung, nur nicht so fein wie verlangt. Ein Aufruf, der nichts zu tun hat, gibt dieselbe Instanz zurück.
    • MinAngle ist der kleinste Winkel eines Dreiecks in Grad (60 bei einem gleichseitigen) und der ganzen Triangulierung (NaN ohne Dreiecke).
    • Tests: kein Winkel unter der Grenze, die Fläche, jeder ursprüngliche Eckpunkt bleibt, jeder neue Eckpunkt liegt auf der Fläche (eine Ebene als Orakel), die größte Fläche, eine Bruchkante, die eine Kette von Zwangskanten auf der Linie bleibt, ein Polygon mit seinem Rand, die Grenze der Punkte und Stresstests auf schmutzigen Punkten.
  • Volume(other) ist Abtrag und Auftrag zwischen zwei Flächen, exakt über der Fläche, die beide abdecken: Die beiden Triangulierungen werden übereinandergelegt, jedes Dreieck der einen wird mit den Dreiecken der anderen geschnitten (konvexes Schneiden an drei Halbebenen, die Kandidaten aus dem Index), und über jedem Stück ist die Differenz zweier Ebenen eine Ebene, sodass das Volumen darüber und darunter dasselbe Integral ist wie bei Volume(z) (ADR 0039). Above ist dort, wo diese Fläche über der anderen liegt, Below wo darunter; vertauscht man beide, vertauschen sich die Werte, und Above − Below ist die Differenz der Nettovolumen. Dreiecke mit einem Eckpunkt ohne Z zählen nicht; ohne gemeinsame Fläche kommt (0, 0). Tests: Platten, eine Rampe gegen eine Ebene, teilweise Überdeckung, die Gleichheit mit Volume(z) für eine ebene zweite Fläche und die Symmetrie.

  • SlopeZones ist die Karte der Neigungen. Die Dreiecke werden nach Slope in Klassen eingeordnet (Klasse 0 unter der ersten Grenze, Klasse i von Grenze i − 1 bis Grenze i, die letzte ab der letzten Grenze), und jede Klasse wird zu einem Polygon; eine Klasse ohne Fläche ist ein leeres Polygon. Das Polygon entsteht nicht mit dem Overlay: Die Kanten, auf deren anderer Seite ein Dreieck einer anderen Klasse (oder keines) liegt, sind die Grenze; sie werden zu Ringen mit der Fläche links verkettet, Ringe im Uhrzeigersinn sind Löcher und gehören zum kleinsten Ring, der sie enthält, und ein Ring, der sich in einem Eckpunkt selbst berührt (eine Tasche, die den Rand in einem Punkt trifft, zwei Teile, die sich in einer Ecke treffen), wird dort aufgetrennt, sodass jeder Ring einfach ist. Die Dreiecke einer Triangulierung überlappen sich nie, also muss nichts vereinigt werden. Die Grenzen müssen endlich und streng aufsteigend sein. Tests: ein ebener Teil gegen eine Rampe, die Klassen überdecken die Fläche, jedes Dreieck liegt in seiner Klasse, jede Zone ist gültig und gleich der Vereinigung ihrer Dreiecke (mit dem Overlay als Orakel), Löcher und Teile, die sich in einer Ecke berühren, und der Stresstest auf schmutzigen Punkten.

  • LineOfSight fragt, ob das Gelände die Sicht versperrt. Die Linie vom Auge (die Fläche bei from plus observerHeight) zum Ziel (die Fläche bei to plus targetHeight) wird an jeder Stelle mit der Fläche verglichen, an der sie eine Kante oder einen Eckpunkt kreuzt, das sind dieselben Schnitte wie bei Drape (ADR 0039); dazwischen ist die Fläche linear, sodass nur diese Stellen geprüft werden müssen. Eine Linie, die das Gelände nur berührt (ein ebenes Feld mit beiden Höhen 0, ein Grat genau im Weg), ist frei, mit einer Toleranz von 1e-9 der Höhe. Ein Punkt außerhalb der Fläche oder ohne Höhe ergibt false; wo die Linie die Fläche verlässt (eine Einbuchtung eines Polygons), gibt es kein Gelände, das sie versperrt. Tests: ein Hügel, ebenes Gelände, Symmetrie und dass ein höheres Auge oder Ziel nie weniger sieht.

  • Geschwindigkeit. Einmalmessungen (--quick-terrain, Release-Build, gleichverteilte Zufallspunkte mit Höhen):

    Punkte 100k InterpolateZ (ms) 100k InterpolateNaturalNeighbour (ms) Volume(other) (ms) SlopeZones (ms) 10k kurze LineOfSight (ms) 1k lange LineOfSight (ms)
    10.000 144 386 44 17 115 95
    50.000 201 408 269 304 218 220
    Punkte Refine(25) (ms) Dreiecke vorher → nachher Kleinster Winkel vorher → nachher
    1.000 31 1.978 → 5.705 0,00 → 25,00
    10.000 181 19.977 → 51.884 0,00 → 25,00
    100.000 2.195 199.974 → 510.423 0,00 → 25,00

    Natürliche Nachbarn kosten etwa das Zwei- bis Zweieinhalbfache der linearen Höhe. Refine wächst etwa linear, und eine Fläche aus 100.000 Punkten wird in zwei Sekunden verfeinert. SlopeZones braucht kein Overlay und für 100.000 Dreiecke eine Viertelsekunde (mit der Vereinigung der Dreiecke per UnionAll waren es 14 Sekunden). Eine Sichtlinie (und Drape) kostet die Dreiecke entlang der Linie: Sie wird in Stücke von einigen Dreiecksgrößen geschnitten, und der Index wird nach der Envelope jedes Stücks gefragt, nicht nach der Envelope der ganzen Linie, die bei einer Diagonale mit dem Quadrat ihrer Länge wächst (vorher brauchten 1.000 Linien über 50.000 Punkte 1,8 Sekunden, jetzt 0,2).

  • Ausnahmen (ADR 0012): ArgumentOutOfRangeException für Koordinaten oder Höhen, die nicht endlich sind, für minAngle außerhalb von 0 bis 34, für ein maxArea, das nicht größer als 0 ist, für ein negatives maxSteinerPoints und für einen Dreiecksindex außerhalb des Bereichs; ArgumentNullException für null; ArgumentException für Grenzen, die nicht endlich oder nicht aufsteigend sind; InvalidOperationException ohne Factory.

  • Playground und Dokumentation: Einträge naturalNeighbour, refine, slopeZones, lineOfSight und surfaceVolume mit Beispielen (die Geländebeispiele werden geteilt, neu sind eines für die Sicht über einen Hügel und eines für einen Aushub), Abschnitte in der Konzeptseite „Triangulierung, Voronoi und Gelände“, Glossareinträge.

  • Nicht jetzt: ein Raster von interpolierten Werten (InterpolateNaturalNeighbour je Zelle aufrufen), natürliche Nachbarn unter Beachtung der Bruchkanten, Laplace oder andere Interpolationen, eine Sichtbarkeitsfläche (der Bereich, der von einem Punkt aus zu sehen ist) und die konformen und die Mindestgrößen-Netze von Shewchuk (Off-Center und konzentrische Schalen bei kleinen Eingangswinkeln).

Considered Options

  • Natürliche Nachbarn, indem der Punkt in eine Kopie des Netzes eingefügt wird und die Flächen daraus gelesen werden (verworfen: Es kopiert die Triangulierung bei jeder Abfrage; die Höhle des Punkts und die Flächen der Voronoi-Zellen liefern dieselben Gewichte aus der unveränderten Struktur)
  • Laplace-Interpolation (ohne Sibson), die nur Kantenlängen braucht (verworfen: Sie ist nicht die übliche Referenz, und ihre Gewichte weichen von denen nach Sibson ab, sodass jemand, der mit anderer Software vergleicht, andere Zahlen bekommt; sie kann ergänzt werden)
  • Natürliche Nachbarn unter Beachtung der Zwangskanten (verworfen: Die Logik der Höhle braucht die Delaunay-Eigenschaft, und eine Zwangskante heißt, dass die Fläche einen Knick hat, den die glatte Interpolation gerade beseitigen soll; der Rückfall auf die lineare Höhe ist die ehrliche Antwort)
  • Verfeinern durch Neubau der Constrained-Delaunay-Triangulierung nach jeder Runde von Einfügungen (die erste Fassung; nach der Messung verworfen: Sie nutzt den getesteten Code, kostet aber je Runde einen vollen Aufbau, 28 Sekunden für 100.000 Punkte, gegen 2 Sekunden mit einem Netz, das an Ort und Stelle verändert wird, ADR 0045)
  • Verfeinerung mit den Beweisen von Shewchuk (Off-Center, konzentrische Schalen für kleine Eingangswinkel) (vorerst verworfen: Die Größenuntergrenze und die Grenze für die Punkte lassen das Verfahren anhalten, und die Garantie für den Winkel gilt dort, wo die Eingabe es erlaubt)
  • Eine Funktion, die ein Raster von Höhen zurückgibt (verworfen: Ein Raster ist eine andere Struktur der Bibliothek, und der Aufruf je Zelle ist einfach; die natürlichen Nachbarn haben keine Knicke, sodass ein grobes Raster genügt)
  • Volume(other) durch Abtasten beider Flächen in einem Raster (verworfen: nicht exakt; der Schnitt zweier linearer Flächen ist exakt und schnell)
  • Eine Sichtbarkeitsfläche statt einer einzelnen Sichtlinie (vorerst verworfen: Sie ist ein Polygon aus einem Rundumlauf um den Beobachter, ein größeres Stück Arbeit; die Sichtlinie ist ihr Baustein und beantwortet die Frage für einen Punkt)