Как мне получить диаграмму Вороного, учитывая ее набор точек и ее триангуляцию Делоне?
Я работаю над игрой, в которой я создаю случайную карту провинций (а-ля Риск или Дипломатия). Чтобы создать эту карту, я сначала генерирую серию полуслучайных точек, а затем вычисляю триангуляции Делоне этих точек.
После этого я собираюсь создать диаграмму Вороного точек, которая будет служить отправной точкой для границ провинции. Мои данные на данный момент (без каламбура) состоят из исходной серии точек и набора треугольников Делоне.
Я видел несколько способов сделать это в сети, но большинство из них связано с тем, как был получен Delaunay. Я бы хотел найти что-то, что не нужно интегрировать в Delaunay, но может работать только на основе данных. В противном случае я ищу что-то понятное для новичка в относительной геометрии, в отличие от оптимальной скорости. Спасибо!
Ответы 4
Диаграмма Вороного - это просто двойственный граф триангуляции Делоне.
- Итак, ребра диаграммы Вороного расположены вдоль серединных перпендикуляров ребер триангуляции Делоне, поэтому вычислите эти прямые.
- Затем вычислите вершины диаграммы Вороного, найдя пересечения смежных ребер.
- Наконец, ребра - это подмножества вычисленных вами линий, которые лежат между соответствующими вершинами.
Обратите внимание, что точный код зависит от внутреннего представления, которое вы используете для двух диаграмм.
Как было предложено в приведенном выше комментарии, я бы сделал это в два этапа: 1. Вычислите центр описанной окружности каждого треугольника Делоне -> это вершины Вороного. См. en.wikipedia.org/wiki/… 2. Для каждого ребра Делоне вычислите ребро Вороного: сегмент, соединяющий центры описанных окружностей двух соседних треугольников Делоне.
@ balint.miklos Что делать с внешними участками / треугольниками?
Если оптимальная скорость не рассматривается, следующий псевдокод сгенерирует диаграмму Вороного сложным путем:
for yloop = 0 to height-1
for xloop = 0 to width-1
// Generate maximal value
closest_distance = width * height
for point = 0 to number_of_points-1
// calls function to calc distance
point_distance = distance(point, xloop, yloop)
if point_distance < closest_distance
closest_point = point
end if
next
// place result in array of point types
points[xloop, yloop] = point
next
next
Предполагая, что у вас есть «точечный» класс или структура, если вы назначите им случайные цвета, вы увидите знакомый узор вороного при отображении вывода.
Все это красиво и модно, но я не вижу никакого смысла в диаграмме Вороного, созданной как изображение. Может есть такой?
Не как изображение как таковое, но я использовал его для процедурной генерации мира на основе тайлов (где каждый тайл определяется ячейкой, к которой он принадлежит).
Каждый из ваших треугольников Делоне содержит одну точку диаграммы Вороного.
Вы можете вычислить эту точку, найдя пересечение трех перпендикулярные биссектрисы для каждого треугольника.
Ваша диаграмма Вороного соединит этот набор точек, каждая с тремя ближайшими соседями. (у каждого соседа одна сторона треугольника Делоне)
Как вы планируете подходить к крайним случаям?
Обратите внимание, что хотя каждому треугольнику Делоне соответствует одна вершина Вороного, эта вершина также может быть вне треугольника. см. пример здесь: mathopenref.com/trianglecircumcenter.html
Попытавшись использовать эту ветку в качестве источника ответов на мой аналогичный вопрос, я обнаружил, что алгоритм Фортуны - вероятно, потому, что он самый популярный и, следовательно, наиболее документированный - был самым простым для понимания.
Статья в Википедии об алгоритме Фортуны хранит свежие ссылки на исходный код на C, C# и Javascript. Все они были первоклассными и сопровождались прекрасными примерами.
Вы также можете найти двойственную (т.е. диаграмму Вороного), просто вычислив центры описанных окружностей всех треугольников и соединив любые два центра описанных окружностей, треугольники которых имеют одно ребро.