Алгоритм однозначного поиска ребер из полигональной сетки
Я ищу хороший алгоритм, который может дать мне уникальные ребра из набора данных многоугольника. В этом случае многоугольники определяются двумя массивами. Один массив - это количество точек на многоугольник, а другой массив - это список индексов вершин.
У меня есть работающая версия, но производительность падает при достижении более 500 000 полигонов. Моя версия проходит по каждой грани и добавляет отсортированные вершины каждого ребра в stl :: set. Мой набор данных будет в основном состоять из треугольников и четырехугольников, и большинство ребер будут общими.
Есть ли для этого более умный алгоритм?
Ответы 5
Чтобы прояснить, вы хотите, чтобы список многоугольников был таким:
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 и поделиться ею?
Какие проблемы с производительностью вы наблюдаете у своего алгоритма? Я бы сказал, что набор с разумной реализацией хеширования должен работать нормально. С другой стороны, если ваш хеш не оптимален для данных, у вас будет много конфликтов, которые могут сильно повлиять на производительность.
Да
Используйте двойную хеш-карту.
Каждое ребро имеет два индекса A, B. допустим, что A> B.
Первая хэш-карта верхнего уровня сопоставляет A с другой хеш-картой, которая, в свою очередь, сопоставляет B с некоторым значением, которое представляет информацию, которую вы хотите получить о каждом ребре. (или просто bool, если вам не нужно хранить информацию для ребер) .
По сути, это создает двухуровневое дерево, состоящее из хэш-карт.
Чтобы найти край в этой структуре, вы берете индекс большего размера, просматриваете его на верхнем уровне и получаете хеш-карту. затем возьмите меньший индекс и найдите его на этой второй хэш-карте.
Вы оба правы. Использование хорошего хеш-набора позволило добиться производительности, значительно превышающей требуемый уровень. В итоге я скатал свой собственный маленький набор хешей.
Общее количество ребер будет от N / 2 до N. N - количество уникальных вершин в сетке. Все общие ребра будут N / 2, а все уникальные ребра будут N. Оттуда я выделяю буфер из uint64 и упаковываю свои индексы в эти значения. Используя небольшой набор уникальных таблиц, я могу быстро найти уникальные края!
Сначала вам нужно убедиться, что ваши вершины уникальны. Это если вам нужно только одно ребро в определенной позиции. Затем я использую эту структуру данных
typedef std::pair<int, int> Edge;
Edge sampleEdge;
std::map<Edge, bool> uniqueEdges;
Ребро содержит индексы вершин, составляющих ребро в отсортированном порядке. Следовательно, если sampleEdge - это ребро, составленное из вершин с номерами индексов 12 и 5, sampleEdge.first = 5 и sampleEdge.12.
Тогда ты можешь просто сделать
uniqueEdges[sampleEdge] = true;
для всех краев. uniqueEdges будет содержать все уникальные края.
Вот реализация C хеширования краев, используемая в Blender именно для быстрого создания краев из граней, может дать некоторые подсказки для других, чтобы они могли сделать свои собственные.
Это использует BLI_mempool, https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c
Если я правильно понимаю, вы получите уникальную хэш-карту первого уровня, но с большим количеством хэш-карт уровня 2 (по одной для каждого значения A). Интересно, действительно ли помогают хэш-карты уровня 2 °, достаточно ли значений B на этих вторых хэш-картах?