Estoy buscando un algoritmo eficiente que encuentre la ruta globalmente más corta entre dos puntos en un espacio bidimensional con obstáculos poligonales.Encontrar la ruta globalmente más corta en trapezoides no degeneradas
Los datos fuente están en forma de una trapezoidación vertical no degenerada que consta de hasta 10^4 trapezoides (no degenerados, lo que significa que el lado inferior y el superior de cada trapezoide tienen como máximo 2 trapecios vecinos cada uno).
La ejecución de un algoritmo de ruta más corta en la propia trapezoidación y el uso de un algoritmo de embudo no garantiza la búsqueda de la ruta globalmente más corta.
Calcular el gráfico de visibilidad de los vértices de las esquinas podría funcionar, aunque sospecho que podría usar demasiada memoria porque el requisito para el algoritmo es que pueda usarse frecuentemente (aproximadamente 100 veces por segundo) en un servidor con múltiples (hasta 700) mapas en la memoria, pero no dude en corregirme si cree que no es un problema.
Para visualizar cómo son los datos, cargué la triangulación de un pequeño mapa, puede hacer clic en la imagen para verla como un SVG.
.
el camino más corto se compone de segmentos de recta entre el punto frontera a punto frontera (aparte del segmento desde el punto inicial y el segmento hasta el destino si no son puntos fronterizos). Entonces, el gráfico de visibilidad de todos los puntos fronterizos debería darle la ruta más corta. –
Sí, lo consideré en la pregunta, pero me parece que esto requeriría una gran cantidad de memoria. – xDD
Empiezo a ver el punto ... con 10^4 trapezoides uno tiene aproximadamente 2 * 10^4 puntos (cada uno de los cuales puede representarse con un entero de 16 bits, es decir, 2 bytes) que conducen a 4 * 10^8 bordes en el peor caso significa 800 MBytes para uno solo de los 700 mapas ... –