Я собираюсь реализовать алгоритм наивного графика видимости (т.е. время выполнения O (n ^ 3)), но столкнулся с несколькими проблемами.Мой подход заключается в следующем:
- Дано: массив полигонов (представлен массивом [x, y] вершин)
- Создать дополнительный массив всех ребер в многоугольниках
- "Выровнять" массив полигонов в массив из просто вершин
- Зациклить все возможные уникальные пары вершин (v1, v2)
- Зациклить все ребра
- Имеетпрямая видимости = истина
- Если отрезок линии от v1 до v2 пересекает / пересекает край, то имеет прямую видимость = ложь
- Если имеет прямую видимость = истина, то естьвидимый путь от v1 до v2 (то есть v1 может «видеть» v2)
Чтобы проверить, пересекаются ли два сегмента, я реализовал алгоритм, изложенный здесь: https://martin -thoma.com / как проверить-если-два-отрезка-линии-пересекаются /
У меня две основные проблемы:
- Vertex nдолжен быть подключен к n + 1 и n-1.Однако этот алгоритм предотвращает это, потому что считает, что ребро n пересекает ребро n + 1, потому что у них общая вершина:
- Если я изменю алгоритм, чтобы предотвратить только ребра, которыепересекают друг друга (то есть те, где нет коллинеарных точек / ребер, которые разделяют вершину), тогда он считает, что линии, проходящие через многоугольник, действительны:
Есть какие-нибудь предложения относительно того, как я мог бы настроить свой метод для вычисления графа видимости из набора непересекающихся вершин?Было бы лучше проверить, проходит ли многоугольник от до многоугольника, в отличие от пересечения ребер?
Примечание: я ищу реализацию наивного графика видимости;Я знаю, что есть метод O (n ^ 2 log (n)), который используется чаще, но я ищу простоту.