Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Построение графа видимости

Построение графа видимости

Поделиться
NXTaarПостоялецwww5 апр. 20170:02#0
Здравствуйте.

Имеется произвольный несамопересекающийся многоугольник, внутри которого могут быть другие многоугольники "препятствия".
Чтобы было удобнее объяснять вот фигура для примера
polygon_example | Построение графа видимости

Нужно построить для выпуклых точек (подсвеченных зеленым) граф видимости.
Для этого есть специальный алгоритм, с помощью заметающей прямой.

Описание алгоритма раз (ru) раздел "Lee’s Algorithm"
Описание алгоритма два (ru) раздел "Граф видимости"
Описание алгоритма три (en)
Описание алгоритма четыре (en)

Мне понятен общий принцип работы алгоритма, но меня приводит в замешательтво как применить его именно на многоугольниках, а конкретно 2 момента.

Момент первый.
Во всех описаниях алгоритма рассматривается ситуация, в которой точка, для которой проверяется видимость других точек, лежит вне многоугольников-препятствий в пустом пространстве. В моем же случае каждая точка для которой проверяется видимость, одновременно является и вершиной по которой судя по описанию в алгоритме, должна пройти заметающая прямая.
Если на примере.
Допустим мы ищем видимые точки для вершины номер 4. Белым определены фигуры-препятствия (в результате оптимизации по выпуклым вершинам)


1. В описаниях алгоритма сказано - в стадии инициализации проведите из проверяемой точки луч, параллельный оси координат, и занесите в структуру отрезки, которые он пересекает в порядке удаленности точки пересечения от проверяемой точки.
Если у нас из искомой точки исходят 2 отрезка, считается что луч их пересекает?
2. В описании сказано - "Отсортируйте вершины по углу который они образуют между осью x (или y, неважно можно и от той, и от той) и отрезком проведенным от проверяемой точки к вершине"
Т.к. у нас точка 4 одновременно является и вершиной, должна ли она быть в этом списке отсортированных, или этот список составляется без нее? И если должна то с каким углом? 0°?
3. Из первого вопроса выходит второй. Если точка должна быть в списке вершин, то когда в нее приходит заметающая прямая, как она должна себя вести?
4. Допустим заметающая прямая приходит в вершину 9.
Будет ли считаться что она пересекается с отрезком 4-9?
Или наоборот не пересекается. В описании алгоритма сказано что надо работать с отрезками "слева" от заметающей прямой, и "справа".
А где относительно заметающей прямой, в таком случае будет отрезок 4-9, если он по сути будет равен заметающей прямой, т.к. она всегда исходит из точки 4?
Очень непонятно, как мне действовать в этой ситуации


Момент второй.
Все в тех же описаниях алгоритмов рассматривается ситуация что препятствия находятся у нас в некоем прямоугольнике, и у него нет ломанных сторон.
Допустим если мы точку 3 трактуем как в описании алгоритма, то непонятно как заметающая прямая из нее должна взаимодействовать с точками 0,1 и 2. И вообще, может 1-2 это должен быть отрезок?


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

Правка: 5 апр. 2017 13:10

/ Форум / Программирование игр / Игровая логика и ИИ

2001—2017 © GameDev.ru — Разработка игр