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.