Hitung grafik visibilitas pada bola

9

Saya memiliki tabel PostGIS dengan beberapa poligon (disimpan menggunakan tipe data geografi). Mereka mewakili daerah di bumi bulat.

Untuk setiap pasangan simpul yang dipilih dari semua poligon, saya ingin menghitung apakah kedua simpul itu "terlihat" satu sama lain. (Ada n * ( n -1) / 2 pasangan demikian, di mana n adalah jumlah total simpul unik di semua poligon dalam tabel.) Dengan "terlihat satu sama lain," Maksud saya, jalur lingkaran besar antara dua simpul tidak memotong salah satu poligon di dalam tabel.

Apa cara tercepat untuk melakukan perhitungan itu, lebih disukai di PostgreSQL / PostGIS?

Saya punya sesuatu yang berfungsi, tetapi lambat. Saya secara naif mengulangi semua pasangan dan melihat apakah LineString di antara mereka memotong setiap poligon. (Tipe data geografi PostGIS menangani semua matematika sulit di bola untuk saya.) Jadi saya bertanya-tanya apakah ada struktur data yang pintar atau algoritma yang mungkin mempercepat segalanya.

postgis postgresql spherical-geometry csd
sumber
6
Konsep yang relevan: grafik visibilitas dan, jika Anda ingin melakukan pekerjaan ini dalam 2D ​​daripada 3D, proyeksi Gnomonic .
whuber
Apakah "iterate over all pair" berarti Anda memiliki FOR loop dalam prosedur yang menguji jika satu garis memotong semua poligon ?. Jika demikian, (mungkin) lebih cepat, buat saja tabel linestring dengan semua kemungkinan kombinasi dan lakukan satu kueri tempat Anda menguji apakah garis memotong tabel poligon
simplexio
Bisakah Anda membagikan ilustrasi masalahnya.
addcolor
Anda dapat mengecualikan semua yang ada di luar cakrawala bulat (plus bit untuk objek tinggi di dekat tepi) yang dengan cepat dilakukan dengan kotak pembatas koordinat perkiraan. Kalau tidak, saya pikir itu pada dasarnya NP keras.
AnserGIS

Jawaban:

1

Putuskan apa yang tidak terlihat. Misalkan Anda berdiri di sebuah simpul di pantai, memandangi dua simpul terpencil dari sebuah poligon yang berdekatan. Maka Anda dapat mengasumsikan bahwa setiap simpul di seluruh sektor di belakang simpul ini tidak terlihat dari simpul ini.

Peter
sumber