Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Point on Line Segment in 3D ? Fast Algorithm

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Jens Hilwig

Date: 30 May, 2008 08:39:53

Message: 1 of 8

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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Roger Stafford

Date: 30 May, 2008 09:17:01

Message: 2 of 8

"Jens Hilwig" <jhilwig@gmx.de> wrote in message
<6a9sqqF35gdblU1@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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Kevin

Date: 30 Jun, 2010 13:13:04

Message: 3 of 8

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <g1ogmd$9md$1@fred.mathworks.com>...
> "Jens Hilwig" <jhilwig@gmx.de> wrote in message
> <6a9sqqF35gdblU1@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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Avni Pllana

Date: 30 Jun, 2010 14:13:44

Message: 4 of 8

> 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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Roger Stafford

Date: 30 Jun, 2010 16:16:21

Message: 5 of 8

Avni Pllana <avniu66@hotmail.com> wrote in message <461012205.28470.1277907275265.JavaMail.root@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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Matt J

Date: 30 Jun, 2010 18:08:04

Message: 6 of 8

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

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Kevin

Date: 30 Jun, 2010 19:30:20

Message: 7 of 8

How could this method be used for finding if a point was located beneath a surface. Such as a matrix of points?

Subject: Point on Line Segment in 3D ? Fast Algorithm

From: Matt J

Date: 30 Jun, 2010 20:04:04

Message: 8 of 8

"Kevin " <kablack@umich.edu> wrote in message <i0g60c$afg$1@fred.mathworks.com>...
> How could this method be used for finding if a point was located beneath a surface. Such as a matrix of points?
=============

I doubt it could.

In the case of a surface, you would need to first find an equation that describes the surface and fits the points. In the case of the line segment, that's trivial, because it is straightforward how to fit a line segment to 2 points.

Once you have your surface equation c(x)=0, determining whether a point P lies in, under, or above the surface is a matter of looking at the sign of c(P).

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us