Топология треугольной сетки

Question

У меня есть класс треугольной сетки, который содержит список узлов (в моем случае 2d, но это не имеет значения) и список граней.Каждая грань представляет собой треугольник и содержит только индексы массива узлов.Сетка создается на основе алгоритма Делоне, поэтому она очень чистая.

Для каждого узла сетки мне нужно найти, какие узлы соединены с ним одним ребром.Каким будет быстрый способ создания и поиска в этой базе данных топологии?

Обязан, Дэвид Руттен

Answer 1

Существуют две несколько стандартные структуры данных, которые облегчают запросы топологии сетки.Один Крылатые края (обычно называемый также полукрай), а другой Направленные края.Погуглите, и вы получите миллионы подробностей и вступления различного уровня к каждой из них.

Недостаточно знаний о вашем сценарии, чтобы рекомендовать один из них.Например, направленные края оптимизированы для хранения и лучше всего подходят для очень больших сеток.Крылатые края считаются «классикой» и являются хорошей отправной точкой для более продвинутых вкусов.

На самом деле, если вы уверены, что это единственный запрос, который вам понадобится, тогда оба являются излишними, и вы прекрасно справитесь с одним хешем.Однако если вам нужны эффективные ответы на такие вопросы, как -

• Какие грани используют эту вершину?
• Какие ребра используют эту вершину?
• Какие грани окаймляют этот край?
• Какие ребра окаймляют эту грань?
• Какие лица рядом с этим лицом?

Вам стоит подумать о погружении в один из них.

Answer 2

Кажется, я слепо смотрел на HashTables, словари и отсортированные списки...Следующее, вероятно, самое простое и быстрое:

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