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:

Solution description

A shortest path between two points is a segment that connects them. It’s clear that our route consists of segments (if a part of the path was a curve other than a segment, we could straighten it and get better results). Moreover, those segments (which are part of the route) have their endpoints either on polygon vertices or the start or end point. Again, if this were not the case, we would be able to make the path shorter by routing via the nearest polygon vertex.

Armed with this knowledge, let’s consider all possible segments that connect the start and end point and all polygon vertices that don’t intersect the polygon. Let’s then construct a graph out of these segments. Now we can use Dijkstra’s algorithm (or any other path finding algorithm such as A*) to find the shortest route in the graph between start and endpoints. Note how any shortest path algorithm can essentially boil down to a path finding in a graph, because a graph is a very good representation for a lot of situations.

From the implementation perspective, I used my dynamic geometry library and Silverlight to create a simple demo project that lets you drag the start and end points as well as polygon vertices. You can also drag the polygon and the plane itself. I also added rounded corners to the resulting path and made it avoid polygon vertices to make it look better.

Here is the source code for the sample. Here’s the main algorithm. It defines a data structure to describe a Graph that provides the ShortestPath method, which is the actual implementation of the Dijkstra’s algorithm. ConstructGraph takes care of adding all possible edges to the graph that do not intersect our polygon. SegmentIntersectsPolygon also determines what the name suggests.

I hope to post more about polygon routing in the future and do let me know if you have any questions.

Comments

• Anonymous
  June 07, 2009
  Now I know how pathfinding works :) Btw, the silverlight program seems to fail and start drawing triangles instead of lines for me at some situations: http://www.picamatic.com/show/2009/06/08/01/30/3932016_481x451.png

• Anonymous
  June 08, 2009
  I've been in the business world going on ten years now doing general business application development and I've recently had an inkling to get back into game development. I read articles like this and I see why I feel that way. Very cool. Thank you for sharing.

• Anonymous
  June 08, 2009
  The comment has been removed

• Anonymous
  June 08, 2009
  OK I know where the artefact comes from - I'm trying to draw an arc to a point which is too close to the previous one (the arc radius is larger). It looks like instead of just not drawing the arc, Silverlight tries to do it anyway and produces the weird triangle. I'll fix it when I have time.

• Anonymous
  June 09, 2009
  This is generalized into the Convex Hull computer imaging problem.  A convex hull is a polygon that surrounds an arbritrary shape found in a computer bitmap.

• Anonymous
  June 09, 2009
  Welcome to the 49th edition of Community Convergence. The big excitment of late has been the recent release

• Anonymous
  June 10, 2009
  Thanks everyone for great feedback and bug reports! I've fixed the rendering artefacts so things should appear normally now.

• Anonymous
  August 24, 2009
  Besides A* in place of Dijkstra this problem allows other interesting optimizations: when constructing a graph of segments (in the second paragraph under "Solution description") we can take significantly lesser amount of segments (and vertices) and still get a correct solution. This improvement helps a lot when a number of shortest path queries are executed on the same map so we can reuse once-built optimized graph again and again.

• Anonymous
  February 25, 2010
  Very cool, A+ for including a working Silverlight example too.

• Anonymous
  March 13, 2010
  can i do it on other shape other than polygon?

• Anonymous
  March 16, 2010
  Well, my implementation only works for polygons. I think you can approximate any shape reasonably well with a polygon. What shapes do you have in mind?

• Anonymous
  December 01, 2010
  Hi. Very, very cool. If i apply this algorithm with two or more shapes?

• Anonymous
  December 08, 2011
  Hi, Does work this algorithm with two o more polygons? best regards

• Anonymous
  February 15, 2014
  Is it possible to get all network router information and also get the information of all possible routing path and select shortest path ? please provide solution and C# code that is perform above task