# Compute visibility graph on sphere

I have a PostGIS table with some polygons (stored using the geography data type). They represent regions on a spherical earth.

For each pair of vertices chosen from among all the polygons, I want to calculate whether those two vertices are "visible" to each other. (There are n*(n-1)/2 such pairs, where n is the total number of unique vertices across all polygons in the table.) By "visible to each other," I mean that the great-circle path between the two vertices does not intersect any of the polygons in the table.

What is the fastest way to do that computation, preferably in PostgreSQL/PostGIS?

I've got something that works, but it's slow. I just naively iterate over all pairs and see if the LineString between them intersects any polygons. (PostGIS's geography data type handles all the hard math on the sphere for me.) So I wonder if there's a clever data structure or algorithm that might speed things up.

• Relevant concepts: visibility graphs and, if you want to do this work in 2D instead of 3D, the Gnomonic projection. – whuber Apr 23 '14 at 19:16
• does "iterate over all pairs" mean that you have FOR loop in procedure which test if one line intersct all polygons?. If so it is (probably) faster just create linestring table with all possible combinations and do one query where you test if line intersects polygon table – simplexio Nov 11 '15 at 9:29
• Could you share an illustration of the problem. – addcolor Jun 19 '16 at 4:49
• You can exclude everything beyond the spherical horizon (plus bit for tall objects near the edge) which is quickly done with an approximate coordinate bounding box. Otherwise I think it is fundamentally NP hard. – AnserGIS Aug 18 '16 at 8:27