Finding shortest path connecting two points under assumption of staying on the "road"?

Question

I search for the name (and later the algorithm ;) ) of the following problem: find the shortest path from point z0 to ze such as the path stays on the "road". The illustration below shows it better. The road is defined by two vectors of points X=(x1,...,xk) and Y=(y1,...,yn). We assume that the problem is not tricky (i.e. paths X, Y do not cross, initial / end points are on the "road", etc.). We want to find red line (defined as a vector) Z being a shortest path connecting z0 with zend and passing only by the road. Algorithm does not need to be fast. Thanks a lot for any hints!

UPDATE: After the remark I changed the image since it showed wrong solution... :/

Answer 1

The way you've drawn it, your road is a monotone polygon (that is, there's always Y to the left of you, and X to the right of you, when you're facing directly north). Once you've triangulated the polygon there's an algorithm specifically for finding shortest paths in a monotone triangulation, called the "funnel algorithm".

For triangulating the monotone, the description in Mark de Berg's Computational Geometry is great, but failing that, http://www.cs.ucf.edu/courses/cot5520/Triangul_monotone.ppt looks pretty good. For the funnel algorithm, try here.

Answer 2

Perhaps this is the wrong answer, but I am assuming that x and y coordinates are the contour of the road. If so, why not do the following:

1. Draw a line down the middle of the road (separating traffic),
2. Assume the user is driving on the right side (or left for UK, Australia or Japan).
3. Assuming a single lane, then draw a line in the middle of the right side.
4. This line would be the distance traveled along the road.

If this is a road and you look at the red line in the example, the driver is at times in the emergency lane or curb and other times in oncoming traffic.