Алгоритмы
Математика
Разработка игр
Комментарии 13
+1
Спасибо за статью. Именно ёё мне не хватало года 4 назад, когда хотел написать свой клон Космических Рейнджеров.
0
Прилично. Мне понравилось. Спасибо большое.
Ещё из похожей геометрии мне очень нравилсь триангуляция Делоне. Очень красиво получается, когда при добавлении точки перестраивается почти вся сеть.
+2
Так Делоне обычно с помощью Форчуна и делают (если речь о произвольных точках).
Если нужна просто сетка — то там есть и другие способы.
0
Дело было больше чем 25 лет назад. Не помню какой был алгоритм. Думаю, что придумывал что-то своё. Помню только — на С++, и что это был итерационный процесс. Ещё помню — очень нравилась визуализация процесса — как сеть перестраивается шаг за шагом… А потом стал искать — как добавить точку так, чтобы максимизировать количество перестановок рёбер… В общем — как-то так. Ничего уже не помню, кроме того, что выглядел этот процесс красиво (с моей точки зрения).
0
А не знает ли кто-нибудь адекватного способо построения сетки на торе? В смысле — циклически замкнутой?
А то ничего умнее построения сети с дублированием точек с противоположного края и последующим их пересоединением так и не придумал. В принципе метод работает, но напрягает непредсказуемое количество доп. точек. И их количество. Когда сама сеть имеет многие десятки тыс. точек то дополнение даёт ещё похожий порядок.
0
Взглянув на картинку (прочитав только условие), подумал, что графически это можно решать так: Строим воображаемую линию от места до места, находим середину, рисуем перпендикуляр. Ячейки будут образовываться пересечением этих перпендикуляров. (потом подумал что это же медианы треугольников с вершинами в местах)

Алгоритм же использует совсем другой подход. Очень интересно. Спасибо.
0
upd. Конечно же это не медианы, а серединные перпендикуляры.
Пересечение которых даёт — центр описанной окружности — а значит равное расстояние до вершин.
(Вспоминать школу — тоже, оказывается, интересно)
0

По сути алгоритм использует тот же самый подход. Вся сложность — в том, как выбрать нужные срединные перпендикуляры среди N2 возможных

0

В boost есть хорошая реализация диаграмы Вороного. Причем не только для точек, но и для отрезков.

0
На счёт точно равной ничего не скажу, но примерно равную можно получить прогнав несколько (2..3 минимум) проходов релаксации. Собственно обычно так и делают.
0
Недавно увидел на дороге очень выразительную трещину на асфальте.
image
Задумался о ней, как о динамической системе: все эти напряжения в материале, разрывы, их направления и изгибы, где-то ближе, где-то дальше. А результат даже композиционно эстетичен. Стало интересно — смогу ли я смоделировать правдоподобно выглядящую трещину. В итоге пришёл к выводу что оптимально для этого подойдёт именно диаграма Вороного. Но посмотрев на алгоритмы её построения, отложил это развлечение в долгий ящик.
Только полноправные пользователи могут оставлять комментарии. , пожалуйста.