[vtkusers] Single source shortest path class published

Rasmus Reinhold Paulsen rrp at imm.dtu.dk
Fri Apr 5 06:21:43 EST 2002


> -----Original Message-----
> From: Miller, James V (CRD) [mailto:millerjv at crd.ge.com]
> Sent: 4. april 2002 23:44
>
> It would be cool if there was a mode such the shortest path
> was not constrained to walk from vertex to vertex along the
> polydata.  I would love to have an implementation that allowed
> me to give two points on the surface of a polydata (not necessarily
> vertices but points within a polygon) and have the path
> walk long the surface crossing edges (but not necessarily
> crossing an edge at a vertex).
>
> I suppose you could start with the path that you calculate now
> and then run a relaxation step that will move the points from
> the vertex positions along the edges to further reduce the cost.

Thanks for the swift feedback. That is a very good idea to postprocess the
solution. Using a smoothness constraint and allow the path vertices to move
on the mesh edges could be useable, but I see it a seperate processing step.
The Dijkstra is a (non-unique) exact solution but I see the other as an
approximation with no guarentees.

If it is the "resolution" of the solution that is the problem a quick hack
would be to preprocess the mesh with a subdivision filter, thus generating
more "ways" for the shortest path.

Keep 'em coming!
Rasmus




More information about the vtkusers mailing list