Calcular gráfico de visibilidad en esfera

9

Tengo una tabla PostGIS con algunos polígonos (almacenados usando el tipo de datos de geografía). Representan regiones en una tierra esférica.

Para cada par de vértices elegidos entre todos los polígonos, quiero calcular si esos dos vértices son "visibles" entre sí. (Hay n * ( n -1) / 2 de esos pares, donde n es el número total de vértices únicos en todos los polígonos de la tabla). Por "visible el uno al otro", me refiero a que la ruta del gran círculo entre dos vértices no se cruzan con ninguno de los polígonos en la tabla.

¿Cuál es la forma más rápida de hacer ese cálculo, preferiblemente en PostgreSQL / PostGIS?

Tengo algo que funciona, pero es lento. Simplemente ingenuamente itero sobre todos los pares y veo si LineString entre ellos se cruza con algún polígono. (El tipo de datos de geografía de PostGIS maneja todas las matemáticas difíciles en la esfera para mí). Entonces me pregunto si hay una estructura de datos inteligente o un algoritmo que pueda acelerar las cosas.

postgis postgresql spherical-geometry csd
fuente
66
Conceptos relevantes: gráficos de visibilidad y, si desea hacer este trabajo en 2D en lugar de 3D, la proyección gnomónica .
whuber
¿"iterar sobre todos los pares" significa que tiene un bucle FOR en el procedimiento que prueba si una línea interactúa con todos los polígonos? Si es así, es (probablemente) más rápido, simplemente cree una tabla de
cadenas lineales
¿Podría compartir una ilustración del problema?
addcolor
Puede excluir todo más allá del horizonte esférico (más el bit para objetos altos cerca del borde) que se realiza rápidamente con un cuadro de límite de coordenadas aproximado. De lo contrario, creo que es fundamentalmente NP difícil.
AnserGIS

Respuestas:

1

Deduce lo que no es visible. Suponga que se para en un vértice en la playa, mirando dos vértices remotos de un polígono vecino. Entonces puede suponer que cualquier vértice en todo el sector detrás de estos vértices es invisible desde este vértice.

Peter
fuente