Ой, XML мешает :).
Я на самом деле хорошо это рассмотрел, мой первый ответ был довольно ленивым. вы можете писать лучше (как написано выше), и это не так уж сложно, я бы не стал выкладывать 40 долларов за журнальную статью по этому поводу. Вот решение с псевдокодом, которое должно сработать для вас.
Примечание. Когда я говорю "таблица", я имею в виду "справочную таблицу".
Предположим, что каждый треугольник пронумерован и состоит из вершин v1, v2, v3, которые имеют уникальные номера и могут быть сравнены с помощью оператора ‹(чтобы мы могли получить уникальные комбинации клавиш).
Нам понадобятся две справочные таблицы:
- Таблица edge -> (список треугольников) с именем 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.
Мы используем еще одну справочную таблицу, потому что мы не можем объединить таблицу edge-> faces. Косидера, если ребра e1 и e2 смежны, e2 и e3 смежны, а e1 и e3 - нет. если бы мы объединили записи e1, e2 и e3 в списке edge-> face, вы получили бы некоторые совершенно неверные данные. Это, вероятно, немного больше, чем вы хотите сделать, но это проблема, которую я должен был решить сегодня утром :).
В случае, когда каждое ребро может соответствовать не более чем двум треугольникам, мы можем отказаться от «списка» в традиционном смысле, который мы можем добавить, и использовать массив фиксированного размера размером 2. Это уменьшит накладные расходы на память. и улучшить эффективность памяти. так что наша пограничная таблица будет больше похожа на:
- Таблица edge -> (первый треугольник, второй треугольник) с именем edge_triangles.
В любом случае, базовый алгоритм может быть расширен до любого числа многоугольников с любым числом ребер (не обязательно одинаковым для всех многоугольников), и это время O (N) относительно числа треугольников (или многоугольников в общем случае). Сложность пространства - O (E + N), где E - ребра, а N - количество многоугольников. Время поиска должно быть близко к O (1), если у вас есть хорошие алгоритмы хеширования.
person
Liam M
schedule
13.01.2012
