<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2653.12">
<TITLE>RE: [vtkusers] Shortest route algorithms?</TITLE>
</HEAD>
<BODY>
<P><FONT SIZE=2>Hi there,</FONT>
</P>
<P><FONT SIZE=2>Thanks for the reply, after posting the message, I Google'd around and found your site. It looks like it can be quite useful, I'll just have to find out two things: 1) how to use it for a grid (maybe just convert the grid to polydata - I'm interested in the final cost, more than HAVING to keep it a grid) and 2) how to compile your code so that I can use it from Python.</FONT></P>
<P><FONT SIZE=2>Will bug you some more if I really have a problem figuring something out ;)</FONT>
</P>
<P><FONT SIZE=2>Regards</FONT>
<BR><FONT SIZE=2>Etienne</FONT>
</P>
<P><FONT SIZE=2>-----Original Message-----</FONT>
<BR><FONT SIZE=2>From: Rasmus Reinhold Paulsen [<A HREF="mailto:rrp@imm.dtu.dk">mailto:rrp@imm.dtu.dk</A>]</FONT>
<BR><FONT SIZE=2>Sent: Thursday, September 19, 2002 11:55 AM</FONT>
<BR><FONT SIZE=2>To: Etienne Labuschagne</FONT>
<BR><FONT SIZE=2>Cc: Vtkusers (E-mail)</FONT>
<BR><FONT SIZE=2>Subject: Re: [vtkusers] Shortest route algorithms?</FONT>
</P>
<BR>
<P><FONT SIZE=2>Hi Etienne,</FONT>
</P>
<P><FONT SIZE=2>On Thu, 19 Sep 2002, Etienne Labuschagne wrote:</FONT>
</P>
<P><FONT SIZE=2>> If I have a structured grid containing a cost for each cell, what's the best</FONT>
<BR><FONT SIZE=2>> way to determine the least cost route from one cell to another.</FONT>
<BR><FONT SIZE=2>> </FONT>
<BR><FONT SIZE=2>> I am thinking along the lines of using Dijkstra's algorithm but if there is</FONT>
<BR><FONT SIZE=2>> already something available that is implemented for VTK, I would of course</FONT>
<BR><FONT SIZE=2>> be glad to use that!</FONT>
</P>
<P><FONT SIZE=2>I have implemented a Dijkstra shortest path algorithm for polydata. It is</FONT>
<BR><FONT SIZE=2>therefore not directly usefull for your data, but perhaps you can use some</FONT>
<BR><FONT SIZE=2>of it. I believe though that if you want state-of-the-art path finding,</FONT>
<BR><FONT SIZE=2>level-sets and fast-marching methods are the way to go.</FONT>
</P>
<P><FONT SIZE=2>Look at </FONT>
<BR><FONT SIZE=2>www.imm.dtu.dk/~rrp/VTK</FONT>
</P>
<P><FONT SIZE=2>for the Dijkstra class.</FONT>
</P>
<P><FONT SIZE=2>Regards,</FONT>
<BR><FONT SIZE=2>Rasmus</FONT>
</P>
</BODY>
</HTML>