Prev: Error while evaluating TimerFCN for timer 'timer-1'
Next: BIJECTION ISSUE, iradon(radon(L*L)) --->(L+2)^2
From: Meagan on 17 May 2010 16:45
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.

Thanks,
Meagan
From: Walter Roberson on 17 May 2010 17:00
Meagan wrote:

> 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.

Sounds tricky.

To cross-check: is it permitted for the line to cross a face? For example, if
you had two triangles joined at the base, then the shortest distance between
the far corners would probably go over the faces.

Also, is the shape convex or could it be concave? Concave would, I think, be a
much harder problem.
From: Walter Roberson on 17 May 2010 17:16
Walter Roberson wrote:
> Meagan wrote:
>
>> 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.
>
> Sounds tricky.
>
> To cross-check

Another question to cross-check: is this a 2D or 3D problem (or more?)

When you speak of "distance" and needing contact with the shape surface, would
I be correct in figuring that what you want is the "path length" ? Just to be
sure we have disambiguited "distance" correctly.

For example, if we had a discretized helix, then the distance between two
points would be the same no matter how tightly or loosely the helix was coiled
(provided that the coils did not touch) ?
From: Meagan on 17 May 2010 17:30
Walter Roberson <roberson(a)hushmail.com> wrote in message <hssboe$avg$1(a)canopus.cc.umanitoba.ca>...
> Walter Roberson wrote:
> > Meagan wrote:
> >
> >> 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.
> >
> > Sounds tricky.
> >
> > To cross-check
>
> Another question to cross-check: is this a 2D or 3D problem (or more?)
>
> When you speak of "distance" and needing contact with the shape surface, would
> I be correct in figuring that what you want is the "path length" ? Just to be
> sure we have disambiguited "distance" correctly.
>
> For example, if we had a discretized helix, then the distance between two
> points would be the same no matter how tightly or loosely the helix was coiled
> (provided that the coils did not touch) ?


Thank you for clarifying. I had a feeling that I did not include enough detail in the original message. 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.

Thank you so much for your help,
Meagan
From: Matt J on 17 May 2010 17:48
"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...
 |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Error while evaluating TimerFCN for timer 'timer-1'
Next: BIJECTION ISSUE, iradon(radon(L*L)) --->(L+2)^2