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: Walter Roberson on 17 May 2010 18:09 Meagan wrote: > To answer your questions, > -the line is allowed to cross a face > -the shape in convex > -it is a 3D problem > -it is correct to say that I am looking for the "path length" as in your > example of a helix. Not so easy. Perhaps we should try a simple example and see if we can come up with a strategy. Let us take a 2 x 2 rectangle with a slit from the middle to the right side, and let us lift up the upper-right 1 x 1 flap to an angle of 45 degrees relative to the plane, and let us calculate the distance between the two right hand corners. In this example, because of the discontinuity not providing a valid path, the answer would clearly be to go from the top right corner to the center and there to the bottom right corner, for a total path length of 2 * sqrt(2). Now, let us fasten join two edges of the slight with some stretchable elastic, so as to provide a triangular surface between the two halves. If my mental imaging is correct, there is a path that goes along the right side of the top flap, then drops a perpendicular to the top of the bottom flap, then goes diagonally over to the bottom right corner, and I believe that path length would be 1 + 1/sqrt(2) + sqrt(3 - 2*sqrt(2)), which would be 3/sqrt(2), and thus would be less than the 2 * sqrt(2) for the other path. Is there a shorter route? If not, how do we prove that? Let us take this further by taking that elastic joining the two halves of the slit, and stretching the center of it up or down. possibly to a peak above or valley below. As the distance along that perpendicular increases, it might be worth heading some amount further to the left to avoid descending the valley or climbing the peak, until eventually we get end up with the shortest distance again being to go to the middle and back -- but how do we optimize the path length? I believe that this example is solvable in theory (and practice), but it would take me some more thinking to set up the path length equations.
From: Walter Roberson on 17 May 2010 18:21 Walter Roberson wrote: > Meagan wrote: >> To answer your questions, >> -the line is allowed to cross a face >> -the shape in convex >> -it is a 3D problem >> -it is correct to say that I am looking for the "path length" as in >> your example of a helix. > > Not so easy. Perhaps we should try a simple example and see if we can > come up with a strategy. After all of that, I re-read and realized I had confused "concave" and "convex". The example I gave is concave. For convex... ummm... Suppose you have a square pyramid and the two points are opposite corners of the square. If the pyramid is 0 height then the shortest path would go directly over the center to the opposite corner, and if the pyramid is infinitely high (and thus has infinite slope) then the shortest path is going to go along the two edges. There is plausibly a maximum slope that makes it worth traveling at least part-way over the surface, but at first glance it is also plausible that for any finite slope the shortest path might go over the surface at least a little bit; I would have to explore that further. Clearly, though, as the center rises, the path would get pushed further and further towards following the edges. I haven't figured out yet what the balance is.
From: ImageAnalyst on 17 May 2010 18:23 Couldn't you use dynamic programming? I used that once to track blood vessels but it's a pretty general concept that I think should be able to find the shortest distance numerically. http://en.wikipedia.org/wiki/Dynamic_programming
From: Matt J on 17 May 2010 18:31 ImageAnalyst <imageanalyst(a)mailinator.com> wrote in message <9cf53832-31d4-4c7e-b5a2-4994719d03a4(a)u7g2000vbq.googlegroups.com>... > Couldn't you use dynamic programming? I used that once to track blood > vessels but it's a pretty general concept that I think should be able > to find the shortest distance numerically. > http://en.wikipedia.org/wiki/Dynamic_programming ================= Perhaps if the linear pieces of the path were requireded to run between vertices of the polyhedron. Otherwise, I don't see what sort of backward induction rule you could set up.
From: Roger Stafford on 17 May 2010 18:38
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <hssdij$7pp$1(a)fred.mathworks.com>... > "Meagan " <meagan.musselman(a)l-3com.com> wrote in message <hssche$2o9$1(a)fred.mathworks.com>... > > > > > -the line is allowed to cross a face > > -the shape in convex > > -it is a 3D problem > > -it is correct to say that I am looking for the "path length" as in your example of a helix. > ============== > > I'm going to hypothesize that the shortest distance across a 3D convex polyhedral surface is a piecewise linear path confined to a single plane (don't know how to prove it off the top of my head, though). > > Under this hypothesis, a helpful tool for this problem might be the vert2con function in the FEX: > > http://www.mathworks.com/matlabcentral/fileexchange/7895-vert2con-vertices-to-constraints > > It will allow you to input the vertices and obtain the representation of the polyhedron in the form > > A*x<=b > > The intersection of the polyhedron with a plane passing through your 2 given surface points is a 2D polygon. Using the above inequalities, you can find this 2D polygon and represent it in the x-y plane. Then, you can use this tool > > http://www.mathworks.com/matlabcentral/fileexchange/7894-con2vert-constraints-to-vertices > > to find the vertices of the 2D polygon and trace the distance between the successive vertices. > > The above will give you total distance between the two points for one particular planar cut through the 2 given surface points (and the polyhedron's surface). Using fminsearch, you can search over all such cuts for the minimum distance. > > There are a lot of details to fill in here, but at least this might be a direction to go... 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. For a smooth surface a geodesic curve must always have the curve's normal parallel to the surface's normal, and as the surface normal tilts to the right or left along the path, the curve must corresponingly adjust its own normal to match. (A curve's normal is defined as being in the direction of the change of the tangent unit vector - in other words it must lie in the best-fitting plane to the curve at a given point and be orthogonal to the tangent vector.) Roger Stafford |