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

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

Ivan — Mon, 08 Jun 2009 12:30:48 GMT

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

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

Sean — Mon, 08 Jun 2009 16:52:59 GMT

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.

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

Kirill Osenkov — Mon, 08 Jun 2009 16:55:37 GMT

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.

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

Kirill Osenkov — Mon, 08 Jun 2009 17:25:03 GMT

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.

Convex Hull

Greg — Tue, 09 Jun 2009 17:55:42 GMT

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.

Community Convergence XLIX (IL)

Charlie Calvert's Community Blog — Tue, 09 Jun 2009 23:47:59 GMT

Welcome to the 49th edition of Community Convergence. The big excitment of late has been the recent release

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

Kirill Osenkov — Thu, 11 Jun 2009 00:22:43 GMT

Thanks everyone for great feedback and bug reports! I've fixed the rendering artefacts so things should appear normally now.

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

Sasha Gil — Tue, 25 Aug 2009 03:21:34 GMT

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.