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:
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.
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
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.
Yeah, I've seen this before, but I don't know what the problem is yet. It looks like it happens when three points are on a line. I think in this case the arc degenerates and the renderer goes crazy.
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.
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.
Welcome to the 49th edition of Community Convergence. The big excitment of late has been the recent release
Thanks everyone for great feedback and bug reports! I've fixed the rendering artefacts so things should appear normally now.
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.
Very cool, A+ for including a working Silverlight example too.
can i do it on other shape other than polygon?
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?
Hi. Very, very cool. If i apply this algorithm with two or more shapes?
Hi, Does work this algorithm with two o more polygons?