Сгенерируйте диаграмму Вороного без использования алгоритма Fortune

Я надеюсь создать пейзаж Вороного в Unity на С#. Я просмотрел несколько файлов проекта Unity, но все они реализуют алгоритм Fortune, который мне совершенно не по плечу. Существуют ли другие способы построения диаграммы Вороного (более простые для понимания)? Медленная работа меня вполне устраивает. Очень признателен!

Примечание: поскольку я работаю в Unity и мне нужно создать 2D/3D-сетку из диаграммы Вороного, проверка расстояния между пикселями не будет работать :,( Если подумать, возможно, я мог бы использовать 2D-массив Vector2 вместо пикселей, которые находятся на расстоянии 1,0 единицы друг от друга по осям x и z.


unity3d c# voronoi
person Komm    schedule 27.07.2017    source источник
comment
Так вам на самом деле нужна геометрически точная диаграмма Вороного или подойдет пиксельная аппроксимация, когда вы упоминаете ландшафт?   -  person gue    schedule 27.07.2017
comment
Приближение абсолютно нормально. Хотя было бы неплохо иметь данные вершин или ребер, чтобы я мог использовать их для создания меша. Спасибо, гэ!   -  person Komm    schedule 27.07.2017
comment
Возможный дубликат Самый простой алгоритм диаграммы Вороного для реализации?   -  person Gigamegs    schedule 27.07.2017

Ответы (2)


arrow_upward
2
arrow_downward

Существует очень простой способ создания аппроксимированной диаграммы Вороного VD. Для каждого сайта s, который должен определять ячейку в VD (2D-плоскость), вы центрируете конус в s с постоянным наклоном и определенной высотой. Затем вы смотрите сверху на этот пейзаж из шишек (где видны все шипы). Граница, где встречаются разные конусы (в проекции на 2D-плоскость), представляет собой (аппроксимированную) диаграмму Вороного.

введите здесь описание изображения

(Источник изображения )

Как вы просили в комментариях, получить фактические данные края кажется не так просто. Но могут быть некоторые графические подпрограммы для их генерации путем пересечения конусов.

Альтернативой является вычисление триангуляции Делоне заданного набора точек. В этом сообщении упоминается некоторая реализация (также упоминаются простые приближения). Затем вы вычисляете двойной граф своей триангуляции и получаете диаграмму Вороного. (Двойственный граф означает, что для каждого ребра AB в триангуляции существует ребро в ВД, делящее пополам пространство между двумя вершинами A и B, и для каждого треугольника существует вершина в ВД, где встречаются двойственные ребра.) В противном случае существует множество реализаций C# Вороного: Unity-delaunay, но, как вы упомянули, используя Подход Фортуны.

Если вы хотите закодировать все самостоятельно, вы можете вычислить триангуляцию точек с помощью грубой силы для n точек за O(n^2) времени. Затем примените круговые тесты и краевые сальто. То есть для каждого треугольника t(abc) создайте окружность C, определяемую тремя вершинами t. Затем проверьте, лежит ли другая точка d из набора точек внутри C. Если это так, то переверните ребро, которое находится в t, а также образует ребро в треугольнике с d. Это переворачивание выполняется до тех пор, пока все треугольники не удовлетворят свойству пустого круга (условию Делоне). Опять же с грубой силой займет O(n^2) времени. Затем вы можете вычислить двойной граф, как указано выше.

введите здесь описание изображения

(Источник изображения)

person gue    schedule 27.07.2017
comment
@gui: Вы кандидат наук? Вау! - person Gigamegs; 27.07.2017
comment
Идея состоит в том, чтобы просто разместить конусы, фактически не пересекая их. Затем можно использовать любой трассировщик лучей типа Blender и посмотреть сверху и сразу увидеть (человеческими глазами) ВД, так как он образован долинами между конусами. Тогда снизу вы увидите только плоскую поверхность. Получить реальный ВД из этого графического представления не так просто. - person gue; 27.07.2017

arrow_upward
1
arrow_downward

«Самый простой? Это подход грубой силы: для каждого пикселя в вашем выводе перебираем все точки, вычисляем расстояние, используем ближайшую. Медленно, как может быть, но очень просто. Если производительность не важна, он делает свою работу. "

[1] Самый простой алгоритм диаграммы Вороного для реализации?

person Gigamegs    schedule 27.07.2017
comment
Упомянутый алгоритм - Бойер-Ватсон, который не имеет ничего общего с приближением пикселей, которое вы описываете в ответе. - person gue; 27.07.2017
comment
@gue: О чем ты говоришь? Вы кандидат наук? Вау? - person Gigamegs; 27.07.2017
comment
Я не кандидат наук. Я вижу ошибку, ссылка, которую вы использовали, не та, которую вы цитируете, вы цитируете (stackoverflow.com/a/10848478/4462067), но на него ссылается (stackoverflow.com/questions/973094/). Отсюда и пошло мое замешательство. - person gue; 27.07.2017
comment
@gue: извините, исправлено. - person Gigamegs; 27.07.2017