Топология треугольной сетки - PullRequest
Новая
       13

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

2 голосов
/ 14 мая 2009

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

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

Очень благодарен, Дэвид Руттен

Ответы [ 2 ]

2 голосов
/ 17 сентября 2009

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

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

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

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

Вы должны подумать о том, чтобы погрузиться в одну из них.

0 голосов
/ 14 мая 2009

Мне кажется, я слепо смотрю на 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
...