Диаграмма Вороного, триангуляция Делоне - структуры данных

Я хочу вычислить Вороного и его двойственную триангуляцию Делоне. Я использую алгоритм Уотсона Бойера. Моя цель - вычислить альфа-формы (вогнутые корпуса). Поэтому мне нужно будет быстро получить доступ к ячейке вороной для данной точки, соседям ...

Какие структуры данных вы использовали для своего алгоритма Вороного / Делоне? Я думал об использовании непересекающейся структуры данных множества с операциями поиска объединения, чтобы я мог «связать»; одному из родителей точка p в исходном наборе данных, точка множества в Vp. Однако одна точка на диаграмме Вороного "принадлежит". в несколько клеток Вороного.

Каков ваш совет, или вы могли бы намекнуть на какую-нибудь хорошую ссылку?

С уважением.

Ответы на вопрос(1)

Решение Вопроса

http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml

Половинная структура данных используется во многих приложениях и средах. Одна реализация этого найдена в структуре GEL:

http://www2.imm.dtu.dk/projects/GEL/

 octoback08 сент. 2012 г., 21:05
Спасибо! Существуют ли более простые альтернативы, чем хранение структуры данных на одной и той же временной грани, следующем ребре, следующей вершине?
 octoback08 сент. 2012 г., 21:08
Вы знаете какую-то реализацию этого на Python? Благодарю.
 09 сент. 2012 г., 10:27
Я не знаю каких-либо более простых решений. Я также не знаю никакой реализации Python, но код должен быть довольно легко портировать на Python.
 10 сент. 2012 г., 08:22
Если вы хотите использовать что-то уже работающее,cgal-bindings Проект предоставляет оболочку Python вокруг реализации альфа-формыCGAL.

Ваш ответ на вопрос