shortest path search in a map represented as 2d shapes
Posted
by joe_shmoe
on Stack Overflow
See other posts from Stack Overflow
or by joe_shmoe
Published on 2010-04-29T14:45:19Z
Indexed on
2010/04/29
14:47 UTC
Read the original article
Hit count: 335
Hi,
I have a small library of a few shortest path search algorithms. They were developed for simple undirected graphs (the normal representation - vertices and edges). Now I'd like to somehow apply them on a bit different scenario - where the maps are represented as 2-dimensional shapes, connected by shared edges (edges of the polygons, that is). In this scenario, the search can start/end either at a map object or some point (x,y). What would be the best approach? Try to apply the algorithms onto shapes? or try to extract a 'normal' graph out of the shapes (I have preprocessing time available)? Any advice would be much appreciated, as I'm really not sure which way to go, and I don't have enough time (and skill) to explore many options...
Thanks a lot
© Stack Overflow or respective owner