Tesselieren Sie eine Punkteebene

lese die erste Zeile, nenne sie N . Lies die restlichen Punkte in ein Array A .

Natürlich wird davon ausgegangen, dass Sie wirklich alle Punkte in der Gitterreihenfolge erhalten. Wenn nicht, sortiere sie zuerst.

Trennen Sie das Gitter in der Ebene in eine Reihe von Linien. Die Tesselation ist gegeben, indem jedes Paar von benachbarten Punkten auf einer Linie genommen wird und der nächste Punkt von jedem Mitglied des Paares in den benachbarten Linien zu dem Paar hinzugefügt wird.

Sie können die Ebene in Linien unter Verwendung von Vektorarithmetik trennen. Nehmen Sie den ersten Punkt in der Datei als Ebenenbasis und den Vektor als zweiten Punkt als X-Achse. Projizieren Sie den Vektor vom ersten Punkt an einen beliebigen Punkt auf dem X-Achsenvektor und verwenden Sie die Länge der Projektion als X-Koordinaten. Da Sie ein reguläres Raster annehmen, sollten diese Werte 0, 1, 2, 3 usw. sein und die Punkte einfach in Zeilen segmentieren.

Versuchen Sie für den Tesselationsalgorithmus, rechtwinklige Dreiecke benachbarter Punkte zu erzeugen und auf den Vektor zu schieben (ohne sie zu überlappen). Angenommen, Sie haben alle Punkte in einer m x n -Matrix in der richtigen Reihenfolge gespeichert, können Sie diese Dreiecke erstellen:

• {(i,j),(i+1,j),(i+1,j+1)} für 0 < i < m-1 und 0 < j < n-1 .
• {(i,j+1), (i+1,j+1), (i,j) für 0 < i < m-1 und 0 < j < n-1 .

Ich habe die Form {p1, p2, p3} für ein Dreieck und (x, y) für das Indexpaar des Punktes in der Matrix verwendet. In Ihrem Fall sind diese m und n Variablen gleich 5.

Vielleicht hilft Ihnen Delaunay Triangulation ? Dieser Link bietet einige Algorithmen, um eine Delaunay-Triangulation zu erhalten

Ein anderer Algorithmus wird hier angegeben.

Es gibt natürlich viele verschiedene Möglichkeiten, um eine Menge von Dreiecken aus einer Menge von Scheitelpunkten zu erhalten, daher bin ich mir nicht sicher, ob ich die gesamten Problemanforderungen verstehe.

Aber mein Ansatz würde wahrscheinlich in etwa so aussehen:

1. Um Fließkomma-Rundungen und / oder Datengenauigkeitsprobleme zu berücksichtigen, würde ich zuerst einen normalen Vektor für die Ebene bestimmen, indem ich etwas wie einen Algorithmus der kleinsten Quadrate benutze. (Obwohl Sie das Flugzeug selbst nicht brauchen, nur die Richtung.)

2. Schreiben Sie Algorithmen, um diesen normalen Vektor zu verwenden, um einige allgemeine Fragen wie "Ist Punkt D im Inneren des Dreiecks ABC?" zu bestimmen. und "Überschneiden sich die Segmente AB und CD?" (in der ebenen Projektion).

Wenn Sie eine bekannte Struktur für die Eingabe haben, die es von diesem Punkt an einfach macht, oder einen vorhandenen Ebenen-Algorithmus, den Sie verwenden möchten, großartig.

Wenn Sie nur einen Satz nicht überlappender Dreiecke erhalten möchten, die die konvexe Hülle tesselieren:

1. Beginnen Sie mit drei beliebigen Punkten und einem einzigen Dreieck. Erinnern Sie sich auch an einen geordneten Zyklus von Ecken, die das Grenzpolygon der bisher bedeckten Region bilden. Dann füge den Rest der Punkte nacheinander hinzu.

2. Wenn sich der neue hinzuzufügende Punkt im Inneren eines vorhandenen Dreiecks befindet, ersetzen Sie das Dreieck durch drei Subtriangles.

3. Andernfalls bestimmen Sie, welche N (N & gt; = 2) Liniensegmente von Grenzpolygonscheitelpunkten zu dem neuen Punkt das Grenzpolygon nicht schneiden. Addiere (N-1) neue Dreiecke. Der neue Punkt ersetzt (N-2) alte Punkte als neuen Eckpunkt im Begrenzungspolygon.

4. Angenommen, es ist eine gute Sache, nahezu kollineare Dreiecke und unnötig lange Segmente zu vermeiden: Schlingen Sie über die Dreieckskanten, die nicht an der Grenze liegen, und prüfen Sie, ob das von den zwei benachbarten Dreiecken abgedeckte Viereck konvex ist seine andere Diagonale ist (signifikant) kürzer als die gemeinsame Dreieckskante, die untersucht wird. Wenn ja, ersetzen Sie diese zwei Dreiecke. Wiederholen Sie diesen Vorgang, bis keine weiteren Substitutionen mehr möglich sind. (Diese Schleife muss enden, da die Gesamtlänge der Kanten immer kleiner wird, und es gibt eine endliche Anzahl von Tesselationen.)