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.

Improve this question
4
  • 6
    Relevant concepts: visibility graphs and, if you want to do this work in 2D instead of 3D, the Gnomonic projection.
    – whuber
    Commented Apr 23, 2014 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
    – simpleuser001
    Commented Nov 11, 2015 at 9:29
  • Could you share an illustration of the problem.
    – addcolor
    Commented Jun 19, 2016 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
    Commented Aug 18, 2016 at 8:27

1 Answer 1

Reset to default
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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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