Oblicz wykres widoczności na kuli

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ć.

postgis postgresql spherical-geometry csd
źródło

Istotne pojęcia: wykresy widoczności i, jeśli chcesz wykonać tę pracę w 2D zamiast 3D, projekcja Gnomonic .

whuber

czy „iteracja po wszystkich parach” oznacza, że masz w procedurze pętlę FOR, która sprawdza, czy jedna linia przecina wszystkie wielokąty ?. Jeśli tak jest (prawdopodobnie) szybciej, po prostu utwórz tabelę z liniami ze wszystkimi możliwymi kombinacjami i wykonaj jedno zapytanie, w którym sprawdzasz, czy linia przecina tabelę wielokątów

simplexio,

Czy możesz podzielić się ilustracją problemu?

addcolor

Możesz wykluczyć wszystko poza sferycznym horyzontem (plus bit dla wysokich obiektów w pobliżu krawędzi), co można szybko zrobić za pomocą przybliżonej ramki ograniczającej współrzędne. W przeciwnym razie myślę, że jest to zasadniczo trudne NP.

AnserGIS,

Oblicz wykres widoczności na kuli

Odpowiedzi: