Más

Encontrar el camino más corto evitando las entidades poligonales

Encontrar el camino más corto evitando las entidades poligonales


Estoy desarrollando una extensión de ArcMap donde tengo un conjunto de entidades poligonales cóncavas estáticas y estoy tratando de encontrar la ruta más corta entre 2 puntos sin cruzar ninguno de los polígonos.

¿Existe un algoritmo para hacer esto?


Si tiene la extensión Spatial Analyst y no le importa trabajar con representaciones ráster de sus datos, puede usar el Análisis de ruta de costos. Los detalles y otras opciones se pueden encontrar dentro del tema de ayuda y la barra lateral asociada para la ayuda.


Una vez implementé un algoritmo que calcula un polígono que incluye el área de un plano (con obstáculos poligonales) que se puede alcanzar en una cierta distancia. Lo que más me ayudó fue darme cuenta de que problemas del camino más corto en un avión esquivando obstáculos se puede considerar como problemas de visibilidad. Si bien no se discute a menudo en un contexto SIG, los problemas de visibilidad son muy populares y están bien documentados en geometría computacional.

Hay dos enfoques que puede tomar para resolver el problema:

  1. Puede encontrar la ruta más corta usando solo los polígonos que son relevantes usando un índice espacial como un R-Tree para que sus polígonos aceleren las cosas.

  2. Puede construir un gráfico sobre todos sus polígonos y luego encontrar la ruta más corta dentro de ese gráfico.

El enfoque 1. es mejor si no puede mantener el estado interno entre las veces que se usa el algoritmo. Si tiene que calcular muchos caminos más cortos y los polígonos permanecen igual, el enfoque 2. es mejor.

El enfoque 1. es lo que hice con mi algoritmo. Lo que hice fue básicamente esto:

  1. Dibuja una línea entre el punto de inicio y el punto final.
  2. Vea si se cruza con el interior de al menos un polígono. Si no se cruza, este es su camino más corto.
  3. Si se cruza, tome el segmento de polígono que se cruza más cerca del punto de inicio.
  4. Itera a través de los vértices del polígono hacia la izquierda y hacia la derecha hasta que una línea entre el vértice y el punto final no se cruce con el interior del polígono o hasta que la línea directa entre el vértice se cruce con otro polígono. Si se cruza con otro polígono, vaya al paso 2 con ese polígono. De lo contrario, vaya al paso 1 y recuerde la longitud entre el punto de inicio y el vértice que ahora es el nuevo punto de inicio.

El enfoque 2. probablemente sea más adecuado para el problema descrito aquí y debería ser más fácil de implementar.

El gráfico que necesita para enrutar en un plano con polígonos como obstáculos es el gráfico de visibilidad. La forma de construir con fuerza bruta es bastante simple. Primero calcula el casco convexo de sus polígonos. Los vértices que no se encuentran en el casco convexo no necesitan formar parte del gráfico de visibilidad. Los vértices del casco convexo son los nodos del gráfico de visibilidad. Luego dibuja una línea entre todos los pares de vértices y observa si esa línea se cruza con el interior de un polígono. Si la línea no se cruza con uno de los polígonos, es un borde en el gráfico de visibilidad.

Debe agregar su punto de inicio y finalización al gráfico de visibilidad. Luego, puede utilizar un algoritmo de ruta más corta ponderada de fuente única. El algoritmo de Dijkstra funcionará bien. Si espera muchas consultas de ruta más corta, puede valer la pena utilizar un algoritmo que calcule todas las rutas más cortas y calcule las rutas más cortas entre todos los pares de nodos en el gráfico de visibilidad de antemano.

Por supuesto, el gráfico de visibilidad se puede utilizar con las herramientas de enrutamiento existentes, por lo que no tiene que implementar el algoritmo de ruta más corta si tiene acceso a dicha herramienta. (Aún enfrenta el problema de que debe agregar sus puntos de inicio y finalización si aún no forman parte de la red)


Aquí hay un código de muestra usando ArcObjects para encontrar la ruta más corta (usando RasterDistanceOP). Puede que esto no sea exactamente lo que desea, sin embargo, puede darle un punto de partida.

Cómo encontrar la ruta más corta usando RasterDistanceOp


Los primeros pensamientos que me vinieron a la cabeza fueron así:

  1. Determine los límites máximos de todas las características, incluidos los puntos de inicio y finalización, elimínelos un poco para asegurarse de que haya espacio alrededor de todas las características. Hacer una característica rectangular, B, desde estos límites.
  2. Reste las características de bloqueo de B.
  3. Tesselate B en triángulos, asegurándose de que los vértices inicial y final sean vértices en esta nueva malla triangular, metro.
  4. Genera los polígonos de Voronoi, t (que deberían ser todos triángulos) de metro.
  5. Los bordes de t Forme una red en la que pueda ejecutar un algoritmo de ruta más corta.

Es posible que esto no genere el mejor camino más corto, porque depende de cómo el teselador haga su trabajo y, en cualquier caso, tomará una línea central en lugar de la línea de carrera. Pero es concebible que después de que se haya generado la ruta más corta, pueda mover o eliminar vértices, probando cada borde afectado para la intersección con las entidades de bloqueo y deshaciendo la operación si se cruza.


El problema es complicado. Hay una nueva implementación genérica: algoritmo de ruta más corta euclidiana

Funciona para cualquier conjunto de objetos de superficie mallados.


Si no le importa traducir algo de C, puede probar el script en http://alienryderflex.com/shortest_path/