Рубрика «алгоритм Форчуна»

image

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


Пространственные отношения

Пространственное отношение — это любая информация, описывающая, как связан один объект в пространстве с другим. Примеры: расстояние между ними, площадь покрываемого каждым из них пространства и пересечение этих площадей, количество таких объектов, расположенных в одной области.

Такие отношения постоянно используются в видеоиграх и могут предоставлять очень полезную информацию ИИ, а также самому игроку.


У Вороного есть ответ

Диаграмма Вороного описывает пространственное отношение между близко расположенными точками или их их ближайшими соседями. Это множество соединённых многоугольников, полученных из точек или локаций. Каждая линия «области» Вороного находится посередине между двумя точками.
Читать полностью »

Последние несколько недель я работал над реализацией алгоритма Форчуна на C++. Этот алгоритм берёт множество 2D-точек и строит из них диаграмму Вороного. Если вы не знаете, что такое диаграмма Вороного, то взгляните на рисунок:

Алгоритм Форчуна, подробности реализации - 1

Для каждой входной точки, которая называется «местом» (site), нам нужно найти множество точек, которые ближе к этому месту, чем ко всем остальным. Такие множества точек образуют ячейки, которые показаны на изображении выше.

В алгоритме Форчуна примечательно то, что он строит такие диаграммы за время $O(nlog n)$ (что оптимально для использующего сравнения алгоритма), где $n$ — это количество мест.

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

Как обычно, код выложен на github, а все использованные мной справочные материалы перечислены в конце статьи.
Читать полностью »

Приветствую, уважаемые читатели данной статьи! В статье я дам описание имплементации алгоритма Форчуна (англ. Fortune's algorithm) для построения диаграммы Вороного (англ. Voronoi diagram) с использованием нативных сбалансированных двоичных деревьев поиска (для уникальных элементов) (англ. BST, binary search tree), предусмотренных стандартом C++, — ассоциативных упорядоченных контейнеров std::map и std::set.

Читать полностью »

Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за Диаграмма Вороного и её применения - 1, Диаграмма Вороного и её применения - 2 — пересечение полуплоскостей, Диаграмма Вороного и её применения - 3 — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).

Диаграмма Вороного и её применения - 4

Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js