Вычислить график видимости на сфере

9

У меня есть таблица PostGIS с некоторыми полигонами (хранится с использованием типа данных географии). Они представляют регионы на сферической земле.

Для каждой пары вершин, выбранных из всех многоугольников, я хочу вычислить, являются ли эти две вершины «видимыми» друг другу. (Существует n * ( n -1) / 2 таких пар, где n - общее количество уникальных вершин во всех многоугольниках в таблице.) Под «видимыми друг другу» я подразумеваю, что путь большого круга между две вершины не пересекаются ни с одним из многоугольников в таблице.

Какой самый быстрый способ сделать это вычисление, предпочтительно в PostgreSQL / PostGIS?

У меня есть кое-что, что работает, но это медленно. Я просто наивно перебираю все пары и вижу, пересекает ли LineString между ними многоугольники. (Географический тип данных PostGIS обрабатывает всю сложную математику для сферы.) Поэтому мне интересно, есть ли умная структура данных или алгоритм, который мог бы ускорить процесс.

CSD
источник
6
Соответствующие концепции: графы видимости и, если вы хотите сделать эту работу в 2D вместо 3D, гномоническая проекция .
whuber
Означает ли "итерация по всем парам", что в процедуре есть цикл FOR, который проверяет, пересекает ли одна линия все многоугольники? Если это так (возможно) быстрее, просто создайте таблицу линейных строк со всеми возможными комбинациями и сделайте один запрос, чтобы проверить, пересекает ли линия таблицу многоугольников
simplexio
Не могли бы вы поделиться иллюстрацией проблемы.
addcolor
Вы можете исключить все, что находится за сферическим горизонтом (плюс бит для высоких объектов у края), что быстро делается с помощью рамки с приблизительными координатами. В противном случае я думаю, что это принципиально NP трудно.
AnserGIS

Ответы:

1

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

Питер
источник