¿Cómo sería un algoritmo de encontrar la distancia más corta entre 2 puntos en horizontal plano 2d , especialmente cuando el camino recto no es posible? Podría ser algo en las líneas de calcular el mínimo desplazamiento de la senda recta?
Respuestas
¿Demasiados anuncios?
El problema de calcular la ruta más corta entre dos puntos es conocido como la búsqueda de caminos, y hay muchos exactos y aproximados de algoritmos para resolver problemas en una variedad de entornos. Una muy empleado es el de Un* algoritmo de búsqueda y sus variantes.
El uso de Un* búsqueda, primero es necesario discretizar la búsqueda en un espacio gráfico (una malla de navegación). Para un espacio de dos dimensiones, con planta poligonal, obstáculos, yo creo que un adecuado discretización sería tomar como nodos de todos los ángulos de los polígonos (además de la de partida y la meta de puntos) y como los bordes de la línea recta caminos entre ellos, excluyendo cualquier rutas que pasan a través de los obstáculos (pero incluyendo los bordes de los polígonos).
En tres dimensiones, las cosas se ponen más complicadas, como lo demuestra el hecho de que puede haber puntos que no están aún accesible a través de un camino recto desde cualquier punto de esquina de un poliédrica obstáculo.
Ps. El camino rojo en la imagen no es la más corta posible, ya que se hace que de vueltas a los puntos excepto en las esquinas de los obstáculos. En particular, la ruta verde de abajo (que sólo hace girar en las esquinas) es claramente más corta:
Elements in Space
Puntos
794
