Алгоритм уникального поиска ребер из полигональной сетки

Question

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

У меня есть версия, которая работает, но производительность снижается при достижении более 500 000 полисов. Моя версия проходит по каждому лицу и добавляет отсортированные вершины каждого ребра в stl :: set. Мой набор данных будет в основном из треугольников и четырехугольников, и большинство ребер будут общими.

Есть ли более разумный алгоритм для этого?

Answer 1

Да
Используйте двойную карту хеша.
Каждое ребро имеет два индекса A, B. допустим, что A> B.
Первая хеш-карта верхнего уровня отображает A на другую хеш-карту, которая, в свою очередь, отображает B на некоторое значение, которое представляет необходимую информацию о каждом ребре. (или просто bool, если вам не нужно хранить информацию для краев).
По сути, это создает двухуровневое дерево, состоящее из хеш-карт.

Чтобы найти ребро в этой структуре, вы берете больший индекс, ищите его на верхнем уровне и в итоге получаете хэш-карту. затем возьмите меньший индекс и найдите его на второй хэш-карте.

Answer 2

Просто, чтобы уточнить, вы хотите, для списка полигонов, как это:

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

Тогда вместо ребер вот так:

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

затем вы хотите удалить дубликаты B - C и C - B и поделиться им?

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

Answer 3

Вы оба правы. Использование хорошего хэш-набора позволило значительно повысить производительность. Я закончила свой собственный маленький хэш-сет.

Общее количество ребер будет между N / 2 и N. N - количество уникальных вершин в сетке. Все общие ребра будут N / 2, а все уникальные ребра будут равны N. Оттуда я выделяю буфер из uint64 и упаковываю свои индексы в эти значения. Используя небольшой набор уникальных таблиц, я могу быстро найти уникальные ребра!

Answer 4

Вот реализация C хэширования краев, используемая в Blender именно для быстрого создания граней из граней, может дать некоторые советы другим сделать их самостоятельно.

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

Это использует BLI_mempool, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h

Answer 5

Сначала вам нужно убедиться, что ваши вершины уникальны. Это если вы хотите только один край в определенной позиции. Тогда я использую эту структуру данных

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge содержит индексы вершин, которые составляют ребро в отсортированном порядке. Следовательно, если sampleEdge является ребром, составленным из вершин с номерами индексов 12 и 5, sampleEdge.first = 5 и sampleEdge.12

Тогда вы можете просто сделать

uniqueEdges[sampleEdge] = true;

для всех краев. uniqueEdges будет содержать все уникальные ребра.