shortest path search in a map represented as 2d shapes

Question

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

Answer 1

What's the "path" you're looking for? A list of the shapes to traverse? (Otherwise you just draw a straight line between start+end points.)

It's easy to preprocess it into a format where the shapes are vertices and are connected by edges when the shapes share a polygon side. Then, just pass it off to your existing library to get the answer.