삼각형 메쉬 토폴로지

Question

노드 목록 (내 경우 2D이지만 중요하지 않음)과 얼굴 목록이 포함 된 삼각형 메쉬 클래스가 있습니다. 각면은 삼각형이며 노드 어레이에 인덱스 만 포함되어 있습니다. 메쉬는 Delaunay 알고리즘에서 나오므로 매우 깨끗합니다.

메쉬의 모든 노드에 대해 단일 모서리로 연결되는 노드를 찾아야합니다. 이 토폴로지 데이터베이스를 구성하고 검색하는 빠른 방법은 무엇입니까?

많은 의무가 있습니다. David Rutten

Answer 1

메쉬 토폴로지 쿼리를 용이하게하는 두 가지 다소 표준 데이터 스트러크가 있습니다. 하나는 날개 달린 가장자리 (일반적으로 또한) 반쪽), 다른 하나는입니다 지시 된 가장자리. Google은 주변에 있으며 여러 가지 세부 정보를 얻을 수 있으며 각각의 다양한 수준의 소개를 얻을 수 있습니다.

당신의 시나리오에 대해 충분히 알지 못하면 그들 중 하나를 추천합니다. 예를 들어, Directed Edges는 저장 최적화되어 있으며 매우 큰 메쉬에 가장 적합합니다. 날개 달린 가장자리는 '클래식'으로 간주되며 고급 향이 더 좋은 출발점입니다.

실제로 그것이 당신이 필요한 유일한 쿼리라고 확신한다면, 둘 다 과잉이며 단일 해시로 잘할 것입니다. 그러나, 당신은 다음과 같은 쿼리에 대한 효율적인 답변이 필요한 경우 -

• 이 정점을 사용하는 얼굴은 어느 얼굴입니까?
• 이 정점을 사용하는 가장자리는 무엇입니까?
• 어느 얼굴 이이 가장자리에 국경을 맞추고 있습니까?
• 어떤 가장자리 가이 얼굴에 경계를 보이나요?
• 이 얼굴에 어떤 얼굴이 인접 해 있습니까?

당신은 그들 중 하나에 다이빙을 고려해야합니다.

Answer 2

나는 내가 해시블, 사전 및 분류 된 목록에 대해 맹인을 쳐다 보았다고 생각합니다 ... 다음은 아마도 가장 쉽고 빠릅니다.

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