Prev: problem with dsolve
Next: Response from Agilent about Segmented Memory's distribution
From: Kevin on 30 Jun 2010 09:13
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <g1ogmd$9md$1(a)fred.mathworks.com>...
> "Jens Hilwig" <jhilwig(a)gmx.de> wrote in message
> <6a9sqqF35gdblU1(a)mid.uni-berlin.de>...
> > Hello,
> >
> > Im looking for a fast algorithm to determine if a point (3D) is inside a
> > line segment (3D).
> > Can you help me ?
> >
> > Regards
> >
> > Jens
> ----------
> If P1 and P2 are vectors giving the endpoint coordinates of the line segment
> and P the coordinates of an arbitrary point, then P lies within the line segment
> whenever
>
> (norm(cross(P-P1,P2-P1)) < tol) & ...
> (dot(P-P1,P2-P1) >= 0) & (dot(P-P2,P2-P1) <= 0)
>
> is true, where 'tol' is just large enough to allow for worst case round-off error
> in performing the 'cross', 'dot', and 'norm' operations.
>
> Roger Stafford
>

I am trying to do the same thing that Jens was I belive, but I am not sure how to go about finding a value for the variable 'tol', what is a standard value to use here. or how do i go about getting a proper value for 'tol'?
Thanks,
Kevin
From: Avni Pllana on 30 Jun 2010 06:13
> Hello,
>
> Im looking for a fast algorithm to determine if a
> point (3D) is inside a
> line segment (3D).
> Can you help me ?
>
> Regards
>
> Jens
>
>
>

Hi Jens,

a simple criterion is as follows:

norm(P-P1) + norm(P-P2) = norm(P1-P2)

Best regards,
Avni
From: Roger Stafford on 30 Jun 2010 12:16
Avni Pllana <avniu66(a)hotmail.com> wrote in message <461012205.28470.1277907275265.JavaMail.root(a)gallium.mathforum.org>...
> > Hello,
> >
> > Im looking for a fast algorithm to determine if a
> > point (3D) is inside a
> > line segment (3D).
> > Can you help me ?
> >
> > Regards
> >
> > Jens
> >
> >
> >
>
> Hi Jens,
>
> a simple criterion is as follows:
>
> norm(P-P1) + norm(P-P2) = norm(P1-P2)
>
> Best regards,
> Avni
- - - - - - - - - -
In the ideal mathematical world, yes, but from a numerical analysis point of view this test is prone to far more inaccuracy than with the cross product.

Suppose P is at the line segment's midpoint and the segment is of length 2. If it is moved perpendicularly by .001, Pythagoras's theorem says that the sum of the distances from the endpoints would increase by the much smaller amount 0.000001 .

Clearly using the sum of the distances this way is a very poor kind of test.

Roger Stafford
From: Matt J on 30 Jun 2010 14:08
Here's another method, similar to Roger's. It might be competitive speed-wise since it cuts down on the dot() and cross() operations. Haven't raced them against each other, though.


A=P2-P1; %direction vector
b=P-P1;

alpha=A\b; %projection of P onto line is at A*alpha+P1

alpha= min(max(alpha,0),1); %restrict projection to line segment

PassFail=norm(A*alpha-b)<tol, %distance of P to projection must obey a tolerance
From: Kevin on 30 Jun 2010 15:30
How could this method be used for finding if a point was located beneath a surface. Such as a matrix of points?
 |  Next  |  Last
Pages: 1 2
Prev: problem with dsolve
Next: Response from Agilent about Segmented Memory's distribution