Dreiecks-Mesh-Topologie

Question

Ich habe ein Dreiecksnetz Klasse bekam, die eine Liste von Knoten (2d in meinem Fall, aber das sollte keine Rolle spielen) enthält und eine Liste von Gesichtern. Jede Fläche ein Dreieck ist, und es enthält nur die Indizes in den Knoten-Array. Das Netz kommt aus einem Delaunay-Algorithmus so ist es sehr sauber.

Für jeden Knoten in dem Netz muss ich feststellen, welche Knoten verbunden sind, um es mit einer einzigen Kante. Was für eine schnelle Möglichkeit, diese Topologie-Datenbank zu konstruieren und suchen sein?

Viel verpflichtet, David Rutten

Answer 1

Es gibt zwei etwas üblichen Daten structs, die Mesh-Topologie-Abfragen erleichtern. Man ist Winged Kanten (häufig auch bezeichnet als Halbrand ), und der andere ist Kanten Regie. Google um, und Sie würden kajillions von Details und verschiedene Ebene Intros in jedem erhalten.

Sie wissen nicht genug über Ihr Szenario einen von ihnen zu empfehlen. Z. B. gerichtete Kanten sind speicheroptimierte und am besten geeignet für sehr große Maschen. Geflügelten Kanten gilt als eine ‚klassische‘ und ist ein guter Ausgangspunkt für fortgeschrittenere Aromen.

Eigentlich, wenn Sie sicher sind, dass die einzige Abfrage ist müssten Sie, dann sind beide zuviel des Guten, und Sie würden mit einem einzigen Hash nur gut tun. Wenn jedoch finden Sie sich in der Notwendigkeit einer effizienten Antworten auf Anfragen wie -

• Welche dieser Eckpunkt steht benutzen?
• Welche diesen Vertex Kanten verwenden?
• Welche Grenze dieser Randflächen?
• Welche Grenze dieses Gesicht Kanten?
• Welche sind neben dieser Gesichter Gesicht?

Sie sollten Tauchen in einem von ihnen betrachten.

Answer 2

Ich glaube, ich habe starrte mich blinder auf HashTables, Wörterbücher und sortierte Listen ... Das folgende ist wahrscheinlich die einfachste und schnellste:

Public Sub SolveConnectivity(ByVal nodes As Node2List, ByVal faces As List(Of Face))
  m_map = New List(Of List(Of Int32))(nodes.Count)

  'Create blank lists
  For i As Int32 = 0 To nodes.Count - 1
    m_map.Add(New List(Of Int32)(6))
  Next

  'Populate connectivity diagram
  For i As Int32 = 0 To faces.Count - 1
    Dim F As Face = faces(i)
    m_map(F.A).Add(F.B)
    m_map(F.A).Add(F.C)

    m_map(F.B).Add(F.A)
    m_map(F.B).Add(F.C)

    m_map(F.C).Add(F.A)
    m_map(F.C).Add(F.B)
  Next
End Sub