Путать с алгоритмом диаграммы Вороного (линия фортуны)

Question

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

Проблема в том, что я действительно запутался в этом алгоритме. Я прочитал книгу «Вычислительная геометрия», еще немного теорий об алгоритме Фортуны. И я действительно смущен сейчас. Мне кажется очень сложным, когда я собираюсь кодировать.

Пожалуйста, посоветуйте мне очень простую реализацию диаграммы Вороного (с заданными координатами). Посоветуйте, пожалуйста, простой код Java, Python или код схемы, желательно без хеша, многопоточности, трейнинга Делоне, необычных цветов и т. Д.

Разве невозможно реализовать диаграмму Вороного, используя алгоритм Fortune, без многопоточности или хэш-карты?

Answer 1

Я открыл репозиторий github с портом оригинальной бумаги Fortune. Реализация Fortune была очень сложной, в основном из-за того, как он обрабатывал структуры данных.

Эта книга выглядит намного более современной

Оригинальная статья Фортуны требует нескольких чтений.

В статье Кена Вонга описан алгоритм, возможно, с большей ясностью, чем в Fortune в оригинальной статье

В презентации Кена Вонга есть отличные слайды (10, 11) о том, как обрабатывать сайт и вершину

Существует интерактивная демонстрация JavaScript ( Архивная версия ), которую вы можете посмотреть, чтобы помочь вам визуализировать алгоритм.

A pdf также описывает алгоритм.

Оригинальная реализация Стивена Фортуна находится на его домашней странице .

На этом сайте Stony Brook перечислены другие реализации

Треугольник - это «Двумерный качественный генератор сетки и триангулятор Делоне».

На диаграммах Вороного есть вся книга

Answer 2

Это кажется сложным, потому что это сложно! Вам не нужны хеш-таблица или потоки, но вам понадобится очередь с приоритетами (обычно реализованная в виде кучи и доступная как в стандартных библиотеках java, так и в python) и дерево, которое позволяет выполнять запросы диапазона в O (log n) (те, что в стандартных библиотеках, на самом деле не подходят, потому что вы не можете получить их внутренности; я бы предложил реализовать дерево AA ). И сам алгоритм все еще довольно волосатый.

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

Answer 3

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

Answer 4

Очевидно, что алгоритм Фортуны не является тривиальным для реализации. Особенно, если вы рассматриваете проблемы числовой надежности график времени. Вы не говорите, какой язык программирования вы хотите использовать для его реализации. В случае, если это C ++, вы можете найти работу Андрея Сидорчука для Boost в рамках проекта GSoC 2010 : Алгоритм Sweepline . Реализация Андрея основана на библиотеке Boost.Polygon . И реализация Вороного, и Boost.Polygon полагаются на целочисленные координаты, чтобы обеспечить числовую устойчивость.

Видеолекция BoostCon по Алгоритм развертки для диаграмм точек Вороного, отрезков линий и средней оси многоугольников на плоскости дает очень хорошее объяснение идеи, проблем и подводных камней.

Довольно много обсуждений, связанных с этим проектом Вороного. произошло в списке рассылки Boost в 2010/2011 годах.

Answer 5

Вот еще одна реализация в Ruby и C, включая визуализацию:

http://github.com/abscondment/rubyvor/

Answer 6

В прошлом году я довольно много смотрел на диаграммы Вороного, и я, безусловно, могу оценить путаницу. Существует несколько реализаций алгоритмов генерации диаграмм Вороного. Смотрите эту страницу для пары, а также здесь . Как уже упоминалось, Qhull, безусловно, стоит посмотреть - MATLAB использует его для генерации диаграмм Вороного, триангуляций Делоне и подобных забавных вещей.