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.FromPointsAndLinesundTriangulation.FromPolygonund die ErweiterungsmethodeShapes.Triangulate(IPolygon2D), inSpatialNET.Extensions, NamespaceSpatialNET. Das Ergebnis ist dieTriangulationaus ADR 0037, mitIsConstrainedundConstrainedEdges, 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
linessind 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.factoryundgridSizezä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); einegridSize, die nicht endlich oder nicht größer als 0 ist, ist eineArgumentOutOfRangeException.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
Orient2DundInCircle(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.FromPolygontrianguliert 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, wieMakeValides liest (ADR 0020); eine Schleife (Bow-Tie) ergibt ihre zwei Dreiecke. Ein Polygon ohne Löcher mitnStützpunkten hatn − 2Dreiecke, 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.TriangulateistFromPolygon(...).ToPolygons(...): die Dreiecke als flache Liste von Polygonen wieDelaunayTriangles, 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
InterpolateZauf der Linie ist die lineare Interpolation entlang ihrer Kanten (ein Test).Ausnahmen (ADR 0012):
ArgumentNullExceptionbeinull,NotSupportedExceptionbei einer unbekannten Geometrieart,ArgumentOutOfRangeExceptionbei einer ungültigengridSize,InvalidOperationExceptionohne 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) FromPointsundFromPointsAndLinesmit einer Linie aus 100 Punkten10.000 7 und 14 – dasselbe 100.000 80 und 131 – FromPolygongegenPolygonTriangulator, 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 FromPolygonnicht mehr)100.000 9.605 61.712 FromPolygongegenPolygonTriangulator, ein zackiger sternförmiger Ring10.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
FromPolygonsie 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 exaktenInCirclelokal Delaunay); eine lange Bruchkante durch viele Punkte; eine Zwangskante durch einen Stützpunkt; sich kreuzende, überlappende und wiederholte Zwangskanten; ein Polygon alslines; Polygone (ein Quadrat, ein U, mit Loch, eine Schleife, kollinear) und zufällige sternförmige Polygone mit und ohne Loch (die Zahl der Dreiecke istn − 2bzw.+ 2je Loch, die Fläche ist die des Polygons, jeder Schwerpunkt liegt innen, jede Ringkante ist eine Kante) mit dem NTS-PolygonTriangulatorals 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) undTriangulate(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 (
FromPointsAndLinesmit dem Polygon alslinestrianguliert 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)