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 17 May 2010 19:05 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hssggc$gr8$1(a)fred.mathworks.com>... > Matt, geodesics, even over surfaces consisting of plane faces, do not have to follow a planar path. ========= OK. Well, clearly, they must follow a linear path across each face. I'm starting to wonder if this couldn't be used to set up a dynamic programming formulation, along the lines of what ImageAnalyst was proposing... However, it still seems like it would lead to a brutal continuous state space dynamic program.
From: ImageAnalyst on 17 May 2010 21:00 On May 17, 6:31 pm, "Matt J " <mattjacREM...(a)THISieee.spam> wrote: > Perhaps if the linear pieces of the path were required to run between vertices of the polyhedron. Otherwise, I don't see what sort of backward induction rule you could set up. -------------------------------------------------------------- Well, you're right Matt. I was thinking that if she needed to find the distance along the faces/facets that she'd just resample it fine enough to create extra vertices so that it could traverse the face. For example, it might be shorter to travel AROUND the mountain than across it's peak but if all you had was the peak and the base locations, you couldn't go around, but if you interpolated more locations in between (which would be on the sides of the mountain), then you could go around. And, by the way, I realize it would be a numerical approximation, not an exact analytical one but I was assuming that she didn't really have an analytical function to begin with anyway - that it was starting out as a numerical array (which may or may not be a sampling of an analytical function but that's immaterial).
From: Walter Roberson on 18 May 2010 00:44 Matt J wrote: > "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in > message <hssggc$gr8$1(a)fred.mathworks.com>... >> Matt, geodesics, even over surfaces consisting of plane faces, do >> not have to follow a planar path. > OK. Well, clearly, they must follow a linear path across each face. I'm > starting to wonder if this couldn't be used to set up a dynamic > programming formulation, along the lines of what ImageAnalyst was > proposing... However, it still seems like it would lead to a brutal > continuous state space dynamic program. I am not _certain_ that it would lead to a continuous state space dynamic program. When you get down to a simple enough geometry, I think you should be able to solve the problem absolutely (except for symmetries), and it seems to me that the assumption of convex shape should allow one to reason about which faces and edges could be involved in the shortest path. If the problem involved con*cave* objects, then you would run into situations where you headed "down" and have to switch to "up" (or vice versa), which could lead you to taking zig-zags around the outskirts of a face to avoid going too far up or down on the face. That cannot happen on a con*vex* object: once you are on a face, all the other faces attached to it curl "down" away from that plane. I think it would help if we had an example from the original poster to look at.
From: Bruno Luong on 18 May 2010 02:11 "Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hssggc$gr8$1(a)fred.mathworks.com>... > > Matt, geodesics, even over surfaces consisting of plane faces, do not have to follow a planar path. They can wander back and forth in complicated ways in seeking a shortest path. Agree with Roger. The geodesic on polytope is a straight line when the polytope is flattenen (making a cuts on the cell edges, excepted those crossed by the geoderic, then change the dihedral angle between to neighboring faces to pi, i.e., 180 degree). As we disccus in earlier thread, given a local azimuth direction from the start point, is possible to follow the geodesic from cell to cell by the above characteristic. The problem become 1D solve: find the azimuth that leads to the geodesic crossing the end point. Easy to tell the theory than to code it. Bruno
From: Roger Stafford on 18 May 2010 05:52
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hstb1q$fl7$1(a)fred.mathworks.com>... > Agree with Roger. > > The geodesic on polytope is a straight line when the polytope is flattenen (making a cuts on the cell edges, excepted those crossed by the geoderic, then change the dihedral angle between to neighboring faces to pi, i.e., 180 degree). As we disccus in earlier thread, given a local azimuth direction from the start point, is possible to follow the geodesic from cell to cell by the above characteristic. The problem become 1D solve: find the azimuth that leads to the geodesic crossing the end point. Easy to tell the theory than to code it. > > Bruno Following those geodesics from various azimuths is not as one-dimnsional an affair as one would like it to be. For example, if two geodesics proceeding as you correctly describe, Bruno, and in nearly parallel paths, go short distances on opposite sides of a vertex joining three facets, then after they pass that vertex their paths may cross each other at very sizable angles on the other side. This means that choosing an azimuth for one geodesic just to the left of another geodesic is no guarantee that that geodesic will remain to the left. It can go far to the right instead. Therefore there can remain still much of a combinatorial nature about seeking a shortest path across a surface composed of numerous plane facets and therefore exceedingly difficult to determine. Roger Stafford |