9

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.

  • 6
    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
1

Deduce what is not visible. Suppose you stand at a vertex on the beach, looking at two remote vertices of a neighboring polygon. Then you can assume that any vertex in the whole sector behind these vertices is invisible from this vertex.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.