Самый легкий алгоритм Диаграммы Вороного для реализации? [закрытый]
Чрезмерная инженерия означает разработку и проектирование приложения с большим количеством компонентов, чем это должно быть в действительности согласно списку требований.
Существует большая разница между чрезмерной разработкой и созданием расширяемого приложения, которое может быть обновлено по мере изменения требований. Если я могу привести пример, я отредактирую пост.
3 ответа
Простой алгоритм для вычисления триангуляции Делоне набора точек - это перевернутые края . Поскольку триангуляция Делоне является двойственным графом диаграммы Вороного, вы можете построить диаграмму из триангуляции за линейное время.
К сожалению, время работы метода переворота в худшем случае составляет O (n ^ 2). Существуют лучшие алгоритмы, такие как строчная развертка Fortune, которые занимают время O (n log n). Однако реализовать это довольно сложно. Если вы ленивы (как и я), я бы посоветовал поискать существующую реализацию триангуляции Делоне, использовать ее, а затем вычислить двойственный граф.
В общем, хорошая книга по этой теме - Вычислительная геометрия де Берга и др.
Существует свободно доступная реализация voronoi для двумерных графов на C и в C ++ от Стефана Фортуна / Шейна О'Салливана:
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
Вы найдете его во многих местах. Т.е. на http://www.skynet.ie/~sos/masters/
Страница Википедии ( http://en.wikipedia.org/wiki/Voronoi_diagram ) есть раздел «Алгоритмы» со ссылками на алгоритмы для реализации диаграмм Вороного.