find distance along complicated geometric surface
in [Matlab]
|
Prev: Error while evaluating TimerFCN for timer 'timer-1'
Next: BIJECTION ISSUE, iradon(radon(L*L)) --->(L+2)^2
From: Matt J on 18 May 2010 11:55 Perhaps the following article can help. I haven't read it, though R. Kimmel and N. Kiryati. Finding shortest paths on surfaces by fast global approximation and precise local refinement. International Journal of Pattern Recognition and Artificial Intelligence, 10(6):643-656, 1996.
From: Rune Allnor on 18 May 2010 13:34 On 17 Mai, 22:45, "Meagan " <meagan.mussel...(a)l-3com.com> wrote: > hi all, > > I am working on a project and I have hit a wall and could really use some help. > > I am trying to find the distance between two points on a shape that is defined by vertices and faces. I can't just use the distance formula because I need to make sure that the entire distance between the two points is in contact with the shape surface. I have no idea how to start doing this or if this task is even possible so any input would be greatly appreciated. The *idea* is simple, assuming you already have a surface consisting of edges and vertices, like in a triangulation: Track the points where you cross edges, and compute the distance between consecutive edge crossings (possibly also accounting for path waypoints). The total distance along the path will be the cumulant sum of all such edge-to-edge distances. *Implementing* this simple idea is not at all simple. If you want this to be fast, you will need to have access to certain awkward data structures internal to the triangulated surface. A naive method might be to check the path for intersections with all the edges in the triangulation. This method will find all the edge crossings, and will also allow you to sort the edge crossing points to the order in which they are traversed along the path. However, this method will be very slow; maybe intolerably slow. Rune
From: Matt J on 18 May 2010 13:51 Rune Allnor <allnor(a)tele.ntnu.no> wrote in message <99c70f0a-1227-4506-b3a1-ab85568616c8(a)l6g2000vbo.googlegroups.com>... > The *idea* is simple, assuming you already have a surface > consisting of edges and vertices, like in a triangulation: > Track the points where you cross edges, and compute the > distance between consecutive edge crossings (possibly also > accounting for path waypoints). The total distance along the > path will be the cumulant sum of all such edge-to-edge > distances. ======== The difficulty though, Rune, is that you don't have the shortest-distance path a priori. It's finding the shortest path, not computing its length, which is the challenge.
From: Rune Allnor on 18 May 2010 14:52 On 18 Mai, 19:51, "Matt J " <mattjacREM...(a)THISieee.spam> wrote: > Rune Allnor <all...(a)tele.ntnu.no> wrote in message <99c70f0a-1227-4506-b3a1-ab8556861...(a)l6g2000vbo.googlegroups.com>... > > The *idea* is simple, assuming you already have a surface > > consisting of edges and vertices, like in a triangulation: > > Track the points where you cross edges, and compute the > > distance between consecutive edge crossings (possibly also > > accounting for path waypoints). The total distance along the > > path will be the cumulant sum of all such edge-to-edge > > distances. > > ======== > > The difficulty though, Rune, is that you don't have the shortest-distance path a priori. It's finding the shortest path, not computing its length, which is the challenge. I can't see how being able to compute the distance along a genrral path isn't helpful: 1) Select an initial path 2) Compute the distance along this path 3) Modify the path in a way that likely might shorten the distance 4) Repeat from 2 until no significant improvements in path distance can be made. Of course, one can only hope to find a local solution to this problem. Rune
From: ImageAnalyst on 18 May 2010 15:08
On May 18, 1:51 pm, "Matt J " <mattjacREM...(a)THISieee.spam> wrote: > The difficulty though, Rune, is that you don't have the shortest-distance path a priori. It's finding the shortest path, not computing its length, which is the challenge. ---------------------------------------------------------------------------------------------------------- Isn't that were dynamic programming, Djikstra, A*, or your other favorite search-path/optimization routine comes in? They will efficiently find the shortest path (given all the possible points along the way) without searching through an infinite number of possibilities. For example, if you're tracking a bright ridge (e.g. a blood vessel in an angiogram) and you know two image columns that it passes through, you can use dynamic programming to find the path between the left column and the right column that has the highest average brightness - without actually searching through all the bazillion possible paths. (I know because I've done it, although it was 24 years ago) In Meagan's case she could use the cumulative length of the path for the criteria rather than the average path brightness as in my example. However with my limited spare time, I'm not about to tackle her airplane data, though I think it could be done. |