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

Question

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

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

Премного, Дэвид Rutten

Answer 1

Есть две несколько стандартных структур данных, которые облегчают топологию-сетку. Один из них - Winged Edges (обычно называемый также half-edge), а другой - Directed Edges. Google вокруг, и вы получите кадзиллионы деталей, а также различные уровни в каждом из них.

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

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

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

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

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