*****************************************************
* Desarrollado por Ødd Øne Øut - www.OddOneOut.info *
*****************************************************

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
		  
VARIABLES QUE NECESITAN SER DECLARADAS PREVIAMENTE;
* poligonos - ARRAY
* solucion - ARRAY
* xi - INTEGER
* yi - INTEGER
(xi e yi son necesarias para la comunicación entre las funciones intersección_rectas e interseccion_segmentos)

		  
SCRIPT PRINCIPAL
 * buscar_camino

SCRIPTS SECUNDARIOS
* segmento_en_poligono - Verifíca si un segmento determinado se encuentra dentro del polígono principal y no atraviesa obstáculos
* poligono - Define las coordenadas de los nodos que forman los polígonos

SCRIPTS TERCIARIOS
* punto_en_poligono - Indica si un punto se encuentra dentro del polígono principal y fuera de los obstáculos
* interseccion_rectas - Nos devuelve el punto de intersección de dos rectas si es que existe
* interseccion_segmentos - Nos devuelve el punto de intersección de dos segmentos si es que existe
* punto_en_segmento - Nos indica si un punto forma parte de un segmento
* distancia - Devuelve la distancia entre dos puntos

<script language="javascript">
	function buscar_camino(origen_x, origen_y, destino_x, destino_y)
	{
		// Reiniciamos la variable de solucion
		solucion = [];
		
		// Comenzamos buscando la solucion mas sencilla que seria que el punto de origen y el de destino se pudieran conectar con una simple linea
		if (segmento_en_poligono(origen_x, origen_y, destino_x, destino_y))
		{
			solucion = [];
			solucion[0] = [];
			solucion[0]["x"] = origen_x;
			solucion[0]["y"] = origen_y;
			solucion[1] = [];
			solucion[1]["x"] = destino_x;
			solucion[1]["y"] = destino_y;
			return true;
		}
		
		var nodos = [];
		var nodos_no_conectados = [];
		var nodos_disponibles = [];
		var posibles_nuevos_nodos = [];
		var nuevos_nodos = [];
		var nodo_actual;
		
		// Crea una lista de nodos comenzando con el punto de origen, pasando por todos los nodos de cada poligono y finalizando con el punto de destino
		nodos[0] = [];
		nodos[0]["x"] = origen_x;
		nodos[0]["y"] = origen_y;
		nodos[0]["g_hipotetico"] = 0;
		nodos[0]["g_optimo"] = true;
		nodos[0]["camino"] = [];
		nodos[0]["camino"].push(0);
		
		// Esta variable le asignara un ID a cada nodo y al final termina indicando la cantidad total de nodos
		var cantidad_nodos = 1;
		
		// Repite el codigo para cada poligono existente
		for (i = 0; i < poligonos.length; i++)
		{
			// Repite el codigo para cada nodo del poligono
			for (j = 0; j < poligonos[i].length; j++)
			{
				nodos[cantidad_nodos] = [];
				nodos[cantidad_nodos]["x"] = poligonos[i][j]["x"];
				nodos[cantidad_nodos]["y"] = poligonos[i][j]["y"];
				nodos[cantidad_nodos]["camino"] = [];

				// Verifica si el nodo se encuentra disponible desde el punto de origen
				if (segmento_en_poligono(origen_x, origen_y, nodos[cantidad_nodos]["x"], nodos[cantidad_nodos]["y"]))
				{
					// Si el nodo se puede conectar con el punto inicial se le asigna el G hipotetico
					nodos[cantidad_nodos]["g_hipotetico"] = distancia(origen_x, origen_y, nodos[cantidad_nodos]["x"], nodos[cantidad_nodos]["y"]);

					// Agrega el nodo a la lista de nodos disponibles
					nodos_disponibles.push(cantidad_nodos);

					// Creamos el camino del nodo actual
					nodos[cantidad_nodos]["camino"].push(0);
					nodos[cantidad_nodos]["camino"].push(cantidad_nodos);
				}

				// Agrega este nodo a la lista de nodos no conectados
				nodos_no_conectados.push(cantidad_nodos);
				
				cantidad_nodos++;
			}
		}
		
		nodos[cantidad_nodos] = [];
		nodos[cantidad_nodos]["x"] = destino_x;
		nodos[cantidad_nodos]["y"] = destino_y;
		nodos[cantidad_nodos]["camino"] = [];
		nodos_no_conectados.push(cantidad_nodos);
		cantidad_nodos++;
		
		nodo_actual = 0;
		
		// Mientras hayan nodos disponibles a los que moverse...
		while (nodos_disponibles.length > 0)
		{
			var nodo_menor_g = nodos_disponibles[0];
			var menor_g = nodos[nodos_disponibles[0]]["g_hipotetico"];

			// Busca el nodo de menor G hipotetico dentro de los nodos disponibles
			for (i = 0; i < nodos_disponibles.length; i++)
			{
				if (nodos[nodos_disponibles[i]]["g_hipotetico"] < menor_g)
				{
					nodo_menor_g = nodos_disponibles[i];
					menor_g = nodos[nodos_disponibles[i]]["g_hipotetico"];
				}
			}
			
			// Actualizamos el G optimo de este nodo
			nodos[nodo_menor_g]["g_optimo"] = true;
			
			// Verificamos si el nodos de menor G hipotetico es el punto de destino
			if (nodo_menor_g == cantidad_nodos - 1)
			{
				solucion = [];
				for (i = 0; i < nodos[nodo_menor_g]["camino"].length; i++)
				{
					solucion[i] = [];
					solucion[i]["x"] = nodos[nodos[nodo_menor_g]["camino"][i]]["x"];
					solucion[i]["y"] = nodos[nodos[nodo_menor_g]["camino"][i]]["y"];
					solucion.push(nodos[nodo_menor_g]["camino"][i]);
				}
				return true;
			}
			
			// Eliminamos el nodo de menor G de la lista de nodos no conectados y de la lista de nodos disponibles
			nodos_no_conectados.splice(nodos_no_conectados.indexOf(nodo_menor_g), 1);
			nodos_disponibles.splice(nodos_disponibles.indexOf(nodo_menor_g), 1);

			// Asigna el nodo de menor G como nodo_actual
			nodo_actual = nodo_menor_g;
			
			// Buscamos los nodos conectables al nodo actual que esten en la lista de nodos no conectados.
			for (i = 0; i < nodos_no_conectados.length; i++)
			{
				if (segmento_en_poligono(nodos[nodo_actual]["x"], nodos[nodo_actual]["y"], nodos[nodos_no_conectados[i]]["x"], nodos[nodos_no_conectados[i]]["y"]))
				{
					// Comparamos el G hipotetico actual con el G hipotetico partiendo desde el nodo actual (Si esta sin definir es un G hipotetico valido)
					if (nodos[nodos_no_conectados[i]]["g_hipotetico"] > nodos[nodo_actual]["g_hipotetico"] + distancia(nodos[nodo_actual]["x"], nodos[nodo_actual]["y"], nodos[nodos_no_conectados[i]]["x"], nodos[nodos_no_conectados[i]]["y"]) || nodos[nodos_no_conectados[i]]["g_hipotetico"] == undefined)
					{
						// Actualizamos el G hipotetico
						nodos[nodos_no_conectados[i]]["g_hipotetico"] = nodos[nodo_actual]["g_hipotetico"] + distancia(nodos[nodo_actual]["x"], nodos[nodo_actual]["y"], nodos[nodos_no_conectados[i]]["x"], nodos[nodos_no_conectados[i]]["y"]);
						
						// Actualizamos el camino del nodo
						nodos[nodos_no_conectados[i]]["camino"] = [];
						for (j = 0; j < nodos[nodo_actual]["camino"].length; j++)
						{
							nodos[nodos_no_conectados[i]]["camino"].push(nodos[nodo_actual]["camino"][j]);
						}
						nodos[nodos_no_conectados[i]]["camino"].push(nodos_no_conectados[i]);
					}
					
					// Si el nodo no se encuentra en la lista de nodos disponibles lo agregamos
					if (nodos_disponibles.indexOf(nodos_no_conectados[i]) == -1)
					{
						// Agregamos el nodo a la lista de nodos disponibles
						nodos_disponibles.push(nodos_no_conectados[i]);
					}
				}
			}
		}
		return false;
	}

	function segmento_en_poligono(x1, y1, x2, y2)
	{
		/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		// Existe un problema con esta función. Para ver los detalles dirigirse a http://www.OddOneOut.info/laboratorio/camino_mas_corto/bug_1.jpg //
		/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
		// Verificamos que los puntos A y B esten dentro del poligono
		if (!punto_en_poligono(x1, y1)) return false;
		if (!punto_en_poligono(x2, y2)) return false;
		
		var contacto_con_poligono_a = -1;
		var contacto_con_poligono_b = -1;

		for (i_sep = 0; i_sep < poligonos.length; i_sep++)
		{
			for (j_sep = 0; j_sep < poligonos[i_sep].length; j_sep++)
			{
				var k_sep = j_sep + 1;
				if (k_sep == poligonos[i_sep].length) k_sep = 0;

				var x3 = poligonos[i_sep][j_sep]["x"];
				var y3 = poligonos[i_sep][j_sep]["y"];
				var x4 = poligonos[i_sep][k_sep]["x"];
				var y4 = poligonos[i_sep][k_sep]["y"];

				// Verificamos si el segmento intersecta el lado del poligono que analizamos
				if (interseccion_segmentos(x1, y1, x2, y2, x3, y3, x4, y4))
				{
					return false;
				}
				
				// Verificamos si uno de los extremos del segmento pertenece al lado del poligono que analizamos
				if (contacto_con_poligono_a == -1)
				{
					if (punto_en_segmento(x1, y1, x3, y3, x4, y4)) contacto_con_poligono_a = j_sep;
				}
				if (contacto_con_poligono_b == -1)
				{
					if (punto_en_segmento(x2, y2, x3, y3, x4, y4)) contacto_con_poligono_b = j_sep;
				}
			}
		}
		
		// Si el segmento tiene contacto con el poligono en sus dos extremos realizamos la verificacion nuevamente con uno de los extremos del segmento y el punto medio del mismo
		if (contacto_con_poligono_a != -1 && contacto_con_poligono_b != -1)
		{
			var xa = (x2 - x1) / 2 + x1;
			var ya = (y2 - y1) / 2 + y1;

			for (i_sep = 0; i_sep < poligonos.length; i_sep++)
			{
				for (j_sep = 0; j_sep < poligonos[i_sep].length; j_sep++)
				{
					var k_sep = j_sep + 1;
					if (k_sep == poligonos[i_sep].length) k_sep = 0;

					var x3 = poligonos[i_sep][j_sep]["x"];
					var y3 = poligonos[i_sep][j_sep]["y"];
					var x4 = poligonos[i_sep][k_sep]["x"];
					var y4 = poligonos[i_sep][k_sep]["y"];
					
					// Basicamente llamamos esta misma funcion. El motivo por el cual no hacemos eso exactamente es por problemas con las variables de los for
					if (!punto_en_poligono(xa, ya)) return false;
					
					var contacto_con_poligono_a = -1;
					var contacto_con_poligono_b = -1;

					for (i_sep_2 = 0; i_sep_2 < poligonos.length; i_sep_2++)
					{
						for (j_sep_2 = 0; j_sep_2 < poligonos[i_sep_2].length; j_sep_2++)
						{
							var k_sep_2 = j_sep_2 + 1;
							if (k_sep_2 == poligonos[i_sep_2].length) k_sep_2 = 0;

							var x3 = poligonos[i_sep_2][j_sep_2]["x"];
							var y3 = poligonos[i_sep_2][j_sep_2]["y"];
							var x4 = poligonos[i_sep_2][k_sep_2]["x"];
							var y4 = poligonos[i_sep_2][k_sep_2]["y"];

							// Verificamos si el segmento intersecta el lado del poligono que analizamos
							if (interseccion_segmentos(x1, y1, xa, ya, x3, y3, x4, y4))
							{
								return false;
							}
						}
					}
				}
			}
		}
		return true;
	}

	function poligono() // Acepta el formato (arg1, arg2, arg3, ...) y ("arg1, arg2, arg3, ...")
	{
		if (arguments.length == 1)
		{
			var arguments = arguments[0].split(", ");
			
			for (i = 0; i < arguments.length; i++)
			{
				arguments[i] = parseInt(arguments[i]);
			}
		}
		
		var x = []
		var y = []
		for (i = 0; ; i++)
		{
			if (arguments[i * 2] != undefined)
			{
				x[i] = arguments[i * 2];
				y[i] = arguments[i * 2 + 1];
				var puntos = i + 1;
			}
			else
			{
				break;
			}
		}
		
		// Crea el array conteniendo los atributos del poligono
		var cantidad_poligonos = poligonos.length;
		poligonos[cantidad_poligonos] = [];
		for (i = 0; i < puntos; i++)
		{
			poligonos[cantidad_poligonos][i] = [];
			poligonos[cantidad_poligonos][i]["x"] = x[i];
			poligonos[cantidad_poligonos][i]["y"] = y[i];
		}
	}
	
	function punto_en_poligono(test_x, test_y)
	{
		var x = [];
		var y = [];
		
		var dentro = false;
		
		for (i_pep = 0; i_pep < poligonos.length; i_pep++)
		{
			for (j_pep = 0; j_pep < poligonos[i_pep].length; j_pep++)
			{
				var k_pep = j_pep + 1;
				if (k_pep == poligonos[i_pep].length) k_pep = 0;
				
				// Verificamos si el punto forma parte del segmento en cuyo caso consideramos que forma parte del poligono
				if (punto_en_segmento(test_x, test_y, poligonos[i_pep][j_pep]["x"], poligonos[i_pep][j_pep]["y"], poligonos[i_pep][k_pep]["x"], poligonos[i_pep][k_pep]["y"])) return true;
				if (poligonos[i_pep][j_pep]["y"] < test_y && poligonos[i_pep][k_pep]["y"] >= test_y || poligonos[i_pep][k_pep]["y"] < test_y && poligonos[i_pep][j_pep]["y"] >= test_y)
				{
					if (poligonos[i_pep][j_pep]["x"] + (test_y - poligonos[i_pep][j_pep]["y"]) / (poligonos[i_pep][k_pep]["y"] - poligonos[i_pep][j_pep]["y"]) * (poligonos[i_pep][k_pep]["x"] - poligonos[i_pep][j_pep]["x"]) < test_x)
					{
						dentro = dentro?false:true;
					}
				}
			}
		}
		return dentro;
	}
		
	function interseccion_rectas(x1, y1, x2, y2, x3, y3, x4, y4)
	{
		var m1 = (y2 - y1) / (x2 - x1);
		var m2 = (y4 - y3) / (x4 - x3);
		var n1 = y1 - (x1 * (y2 - y1) / (x2 - x1));
		var n2 = y3 - (x3 * (y4 - y3) / (x4 - x3));
		
		if (Math.abs(m1) == Math.abs(m2))
		{
			return false;
		}
		
		if (Math.abs(m1) == Infinity || Math.abs(m2) == Infinity)
		{
			if (Math.abs(m1) == Infinity)
			{
				xi = x1;
				yi = xi * (y4 - y3) / (x4 - x3) + n2;
				return true;
			}
			else
			{
				xi = x3;
				yi = xi * (y2 - y1) / (x2 - x1) + n1;
				return true;
			}
		}
		else
		{
			xi = (n2 - n1) / (m1 - m2);
			yi = m1 * xi + n1;
			return true;
		}
	}

	function interseccion_segmentos(x1, y1, x2, y2, x3, y3, x4, y4)
	{
		xi = '';
		yi = '';

		// Si uno de los extremos de alguno de los dos segmenos forma parte del otro segmento consideramos que no se intersectan
		if (punto_en_segmento(x1, y1, x3, y3, x4, y4) || punto_en_segmento(x2, y2, x3, y3, x4, y4) || punto_en_segmento(x3, y3, x1, y1, x2, y2) || punto_en_segmento(x4, y4, x1, y1, x2, y2)) return false;
		
		var interseccion = interseccion_rectas(x1, y1, x2, y2, x3, y3, x4, y4);
		
		if (interseccion)
		{
			var i_en_ab = ((xi >= x1 && xi <= x2) || (xi <= x1 && xi >= x2)) && ((yi >= y1 && yi <= y2) || (yi <= y1 && yi >= y2))? true: false;
			var i_en_cd = ((xi >= x3 && xi <= x4) || (xi <= x3 && xi >= x4)) && ((yi >= y3 && yi <= y4) || (yi <= y3 && yi >= y4))? true: false;
			return i_en_ab == true && i_en_cd == true? true: false;
		}
		else
		{
			return false;
		}
	}

	function punto_en_segmento(xa, ya, x1, y1, x2, y2)
	{
		// Verificamos que el punto A pertenezca a la recta formada por los extremos del segmento
		if (xa * (y2 - y1) - ya * (x2 - x1) - x1 * (y2 - y1) + y1 * (x2 - x1) == 0)
		{
			// Verificamos si el punto esta entre los extremos del segmento
			return ((xa >= x1 && xa <= x2) || (xa <= x1 && xa >= x2)) && ((ya >= y1 && ya <= y2) || (ya <= y1 && ya >= y2))? true: false;
		}
		else
		{
			return false;
		}
	}

	function distancia(x1, y1, x2, y2)
	{
		x2 -= x1;
		y2 -= y1;
		return Math.sqrt(x2 * x2 + y2 * y2);
	}
</script>