Tuesday, February 9, 2010

Algorithms in C#: shortest path around a polygon (polyline routing)

Suppose you have to build a road to connect two cities on different sides of a lake. How would you plan the road to make it as short as possible?

To simplify the problem statement, a lake is sufficiently well modeled by a polygon, and the cities are just two points. The polygon does not have self-intersections and the endpoints are both outside the polygon. If you have Silverlight installed, you can use drag and drop on the points below to experiment:

No comments: