Es gibt wirklich drei Teile auf Ihre Frage, nicht zwei:
- Welche Datenstrukturen sollten verwendet werden, um das Netz darzustellen?
- Welchen Algorithmus sollte ich verwenden, um Kanten aus den Netzdatenstrukturen zu extrahieren?
- Wie sollte der resultierende Kantensatz dargestellt werden?
Sie müssen zusätzliche Fragen stellen, um passende Antworten zu finden.
Welche Datenstrukturen sollten zur Darstellung des Netzes verwendet werden?
Welche Elementtypen müssen Sie handhaben?
Wenn Sie nur Polygone (geschlossene Schleifen) und Simplicials behandeln müssen (jeder Knoten ist mit jedem anderen Knoten im Element verbunden, z. B. einem Tetraeder), dann ist eine geordnete Knotenliste ausreichend, da Kanten von der Liste der Knoten. Wenn Sie andererseits mit Elementtypen wie Hexaedern, Prismen oder allgemeinen Polyedern umgehen müssen, benötigen Sie weitere Informationen zur Elementtopologie. Eine einfache Anordnung von Kantenzuordnungen ist oft ausreichend. Es ist nur ein Array [] [2] von Indizes in der Knotenliste des Elements, das Ihnen sagt, wie Sie die Punkte für einen gegebenen Elementtyp verbinden.
Die von Chris beschriebene Halbkantenstruktur ist eine gute Wahl nur für 2D. In 3D kann eine beliebige Anzahl von Elementen an jeder Kante angebracht sein, nicht nur zwei. Es gibt eine 3D-Erweiterung für die Half-Edge-Darstellung, die ich als Pinwheel-Struktur bezeichne.
Wenn Sie willkürliche Elementtypen unterstützen müssen, bevorzuge ich eine vollständigere Datenstruktur, um die Elementtopologie darzustellen. Eine gängige Option ist die Verwendung von Kanten und Kanten. Es gibt eine Kantenstruktur für jedes Paar verbundener Knoten und eine Nebenkante für jede Verwendung dieser Kante in einem Element. Es ist ähnlich wie bei der Nadelradmethode, aber etwas expliziter.
Welchen Algorithmus soll ich verwenden, um Kanten aus den Elementen zu extrahieren?
Wie wichtig ist Geschwindigkeit oder Speicher? Sollte das Ergebnis jede Kante einmal pro Element oder nur einmal enthalten, egal wie viele Elemente es verwenden? Kommt es auf die Reihenfolge der Kanten im Ergebnis an? Ist die Reihenfolge der Knoten jeder Kante wichtig?
Es ist ziemlich schwierig, einen Algorithmus für beliebige Elementtypen zu finden, der nur einmal jede Kante besucht. Um sicherzustellen, dass jede Kante nur einmal angezeigt wird, können Sie entweder das Ergebnis filtern, oder Sie können ein bisschen hackisch sein und ein "besuchtes" Bit an jeder Kante behalten, um sicherzustellen, dass Sie es nicht zweimal im Ergebnis festhalten.
Wie soll ich die Ergebnisse darstellen?
Was ist wichtig, wie ich das Ergebnis verwenden werde?
Wenn Sie das Ergebnis in einer rechenintensiven Berechnung verwenden, ist möglicherweise eine große Anzahl von Koordinaten die beste Option. Sie möchten die Knotenkoordinaten während Ihrer Berechnung nicht immer wieder abrufen. Wenn Sie jedoch die Ergebnisse filtern, um doppelte Kanten zu entfernen, ist der Vergleich von Koordinaten (6 Doppelpunkte für ein Knotenpaar) nicht der richtige Weg. Wenn Sie filtern, generieren Sie zuerst eine Liste mit Zeigern zu Kantenstrukturen, dann filtern Sie die Duplikate heraus, und dann generieren Sie Ihre Koordinatenliste. Sie können diesen Ansatz auch mit Knotenpaaren verwenden, aber dann müssen Sie für beide möglichen Knotenreihenfolgen pro Kante filtern, um die Zeit zu verdoppeln, die zum Filtern benötigt wird.
Eine Liste der Kantenzeiger ist auch der Weg zu gehen, wenn Speicher mehr als Leistung zählt. Anstatt Ihre Kantenliste in eine Koordinatenliste zu konvertieren, suchen Sie jedoch während der Berechnung nach Koordinaten. Knotenkoordinaten zu erhalten, ist auf diese Weise langsamer, aber Sie vermeiden es, eine riesige Liste von Koordinaten zu erstellen - Sie speichern einen einzelnen Zeiger pro Kante anstelle von 6 Doppelpunkten pro Kante.
Viele Netzanwendungen speichern alle Koordinaten in einem großen globalen Array, wobei jeder Knoten einen Index in das Array hat. Wenn dies der Fall ist, wandeln Sie Ihre Kantenliste in ein Koordinatenfeld um, indem Sie sie in eine Liste von Indizes in das globale Koordinatenfeld konvertieren. Die Leistung sollte von einem lokalen Koordinaten-Array nicht viel abweichen, aber ohne den Speicher- und Populations-Overhead.
