Algorithmus, um Kanten mit Ecken (2D und 3D) in einem Netz zu finden

StackOverflow https://stackoverflow.com/questions/2294032

Frage

Ich habe eine eine Masche, mit bestimmten Typen von Elementen (beispielsweise dreieckig, tetra). Für jedes Element I bekanntlich seine Ecken d.h. ein dreieckförmiges Element 2D wird 3 Knoten v1, v2 und v3, deren x, y, z sind Koordinaten bekannt.

Frage 1

Ich suche einen Algorithmus, der alle Kanten zurückkehren ... in diesem Fall:

Kante (v1, v2), Kante (v1, v3), Kante (v2, v3). Je nachdem, wie viele Ecken hat jedes Element, bestimmt der Algorithmus sollte effizient die Kanten.

Frage 2

Ich bin mit C ++, so wird das sein, was der effizienteste Weg, um die Informationen über die Kanten durch den obigen Algorithmus zurück zu speichern? Beispiel alles, was ich bin an ist ein Tupel (v1, v2), dass ich für einige Berechnung verwenden möchten, und dann vergessen Sie es.

Danke

War es hilfreich?

Lösung

Sie können die Halbranddatenstruktur verwendet werden.


Grundsätzlich Ihre Masche hat auch eine Liste von Kanten, und es ist eine Randstruktur pro Paar verts in jede Richtung. Das heißt, wenn Sie verts A und B gibt es zwei Randstrukturen irgendwo gespeichert, eine für A-> B und eine für B-> A. Jede Kante hat drei Zeiger, ein genannt vorherigen, eine nächste und eine namens Zwilling genannt. Im Anschluss an die nächste und vorherige Zeiger führt Sie rund um die Kanten des Dreiecks oder eines Polygons in dem Netz. Der Aufruf Twin bringt Sie zu der benachbarten Kante in dem benachbarten Polygon oder Dreieck. (Blick auf die Pfeile int er Bild) Dies ist die nützlichste und ausführliche Randdatenstruktur ich kenne. Ich habe es verwendet Maschen zu glätten durch neue Kanten zu schaffen und die Zeiger zu aktualisieren. BTW, sollte jede Kante auch auf einen Scheitelpunkt, so weiß es, wo es im Raum ist.

Andere Tipps

Es gibt wirklich drei Teile auf Ihre Frage, nicht zwei:

  • Welche Datenstrukturen verwendet werden sollen, um das Netz zu repräsentieren?
  • Was Algorithmus soll ich verwenden, um Extrakt Kanten von den Gitterdatenstrukturen?
  • Wie sollte der resultierende Satz von Kanten dargestellt werden?

Sie haben weitere Fragen zu stellen geeignete Antworten zu finden.

Was Datenstrukturen verwendet werden sollen, um das Netz zu repräsentieren?

Was Elementtypen brauchen Sie um?

Wenn Sie nur Griff Polygone müssen (geschlossene Schleifen) und simplicials (jeder Knoten mit jedem anderen Knoten in dem Elemente verbunden ist, wie zum Beispiel eines Tetraeders), dann eine geordnete Knotenliste ist ausreichend, da Kanten aus der Liste impliziert werden können von Knoten. Wenn auf der anderen Seite müssen Sie Elementtypen wie Hexaeder, Prismen oder allgemeine Polyeder zu handhaben, dann müssen Sie weitere Informationen über die Elementtopologie. Eine einfache Anordnung von Kantenabbildungen ist oft ausreichend. Es ist nur ein Array [] [2] des Indizes in die Liste des Elements von Knoten, die Sie sagt, wie die Punkte für einen bestimmten Elementtyp verbinden.

Die Halbrandstruktur von Chris beschrieben ist eine gute Wahl nur für 2D. In 3D es kann eine beliebige Anzahl von Elementen sein, zu jeder Kante befestigt ist, nicht nur zwei. Es ist eine 3D-Erweiterung der Halbkantendarstellung, dass ich denke, ist ein Windrad Struktur genannt.

Wenn Sie haben beliebige Elementtypen zu unterstützen, ziehe ich ein umfangreichere Datenstrukturelement Topologie darstellen. Eine weit verbreitete Möglichkeit ist die Verwendung Kanten und Co-Kanten. Es ist eine Randstruktur für jedes Paar von verbundenen Knoten, und eine Co-Kante für jede Verwendung dieser Kante in einem Elemente. Es ist ähnlich wie der Windrad Ansatz, aber ein wenig deutlicher.

Was Algorithmus soll ich zu extrahieren Kanten verwendet aus den Elementen?

Wie wichtig ist die Geschwindigkeit oder Erinnerung? Sollte sind das Ergebnis jeder Kante einmal pro Element, oder nur einmal, egal wie viele Elemente es verwenden? Ist die Reihenfolge der Kanten im Ergebnis eine Rolle? Ist die Reihenfolge der Knoten jeder Kante Materie?

Es ist ziemlich schwer, mit einem Algorithmus für beliebige Elementtypen zu entwickeln, die nur jede Kante einmal besuchen werden. Um jede Kante sicherzustellen, nur einmal angezeigt wird, können Sie entweder das Ergebnis filtern, oder Sie können ein bisschen hackish sein und halten eine „besuchten“ Bit an jeder Kante Sie, um sicherzustellen, kleben es im Ergebnis nicht zweimal.

Wie soll ich stelle die Ergebnisse?

Was die Art und Weise ankommt, über ich das Ergebnis verwenden?

Wenn Sie vorhaben, das Ergebnis in einer rechenintensive Berechnung zu verwenden, eine große Reihe von Koordinaten kann die beste Option sein. Sie wollen nicht die Knotenkoordinaten über und über während der Berechnung neu zu holen. Wenn Sie jedoch die Ergebnisse sind Filterung doppelte Kanten zu entfernen, Koordinaten (6 Doppelzimmer für ein Knotenpaar) zu vergleichen ist nicht der Weg zu gehen. Wenn Sie filtern, zunächst eine Liste von Zeigern auf Kantenstrukturen erzeugen, dann Duplikate herauszufiltern, und und Generieren Sie Ihre Liste von Koordinaten. Sie könnten diesen Ansatz mit Knotenpaare verwenden auch, aber dann müssen Sie Filter gegen beide möglichen Knoten Aufträge pro Kante, die Höhe der Zeit zu verdoppeln, um Filter nimmt.

Eine Liste von Kanten-Zeiger ist auch der Weg zu gehen, wenn der Speicher mehr als Leistung zählt. Statt Ihre Kantenliste zu einer Koordinatenliste konvertieren, aber schauen Sie Koordinaten während der Berechnung auf. Knotenkoordinaten immer langsamer auf diese Weise, aber Sie vermeiden eine massive Liste von Koordinaten zu machen -. Sie speichern einen einzelnen Zeiger pro Kante statt 6 Doppelzimmer pro Kante

Viele mesh Anwendungen speichern alle Koordinaten in einem großen globalen Array, wobei jeder Knoten einen Index in dem Array aufweist. Wenn dies der Fall ist, anstatt Ihre Kantenliste auf einen Koordinaten Array umzuwandeln, wandelt es in eine Liste von Indizes in das globale Array koordinieren. Leistung sollte nicht viel weg von einem lokalen KoordinatenAnordnung, aber ohne den Speicher und Bevölkerung Overhead.

Ich habe keine Algorithmen für Sie, aber ich kann Ihnen sagen, wo sie suchen müssen.

"Punkt Set Triangulation" ist das, was Sie suchen.

Hier sind einige Open-Source-Bibliotheken, die diese (für Algorithmen grok den Code) wird dies für Sie:

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top