Mam tabelę PostGIS z kilkoma wielokątami (przechowywanymi przy użyciu typu danych geograficznych). Reprezentują regiony na kulistej ziemi.
Dla każdej pary wierzchołków wybranych spośród wszystkich wielokątów chcę obliczyć, czy te dwa wierzchołki są dla siebie „widoczne”. (Istnieje n * ( n -1) / 2 takich par, gdzie n jest całkowitą liczbą unikalnych wierzchołków we wszystkich wielokątach w tabeli.) Przez „widoczne dla siebie” rozumiem, że ścieżka wielkiego koła między dwa wierzchołki nie przecinają żadnego z wielokątów w tabeli.
Jaki jest najszybszy sposób wykonania tego obliczenia, najlepiej w PostgreSQL / PostGIS?
Mam coś, co działa, ale jest powolne. Po prostu naiwnie iteruję po wszystkich parach i sprawdzam, czy LineString między nimi przecina jakieś wielokąty. (Typ danych geograficznych PostGIS obsługuje dla mnie całą trudną matematykę na kuli.) Zastanawiam się więc, czy istnieje sprytna struktura danych lub algorytm, który może przyspieszyć.