У меня есть класс треугольной сетки, который содержит список узлов (в моем случае 2d, но это не имеет значения) и список граней. Каждая грань представляет собой треугольник и содержит только индексы в массиве узлов. Сетка получается из алгоритма Делоне, поэтому она очень чистая.
Для каждого узла в сетке мне нужно найти, какие узлы соединены с ним одним ребром. Каким может быть быстрый способ построения и поиска в этой базе данных топологии?
Премного благодарен, Дэвид Руттен
Есть две несколько стандартные структуры данных, которые облегчают запросы топологии сетки. Одним из них является Winged Edges (обычно также называемый half-edge), а другой — Направленные ребра. Погуглите, и вы получите миллион подробностей и вступительные ролики разного уровня для каждого из них.
Недостаточно знаю о вашем сценарии, чтобы рекомендовать один из них. Например, направленные ребра оптимизированы для хранения и лучше всего подходят для очень больших сеток. Крылатые края считаются «классикой» и являются хорошей отправной точкой для более продвинутых вкусов.
На самом деле, если вы уверены, что это единственный запрос, который вам нужен, то оба являются излишними, и вы прекрасно справитесь с одним хэшем. Если, однако, вам нужны эффективные ответы на такие вопросы, как -
Вы должны рассмотреть возможность погружения в один из них.
Я думаю, что я смотрел на себя вслепую на 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
