Table of Contents

Constrained-Delaunay-Triangulierung und die Triangulierung eines Polygons

Eine einfache Delaunay-Triangulierung (ADR 0029) kennt nur Punkte: Sie legt ihre Kanten dorthin, wo die Leerkreis-Regel es sagt, egal wo die Wirklichkeit einen Rücken, einen Graben, eine Böschung oder eine Flurstücksgrenze hat. Ein Geländemodell braucht Bruchkanten, Kanten, die Teil der Triangulierung sein müssen, und die Dreiecke sollen trotzdem so gut sein, wie die Zwangskanten es erlauben. Dieselbe Maschine liefert die Dreiecke innerhalb eines Polygons: seine Ringe als Zwangskanten und behalten, was innen liegt. Das braucht Darstellung, Flächenzerlegung und ein Netz einer Grenze. Beides macht Triangulation (ADR 0037): FromPointsAndLines und FromPolygon, und Triangulate für ein Polygon als flache Liste von Dreiecken.

English version: 0038-constrained-delaunay-und-polygon-triangulierung.md

Consequences

  • Ort: die statischen Methoden Triangulation.FromPointsAndLines und Triangulation.FromPolygon und die Erweiterungsmethode Shapes.Triangulate(IPolygon2D), in SpatialNET.Extensions, Namespace SpatialNET. Das Ergebnis ist die Triangulation aus ADR 0037, mit IsConstrained und ConstrainedEdges, um die Zwangskanten zu erkennen. Für die Paketvalidierung und die API-Verfolgung ist das eine reine Ergänzung (ADR 0028).

  • API:

    static Triangulation FromPointsAndLines(IGeometry2D points, IGeometry2D lines, IGeometryFactory? factory = null, double? gridSize = null)
    static Triangulation FromPolygon(IPolygon2D polygon, IGeometryFactory? factory = null, double? gridSize = null)
    static IReadOnlyList<IPolygon2D> Triangulate(this IPolygon2D polygon, IGeometryFactory? factory = null, double? gridSize = null)
    

    Die lines sind Polylinien (jedes Segment bleibt erhalten) oder Polygone (jede Kante jedes Rings bleibt erhalten); Punkte und Multipoints steuern nur ihre Stützpunkte als Punkte bei. Die Stützpunkte der Linien sind Stützpunkte der Triangulierung, eine Bruchkante braucht also keine zusätzlichen Punkte. factory und gridSize zählen nur, wenn sich Zwangskanten kreuzen (unten).

  • Was erhalten bleibt. Jedes Segment der Zwangskanten ist eine Kette von Kanten der Triangulierung. Eine Zwangskante, die genau durch einen Stützpunkt geht, wird dort geteilt (der Stützpunkt liegt auf der Linie, die Linie bleibt also als zwei Kanten erhalten). Zwangskanten dürfen sich berühren, Endpunkte teilen und kollinear überlappen, und eine Zwangskante darf doppelt angegeben sein; sie fallen auf dieselben Kanten zusammen. Die Triangulierung füllt die konvexe Hülle aller Stützpunkte, und jede Kante, die keine Zwangskante ist, ist lokal Delaunay (in den Tests für jedes Dreieck geprüft).

  • Sich kreuzende Zwangskanten werden genodet. Zwei Zwangskanten, die sich in einem Punkt kreuzen, der Endpunkt keiner von beiden ist, können nicht beide Kanten sein. Dann werden alle Zwangskanten zuerst wie die Linien eines Overlays genodet (Union, ADR 0005): Der Kreuzungspunkt wird ein Stützpunkt, und alle Zwangskanten werden aufs Gitter gerundet (gridSize, wie bei den Overlays), was ihre Stützpunkte um bis zur Hälfte davon verschieben kann. Das ist dieselbe Regel wie überall sonst in der Bibliothek, und sie gilt nur, wenn es eine Kreuzung gibt: Ohne sie werden die Zwangskanten genau so benutzt, wie sie sind, ohne Rundung. Kreuzungen werden exakt erkannt (der Orientierungstest aus ADR 0005 über einem räumlichen Index der Segmente), das Noden wird also nie durch Rundung übersprungen. Eine Factory braucht nur das Noden (InvalidOperationException, wenn es keine gibt); eine gridSize, die nicht endlich oder nicht größer als 0 ist, ist eine ArgumentOutOfRangeException.

  • Algorithmus (intern). Zuerst entsteht die Delaunay-Triangulierung aller Stützpunkte (ADR 0029). Dann wird jede Zwangskante durch Sloans Kantenflips (1993) eingefügt: Die Kanten, die das Segment kreuzt, werden entlang des Segments gefunden und nacheinander umgelegt (ein Flip geht nur, wenn das Viereck konvex ist, sonst wartet die Kante), bis das Segment eine Kante ist. Ein letzter Durchgang legt jede Kante um, die keine Zwangskante und nicht lokal Delaunay ist, bis keine mehr übrig ist (Lawson-Flips; eine Triangulierung, die die Zwangskanten enthält, endet in der Constrained-Delaunay-Triangulierung). Jede Entscheidung nutzt die exakten Prädikate Orient2D und InCircle (ADR 0029), das Ergebnis ist also für jede Eingabe eine gültige Triangulierung, und eine Zwangskante geht nie durch Rundung verloren. Zwangskanten werden über ihr Stützpunktpaar gemerkt, ein Flip, der die Halbkanten neu nummeriert, kann sie also nicht verwechseln. Punkte auf einem gemeinsamen Kreis erlauben mehrere Constrained-Delaunay-Triangulierungen, wie in ADR 0029.

  • FromPolygon trianguliert das Polygon mit seinen Ringen als Zwangskanten und behält die Dreiecke innen. Ein gültiges Polygon (ein erster Ring mit Löchern darin, alle Stützpunkte verschieden, kein Ring berührt oder kreuzt einen anderen oder sich selbst; kollineare Stützpunkte können ohne Ohr bleiben) nimmt den schnellen Weg unter Geschwindigkeit, der dieselben Dreiecke liefert; jede andere Eingabe nimmt den allgemeinen Weg unten. Das Innere wird von außerhalb der Hülle aus nach der Even-Odd-Regel entschieden: Ein Dreieck an der Hülle ist außen, außer die Hüllenkante ist ein Ring, und das Überschreiten eines Rings kehrt innen und außen um. Löcher bleiben also draußen, und ein ungültiges Polygon (Ringe, die sich kreuzen oder berühren) wird so gelesen, wie MakeValid es liest (ADR 0020); eine Schleife (Bow-Tie) ergibt ihre zwei Dreiecke. Ein Polygon ohne Löcher mit n Stützpunkten hat n − 2 Dreiecke, jedes Loch fügt zwei hinzu (es wird kein Stützpunkt ergänzt: Das ist eine Triangulierung der eigenen Stützpunkte des Polygons, kein Netz mit zusätzlichen Punkten). Jede Kante eines Rings ist eine Kante eines Dreiecks (IsConstrained), und die Dreiecke am Rand haben dort −1 als Nachbarn. Ein Polygon mit weniger als drei verschiedenen oder nur kollinearen Stützpunkten hat keine Dreiecke.

  • Triangulate ist FromPolygon(...).ToPolygons(...): die Dreiecke als flache Liste von Polygonen wie DelaunayTriangles, aber in der Reihenfolge ihrer Ids.

  • Z. Die Stützpunkte tragen das Z der Punkte, aus denen sie stammen; ein Stützpunkt, der Stützpunkt einer Linie und ein Punkt ist, nimmt das Z des ersten, das eins hat (die Punkte zuerst). Die beim Noden entstandenen Stützpunkte haben ein vom Overlay interpoliertes Z (ADR 0015). Eine Bruchkante mit Z legt also die Höhe entlang ihrer fest, und InterpolateZ auf der Linie ist die lineare Interpolation entlang ihrer Kanten (ein Test).

  • Ausnahmen (ADR 0012): ArgumentNullException bei null, NotSupportedException bei einer unbekannten Geometrieart, ArgumentOutOfRangeException bei einer ungültigen gridSize, InvalidOperationException ohne Factory, wenn sich Zwangskanten kreuzen. Zu wenige oder kollineare Stützpunkte ergeben eine leere Triangulierung, keine Ausnahme.

  • Geschwindigkeit. Einmalmessungen (--quick-voronoi, Release-Build). Eine Bruchkante durch 100 der Punkte kostet etwa so viel wie die Triangulierung der Punkte selbst:

    Fall N SpatialNET (ms) NTS (ms)
    FromPoints und FromPointsAndLines mit einer Linie aus 100 Punkten 10.000 7 und 14 –
    dasselbe 100.000 80 und 131 –
    FromPolygon gegen PolygonTriangulator, ein glatter Ring (eine echte Grenze) 1.000 1,9 0,6
    dasselbe 10.000 21 16
    dasselbe 100.000 427 1.234
    dasselbe, nur die Delaunay-Triangulierung der Ring-Stützpunkte (macht FromPolygon nicht mehr) 100.000 9.605 61.712
    FromPolygon gegen PolygonTriangulator, ein zackiger sternförmiger Ring 10.000 89 46
    dasselbe 100.000 6.520 3.621

    Bei einem Polygon entscheidet der erste Schritt, und ein gültiges Polygon geht ihn nicht. Die Stützpunkte einer Grenze liegen auf einer Kurve, und die Delaunay-Triangulierung von Punkten auf einer Kurve ist für jeden Algorithmus teuer: Sie besteht aus langen dünnen Dreiecken, und die Kantenflips laufen weit (9,6 s für 100.000 Stützpunkte eines glatten Rings und 62 s für den NTS-Builder auf denselben Punkten). Darum baut FromPolygon sie für ein gültiges Polygon gar nicht: Es schneidet Ohren ab (zuerst das mit dem kleinsten Umkreis, damit die Dreiecke schon nahe an Delaunay sind; Löcher werden durch Brücken mit dem Außenring verbunden) und macht die Kanten dann mit denselben exakten Flips wie oben Delaunay, wobei die Ringkanten fest bleiben; das endet in derselben Constrained-Delaunay-Triangulierung. Der glatte Ring aus 100.000 Stützpunkten sinkt von 9,8 s auf 0,4 s, schneller als der NTS-PolygonTriangulator (1,2 s), der ebenfalls Ohren abschneidet. Was an Zeit bleibt, ist die Prüfung der Eingabe und das Abschneiden. Der zackige Ring, dessen lange Kanten jede räumliche Abfrage tausende Kandidaten liefern lassen, wird von der Prüfung bestimmt, dass sich keine zwei Kanten kreuzen oder berühren (dieselbe Prüfung braucht der allgemeine Weg für Kreuzungen), und ist nicht schneller als zuvor; NTS ist dort schneller.

  • Tests (ADR 0008): [Covers]-Tests. Eine erzwungene Diagonale; zufällige Zwangskanten zwischen zufälligen Punkten, die viel umlegen müssen (jede Zwangskante ist von Zwangskanten abgedeckt und jede Zwangskante liegt auf einer Zwangslinie; Dreiecke gegen den Uhrzeigersinn; die Fläche ist die der Hülle; jede innere Kante, die keine Zwangskante ist, ist mit dem exakten InCircle lokal Delaunay); eine lange Bruchkante durch viele Punkte; eine Zwangskante durch einen Stützpunkt; sich kreuzende, überlappende und wiederholte Zwangskanten; ein Polygon als lines; Polygone (ein Quadrat, ein U, mit Loch, eine Schleife, kollinear) und zufällige sternförmige Polygone mit und ohne Loch (die Zahl der Dreiecke ist n − 2 bzw. + 2 je Loch, die Fläche ist die des Polygons, jeder Schwerpunkt liegt innen, jede Ringkante ist eine Kante) mit dem NTS-PolygonTriangulator als Orakel für Zahl und Fläche; zufällige Polygone mit bis zu neun Löchern, in beiden Richtungen, auf beiden Wegen (Ohren abschneiden mit Flips, und alle Stützpunkte mit eingezwungenen Ringen): dieselben Dreiecke, weil die Constrained-Delaunay-Triangulierung ohne Punkte auf einem gemeinsamen Kreis eindeutig ist; Polygone, die der schnelle Weg nicht nehmen kann (ein Loch oder ein Stützpunkt, der einen Ring berührt, ineinanderliegende Löcher) und die der allgemeine Weg trotzdem trianguliert; ein Polygon mit 3.000 Stützpunkten; Argumentfehler.

  • Playground und Dokumentation: Deskriptoren für ConstrainedDelaunay (Punkte und Bruchkanten) und Triangulate (ein Polygon) mit Beispielen (ADR 0011). Die Konzeptseite „Triangulierung, Voronoi und Gelände“, je ein Snippet für Bruchkanten und Polygone, Glossareinträge.

  • Vorerst nicht dabei: konforme und Qualitäts-Triangulierungen, die Punkte ergänzen (Steiner-Punkte, ein Mindestwinkel; NTS hat einen konformen Builder), eine Triangulierung eines Polygons mit zusätzlichen Punkten darin (FromPointsAndLines mit dem Polygon als lines trianguliert die ganze konvexe Hülle und behält die Dreiecke außerhalb des Polygons; der Aufrufer kann sie entfernen), nachträgliches Entfernen und Einfügen von Zwangskanten.

Considered Options

  • Ear Clipping für Polygone als einzige Methode (verworfen: Seine Dreiecke sind nicht Delaunay, es kann weder Bruchkanten noch innere Punkte aufnehmen, und die robusten Varianten brauchen so viel Technik wie die Constrained-Triangulierung, die auch die Dreiecke für Gelände liefert; als erster Schritt des Wegs für gültige Polygone wird es verwendet, wo die Flips die Dreiecke dann Delaunay machen)
  • Eine konforme Delaunay-Triangulierung, die die Zwangskanten teilt, bis sie Delaunay-Kanten sind (verworfen: Sie fügt Stützpunkte hinzu, die nicht in der Eingabe sind, die Stützpunkte einer Triangulierung wären also nicht mehr die Punkte des Nutzers; Zwangskanten als Kanten erhalten sie)
  • Jedes Mal noden (verworfen: Es würde die Stützpunkte jedes Polygons aufs Gitter runden, obwohl sie sich nicht kreuzen; es geschieht nur bei Bedarf)
  • Ein Fehler, wenn sich Zwangskanten kreuzen (verworfen: Bruchkanten und gezeichnete Ringe kreuzen sich, und das Overlay-Noden, das die Bibliothek überall sonst hat, ist die Antwort)
  • Shewchuks Triangle oder eine andere native Bibliothek (verworfen: Die Bibliothek hat keine Abhängigkeiten, ADR 0001, und die exakten Prädikate, die sie braucht, gibt es schon)
  • Die Zwangskanten vor den Punkten einfügen, als Sweep (verworfen: Das Einfügen in die fertige Delaunay-Triangulierung ist einfach, lokal und nutzt sie wieder; die Kosten stehen oben)
  • Das Innere eines Polygons durch den Schwerpunkt jedes Dreiecks entscheiden (verworfen: Der Schwerpunkt eines dünnen Dreiecks kann durch Rundung danebenliegen, während das Flutfüllen über Zwangskanten kombinatorisch und exakt ist)
  • Die Zwangskanten als Kennzeichen an Halbkanten halten (verworfen: Flips nummerieren Halbkanten neu; Stützpunktpaare sind stabil)