Algorithmus zum Erstellen benachbarter Dreiecke

14

Ich habe ein System, in dem Sie einmal klicken können, um einen Knoten in einer Szene zu platzieren. Wenn Sie 3 Knoten platzieren, bildet sich ein Dreieck. Wenn Sie zukünftige Knoten platzieren, wird ein neues Dreieck erstellt, indem dieser Knoten mit den 2 nächstgelegenen vorhandenen Knoten verbunden wird.

Dies funktioniert die meiste Zeit gut, ist jedoch fehlerhaft, wenn es in der Nähe von Dreiecken mit sehr spitzen Winkeln verwendet wird, da einer der beiden nächstgelegenen Knoten häufig nicht verwendet werden sollte.

Siehe zum Beispiel das Bild unten. Das magentafarbene Dreieck ist das erste, das platziert wird. Wenn ich dann auf die mit X gekennzeichnete Position klicke, erhalte ich ein neues Dreieck, in dem sich die blaue Überlagerung befindet. Was ich will, ist ein neues Dreieck, in dem sich die grüne Überlagerung befindet. (dh in diesem Beispiel symmetrisch zum Magenta-Dreieck. Erläuterung: Das grüne und das Magenta-Dreieck überlappen sich nicht - das grüne Dreieck erstreckt sich unter dem blauen zum Knoten ganz links.)

Beispiel für tatsächliches und gewünschtes Verhalten

Wie kann ich bestimmen, welche 2 vorhandenen Scheitelpunkte beim Erstellen neuer Dreiecke verwendet werden sollen, damit Dreiecke nicht so überlagert werden?

BEARBEITEN : Die Suche nach der nächsten Kante liefert bessere Ergebnisse, aber keine perfekten. Betrachten Sie diese Situation:

Geben Sie hier die Bildbeschreibung ein

Der Test der nächsten Kante ist mehrdeutig und kann AB oder AC zurückgeben (da der nächstgelegene Punkt zu X für beide bei A liegt). Das gewünschte Ergebnis wäre AC, um das ACX-Dreieck ohne überlappende Kanten zu bilden. Wie könnte ich dieses Ergebnis sicherstellen? (Ich möchte lieber keine einzelnen Kantenüberlappungstests als Verbindungsunterbrecher durchführen, wenn dies möglich ist, da ich befürchte, dass der nächste Kantentest nicht unbedingt erkennt, dass die 2 aufgrund von Gleitkommapräzisionsproblemen genau gleich weit voneinander entfernt sind.)

Kylotan
quelle
Ist es nicht gut genug, die letzten 5 Scheitelpunkte zu betrachten und die beiden auszuwählen, die dem neu platzierten Scheitelpunkt am nächsten liegen? Ich würde Sie auf die Algorithmen für Dreiecksstreifen verweisen ( verweisen codercorner.com/Strips.htm ), aber diese verwenden oft nur die letzten zwei oder die letzten drei, die einen überspringen.
Roy T.
1
Überlappt das grüne Dreieck das magentafarbene? Was ist das Ziel davon? Muss der Benutzer steuern, wo und wie Dreiecke erstellt werden, oder wäre eine Triangulation einer Punktwolke akzeptabel?
Mistkerl
Um dies in einen Diagrammkontext zu setzen, möchten Sie im Wesentlichen Ihre Knoten verbinden, ohne dass sich Kanten überlappen. (Angenommen, die magentafarbenen / grünen Dreiecke würden sich eine Kante teilen)
MichaelHouse
Roy T: Nein - nur die 2 am nächsten zu wählen ist falsch, wie ich dachte, das Beispiel zeigt. Ist etwas unklar? Bummzack - Der grüne überlappt sich nicht mit dem magentafarbenen. Das Ziel ist es, ein Netz oder eine Grafik dieser Dreiecke zu erstellen. Der Benutzer braucht Kontrolle, ja. Byte56 - Ja, keine Kanten sollten sich kreuzen.
Kylotan
2
Wird der Benutzer die einzelnen Dreiecke tatsächlich sehen? Oder wird es eine durchgehende Oberfläche sein?
Bummzack

Antworten:

11

Anstatt den Mindestabstand zu den Knoten zu ermitteln, ermitteln Sie den Mindestabstand zur Kante (dh das durch die Knoten definierte Liniensegment).

Wenn der nächste Punkt ein Scheitelpunkt ist (für den Sie einen Gleitkomma-Epsilon ** -Test verwenden müssen), vergleichen Sie den Winkel zwischen der Linie vom neuen Punkt zum Scheitelpunkt und jeder der mit diesem Scheitelpunkt verbundenen Kanten. Wählen Sie den mit dem minimalen absoluten Winkel:

MinAngle(newPoint, vertex, edge1, edge2)
{
   newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
   edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
   edge2Unit = norm(edge2 - vertex);

   edge1Dot = dot(edge1Unit, newEdgeUnit);
   edge2Dot = dot(edge2Unit, newEdgeUnit);

   // you can simply compare dot products to find the minimum absolute angle
   if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
   return edge2;
}

** Um zu vermeiden, dass entartete Dreiecke hinzugefügt werden, die den Epsilon-Test stören könnten, sollten Sie einen Bereich um jeden Scheitelpunkt legen, in dem das Hinzufügen von Punkten nicht zulässig ist (etwa das Nichtzulassen von Punkten innerhalb eines Vielfachen des oben verwendeten Epsilons).

Jeff Gates
quelle
3
+1 - Dies ist meiner Meinung nach eine viel einfachere Antwort als die anderen und liefert mit größerer Wahrscheinlichkeit die richtigen Ergebnisse. Die Entfernung zum Segment ist mit einem intelligenten Schema ebenfalls einfach zu berechnen.
Steven Stadnicki
Einverstanden ist dies eine sauberere Methode. Wahrscheinlich, was ich erreicht hätte, wenn ich mehr darüber nachgedacht hätte: /
MichaelHouse
Ah, so nah! Aber wie bei der Antwort von Byte56 und dem Diagramm von Jimmy gibt es manchmal zwei äquidistante Kanten, von denen eine die Einschränkungen verletzt. Ich habe meine Frage aktualisiert.
Kylotan
@Kylotan Vielleicht reicht es in diesem Fall, einfach zu überprüfen, welche sich überschneidet, und die andere Option zu wählen? Suchen Sie nach Dreiecken, die die von Ihnen ausgewählte Kante teilen, und prüfen Sie, ob sich Ihr neues Dreieck auf derselben Seite wie das vorhandene befindet.
Kevin Reid
@Kylotan Stellen Sie sicher, dass Ihre Dreiecke immer die gleiche Wicklung haben? Wenn ja, können Sie die Kante ausschließen, die normal von Ihrem neuen Scheitelpunkt weg zeigt (mithilfe des Punktprodukts).
Bummzack
6

Nachdem das erste Dreieck platziert wurde, werden beim Platzieren eines neuen Scheitelpunkts immer zwei neue Kanten generiert. Die dritte Kante für das neue Dreieck ist immer eine gemeinsame Kante mit einem vorherigen Dreieck. Wenn Sie einen Weg finden könnten, die gemeinsame Kante zu bestimmen, würden Sie wissen, mit welchen Scheitelpunkten eine Verbindung hergestellt werden soll, aber das ist der schwierige Teil. Ich glaube, Sie können dies auf eine Weise tun, indem Sie eine Linie von Ihrem neuen Scheitelpunkt zur Mitte jeder der letzten drei erzeugten Kanten (oder wahrscheinlich der drei nächstgelegenen Kanten) ziehen.

Geben Sie hier die Bildbeschreibung ein

Wenn die Linie von Ihrem Scheitelpunkt zur Mitte der Kante nicht beiden anderen Kanten kreuzt, haben Sie Ihre gemeinsame Kante. Die gemeinsame Kante gibt an, mit welchen zwei Scheitelpunkten Ihr neuer Scheitelpunkt verbunden werden soll.

Jimmy brachte den Fall für einen Punkt vor, der nicht eindeutig ist, wohin das neue Dreieck so führen würde:

mehrdeutiges Dreieck

Das gibt Ihnen die Möglichkeit, zwischen zwei gültigen Dreiecken zu wählen. Vielleicht ist das Brechen der Krawatte, welcher Mittelpunkt am nächsten ist.

In Anbetracht Ihres Updates ist meine Lösung zwar komplexer, führt jedoch nur dann zu einem Gleichstand, wenn Sie zwei gültige Dreiecke haben. Mit dieser Methode würde Ihr zweites Beispielbild das gewünschte Ergebnis erzielen.

Geben Sie hier die Bildbeschreibung ein

MichaelHouse
quelle
Es ist möglich, dass sich zwei der Linien nicht mit Kanten schneiden (wenn X näher an einem Scheitelpunkt als an der Kante liegt)
Jimmy
@ Jimmy kannst du ein Bild von einer solchen Situation zeichnen?
MichaelHouse
Ah ja, dann haben Sie zwei Möglichkeiten, wo Sie das Dreieck platzieren möchten! Jede Seite würde funktionieren. Vielleicht können Sie mit demjenigen brechen, der den kürzesten Abstand zur Mitte hat.
MichaelHouse
@Kylotan funktioniert diese Lösung nicht? Sie haben in einem Kommentar zu Jeff erwähnt, dass Jimmys Bild zwei Fälle hat und einer die Einschränkungen verletzt, aber das ist nicht wahr. In Jimmys Bild würden beide Fälle nach meiner Methode gültige Dreiecke erzeugen.
MichaelHouse
1

Wenn Sie Ihr magentafarbenes Dreieck ABC haben, fügen Sie dann einen neuen Scheitelpunkt X ein. Ich denke, es ist offensichtlich, dass es zwei Linien gibt, die bei D beginnen und sich nicht zwischen den Kanten des Dreiecks ABC schneiden.

Diese beiden Leitungen können AX & BX, BX & CX oder AX & CX sein. Sie können Ihr Problem dann als das klassische Problem behandeln, dass sich zwei Linien schneiden. Sie können dann überprüfen, welches dieser Linienpaare sich nicht mit einer der ABC-Dreieckskanten schneidet, beispielsweise nach einer der Methoden aus dieser Frage . Daher haben Sie die zwei neuen Kanten des neuen Dreiecks.

Dan
quelle
Dies scheint gut zu sein, aber wie Sie gesagt haben, scheint es nur ein einziges Dreieck zu geben. Wie würde es auf viele verallgemeinern?
Kylotan
Hum ... wenn dein X und dein Dreieck ABC fest sind, gibt es wohl nur eines, nicht wahr?
Dan
Das System erstellt für jeden Knoten nach dem zweiten ein neues Dreieck.
Kylotan
Entschuldigung, ich habe Ihre Frage falsch verstanden. Lassen Sie mich sehen, wie ich dies auf viele Dreiecke ausweiten kann.
Dan
Nun, ich denke, Sie könnten die zwei Eckpunkte suchen, die X am nächsten liegen und bei Verbindung mit X keine Kante kreuzen?
Bummzack
1

Es ist ziemlich einfach herauszufinden, ob Sie sich in einem der eindeutigen Bereiche (1, 2, 3 unten) befinden: Behandeln Sie jede Kante Ihres Dreiecks als 2D-Ebene und testen Sie, auf welcher Seite der Ebene sich Ihr neuer Punkt befindet. Wenn Sie sich innerhalb von zwei, aber außerhalb eines befinden, entspricht dieser dem Rand des Dreiecks, der zwei Eckpunkte zu Ihrem neuen Dreieck beiträgt.

Voronoi-Regionen eines Dreiecks

Wenn Sie sich innerhalb von eins und außerhalb von zwei befinden, befinden Sie sich in einem mehrdeutigen Fall, in dem der Ihrem neuen Punkt am nächsten liegende Teil des Dreiecks eine Ecke ist. In diesem Fall können Sie eine 2D-Ebene aus dem Mittelpunkt der gegenüberliegenden Kante (derjenige, in der Sie sich befinden) und dem nächsten Scheitelpunkt (der von den beiden Ebenen, außerhalb derer Sie sich befinden) teilen. Sie können eine Kante auswählen, je nachdem auf welcher Seite dieser Ebene sich Ihr neuer Punkt befindet.

Beachten Sie, dass ein Ebenentest in 2D genauso funktioniert wie in 3D: Punktieren Sie einen Vektor von einer beliebigen Stelle in der Ebene bis zu Ihrem Punkt mit der Normalen der Ebene (in 2D ist dies die Senkrechte der Linie).

(Im Übrigen werden die durch Magenta getrennten Bereiche in diesem Bild Voronoi-Bereiche genannt. Sie sind die Bereiche des Raums, die Punkte enthalten, die einem bestimmten Merkmal - Kante oder Scheitelpunkt - des Dreiecks am nächsten liegen. Bearbeiten: Meine Terminologie hier ist eigentlich nicht ganz richtig, das sind nicht gerade Voronoi-Regionen.)

John Calsbeek
quelle
Mir ist nicht sofort klar, wie sich dies auf mehrere Dreiecke in der Szene verallgemeinert - insbesondere wenn das nächste Merkmal ein Scheitelpunkt ist, der von mehr als einem Dreieck geteilt werden kann.
Kylotan
@Kylotan Führen Sie einfach den Algorithmus für alle Dreiecke aus und wählen Sie das nächstgelegene Feature aus. Sie brauchen eine bahnbrechende Logik, egal was passiert. Wenn das nächste Feature ein gemeinsam genutzter Scheitelpunkt ist, sollten Sie sich für nur ein Dreieck im Randbereich (Nr. 1, Nr. 2, Nr. 3) befinden. Vielleicht können Sie das auswählen?
John Calsbeek