Ой, XML-сетки:).
Я на самом деле хорошо посмотрел на это, мой первый ответ был довольно ленивым. Вы можете писать лучше (как написано выше), и это не так сложно, я бы не стал платить 40 долларов за статью в журнале. Вот решение с псевдокодом, которое должно работать для вас.
Примечание: Когда я говорю «таблица», я имею в виду «справочную таблицу».
Предположим, что каждый треугольник пронумерован и состоит из вершин v1, v2, v3, которые имеют уникальную нумерацию и могут сравниваться с помощью оператора <(поэтому мы можем получить уникальные комбинации клавиш). </p>
Нам нужны две справочные таблицы:
- Таблица ребер -> (список треугольников) с именем edge_triangles.
- Таблица треугольников -> (список ребер) с именем triangle_edges.
Таблица, которая сообщает нам, какие треугольники используют данное ребро, а другая - нам, из каких ребер состоит данный треугольник. Мы строим эти списки следующим образом:
for t = next triangle
// Determine the ordering of vertices.
min_vertex = min(t.v1, t.v2, t.v3);
mid_vertex = median(p.v1, t.v2, t.v3);
max_vertex = max(t.v1, t.v2, t.v3);
// Register which edges this triangle uses.
edge_triangles[min_vertex][mid_vertex].append(t);
edge_triangles[mid_vertex][max_vertex].append(t);
edge_triangles[min_vertex][max_vertex].append(t);
// Set the edges that make up this triangle.
triangle_edges[t].append({min_vertex, mid_vertex});
triangle_edges[t].append({mid_vertex, max_vertex});
triangle_edges[t].append({min_vertex, max_vertex});
for next t
Используя эти списки, мы можем взять ребра в данном треугольнике, использовать их в качестве ключа в таблице ребер и посмотреть, какие многоугольники разделяют это ребро. Таким образом, соседние треугольники. Таким образом, для треугольника t мы могли бы сделать следующее:
adjacent = edge_faces[face_edges[t][0]];
, который является псевдокодом для «смежных», равен списку треугольников, которые разделяют 0-й край треугольника t ', где 0-й является только первым.
Мы используем min, median и max, чтобы убедиться, что у нас нет разных записей для одинаковых ребер: например, {v1, v2} и {v2, v1}, где v1 и v2 - две вершины. Мы могли бы фактически игнорировать это и добавить «компактный» шаг, где мы объединяем списки, которые соответствуют различным записям в нашем списке ребер, но фактически соответствуют одному и тому же ребру.
Еще одна возможная проблема с этим, если у вас есть два ребра, которые совпадают, но не имеют общих вершин. В этом случае вы можете уменьшить любое ребро до параметрического уравнения, сравнить их на совпадение и сформировать справочную таблицу, которая сообщит вам для данного ребра, какие ребра совпадают, поэтому отобразите:
- edge -> (список ребер) таблица с именем edge_coincident_edges.
Мы используем еще одну справочную таблицу, потому что мы не можем объединить таблицу ребер> граней. Косичнее, если ребра e1 и e2 смежны, e2 и e3 есть, а e1 и e3 нет. если мы объединим записи e1, e2 и e3 в списке edge-> face, у вас получатся дико неверные данные. Это, вероятно, немного больше, чем вы хотите сделать, но это проблема, которую я должен был решить сегодня утром:).
В случае, когда каждое ребро может соответствовать максимум 2 треугольникам, мы можем покончить со «списком» в традиционном смысле, который мы можем добавить, и использовать массив фиксированного размера размером 2. Это уменьшит ваши накладные расходы памяти и повысить эффективность памяти. так что наша таблица ребер будет больше похожа на:
- Таблица ребер -> (первый треугольник, второй треугольник) с именем edge_triangles.
В любом случае, базовый алгоритм расширяется на любое количество многоугольников с любым числом ребер (не обязательно одинаковое между всеми многоугольниками) и составляет O (N) время относительно количества треугольников (или многоугольников в общем случае). дело). Пространственная сложность O (E + N), где E - ребра, а N - количество многоугольников. Время поиска должно быть близко к O (1), при условии, что у вас есть хорошие алгоритмы хеширования.