El objetivo de este script es encontrar el camino más corto entre dos puntos que se encuentran dentro de un polígono con obstáculos. Estos obstáculos están definidos por la intersección de dos o más polígonos.
El script esta desarrollado completamente en JavaScript, pero supongo que es fácil de adaptar a otros lenguajes.
He encontrado un bug hasta el momento, el cual no se ve reflejado en la aplicación que se muestra en esta página.
Para comenzar con la explicación de este script debo primero decir que mi inspiración surge del sitio de
Darel Rex Finley (a quien debo agradecer por su trabajo y buena voluntad) donde en su publicación
Shortest path through a concave polygon with holes (Camino más corto a través de un polígono cóncavo con agujeros) nos explica un método para lograr nuestro propósito.
El método consiste en una búsqueda optimizada. La misma se realiza formando ramificaciones desde el punto de origen hacia todos los demás nodos (incluyendo el punto de destino), conectando con cada nodo por el camino mas corto, comenzando con el de menor recorrido hasta llegar al de mayor recorrido.
En su sitio Darel publicó un script desarrollado en C, con el cual no pude obtener buenos resultados, probablemente por algún error de mi parte al convertirlo a JavaScript, lo que me llevó a desarrollar mi propio script utilizando su método. En su sitio también hay una publicación llamada
Point in polygon (Punto en polígono) la cual he utilizado para desarrollar este script, por lo tanto recomiendo que den una mirada a su explicación.
Conociendo el método a utilizar procedo a enumerar los pasos para que dicho método sea efectivo:
1) Declaramos los polígonos (polígono principal y obstaculos)
- Cada polígono se almacena en un array y dentro de ese array se crea otro para cada nodo de cada polígono
2) Declaramos el punto de origen y punto de destino
3) Verificamos si el nodo de origen y el nodo de destino se pueden unir por una recta sin pasar por ningún obstáculo
- Si este fuera el caso...problema resuelto
4) Declaramos un array que incluye todos los nodos de todos los polígonos y los nodos de origen y destino
- A estos nodos (excepto el de origen) los agregamos a un array de nodos no conectados
5) Buscamos los nodos accesibles desde el nodo de origen y los agregamos a un array de nodos disponibles
- A cada nodo conectable desde el punto de origen le damos un valor G hipotético que consiste en la distancia desde ese nodo al nodo de origen siguiendo un cierto camino
- También le asignamos el camino, que en este caso incluiría solamente el nodo de origen y el mismo nodo que estamos analizando
6) Declaramos que el nodo de origen es el nodo actual
Luego se repite el siguiente ciclo hasta que se encuentre un camino o no hayan más nodos disponibles:
7) Dentro de los nodos disponibles buscamos el de menor G hipotético
8) El G hipotético es ahora el G óptimo
9) Verificamos si este nodo es el nodo de destino
- De ser el nodo de destino en el array camino tenemos la resolución del problema
10) Eliminamos este nodo de la lista de nodos no conectados y la lista de nodos disponibles
11) El nodo pasa a ser el nodo actual
12) Buscamos los nodos conectables con el nodo actual que a su vez estén en la lista de nodos no conectados
13) Verificamos si el nodo conectable con el nodo actual tiene definido un G hipotetico
- De no ser así se le asigna uno que se calcula sumando el G del nodo actual con la distancia entre el nodo actual y el nodo conectable
- Si ya poseé un valor de G hipotético se compara su valor con el G que tendría pasando por el nodo actual, si es menor se reemplaza su valor
- Si se le asigna un nuevo G tambien debemos actualizar su camino, el mismo va a pasar a ser el camino del nodo actual con la adición del nodo conectable
- Si el nodo no se encuentra en la lista de nodos disponibles lo agregamos
Cargando, por favor aguarde unos instantes...