[Talk-es] Calculo del camino mas corto en un espacio continuo

[andrzej zaborowski]

2010/12/30 Xavier Barnada Rius <xbarnada en gmail.com>:
> Hola,por hay algun algoritmo que permita el calculo del camino mas corto
> en un espacio continuo como por ejemplo a traves de una zona con casas o
> muros?
> Se que existe Dijkstra para el caluculo de rutas a taves de grafos como
> los de los que se suelen usar con las carreteras, pero en un espacio
> abierto se deberian considerar infinitos nodos en el grafo.

Seguramente existe algo mas efectivo, pero una posibilidad seria usar
el dijkstra en un grafo que contiene todos los vertices de todos los
objetos, y un arco entre cada dos vertices si la linea recta entre los
dos puntos no choca con otros objetos. (en realidad solo se tomarian
en cuenta los vertices de las "envolturas convexas" de los objetos)

Saludos