Thread Subject: distance between point and line segment

Is there a simple way to find the distance between a line segment and
a point? I'm looking for the 2D case specifically, but the more
general 3D case would also be nice to know...
Thanks.
-Steve

Steve <srjm72499@gmail.com> wrote in message <4a2f4ac1-
c21e-4ebf-8530-352f15098a47@41g2000hsc.googlegroups.com>...
> Is there a simple way to find the distance between a line segment and
> a point? I'm looking for the 2D case specifically, but the more
> general 3D case would also be nice to know...
> Thanks.
> -Steve
-------
  Let Q1 and Q2 be endpoints (or any two distinct points) of the line segment
and P the point in question, then

 d = abs(cross(Q2-Q1,P-Q1))/abs(Q2-Q1);

will give the requested orthogonal distance.

Roger Stafford

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fpdqru$8lg$1@fred.mathworks.com>...
> Steve <srjm72499@gmail.com> wrote in message <4a2f4ac1-
> c21e-4ebf-8530-
352f15098a47@41g2000hsc.googlegroups.com>...
> > Is there a simple way to find the distance between a
line segment and
> > a point? I'm looking for the 2D case specifically,
but the more
> > general 3D case would also be nice to know...
> > Thanks.
> > -Steve
> -------
> Let Q1 and Q2 be endpoints (or any two distinct
points) of the line segment
> and P the point in question, then
>
> d = abs(cross(Q2-Q1,P-Q1))/abs(Q2-Q1);
>
> will give the requested orthogonal distance.
>
> Roger Stafford
>
Roger,

This fromual needs that the point be specified for the z
axis.

Do you use z= 0 or z =1?

Chuk

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fpdqru$8lg$1@fred.mathworks.com>...
> Steve <srjm72499@gmail.com> wrote in message <4a2f4ac1-
> c21e-4ebf-8530-
352f15098a47@41g2000hsc.googlegroups.com>...
> > Is there a simple way to find the distance between a
line segment and
> > a point? I'm looking for the 2D case specifically,
but the more
> > general 3D case would also be nice to know...
> > Thanks.
> > -Steve
> -------
> Let Q1 and Q2 be endpoints (or any two distinct
points) of the line segment
> and P the point in question, then
>
> d = abs(cross(Q2-Q1,P-Q1))/abs(Q2-Q1);
>
> will give the requested orthogonal distance.
>
> Roger Stafford
> Also is there a simple way to know if the distances are
on the same side or oposite sides of the line?

Thanks for your help

Chuk

"Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message <fslmdo
$7qg$1@fred.mathworks.com>...
> This fromual needs that the point be specified for the z axis.
> Do you use z= 0 or z =1?
> Chuk
--------
  The formula I gave:

 d = abs(cross(Q2-Q1,P-Q1))/abs(Q2-Q1);

was meant for the 3D case. For the 2D case it becomes

 d = abs(det([Q2-Q1,P-Q1]))/abs(Q2-Q1);

if P, Q1, and Q2 are column vectors, or

 d = abs(det([Q2-Q1;P-Q1]))/abs(Q2-Q1);

if they are row vectors.

Roger Stafford

On Feb 19, 1:39=A0am, Steve <srjm72...@gmail.com> wrote:
> Is there a simple way to find the distance between a line segment and
> a point? =A0I'm looking for the 2D case specifically, but the more
> general 3D case would also be nice to know...
> Thanks.
> -Steve

Steve:
Yep, the 3 D case is here:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html
(See equation 4.)

The 2D case is here:
http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html
(See especially equation 11.)

Glad to help,
ImageAnalyst

Yes thanks for your replies.

However if I use the cross product and assume that the z
axis have zero components I actually get some reuslts
which are more than an order of magnitude bigger thant the
case when I use the determinant to solve for two
dimensions.
Please what is happening to cause such a difference in
results.

Thanks

Chuk

ImageAnalyst <imageanalyst@mailinator.com> wrote in
message <d122bed7-41d5-446a-8b0a-
e786bdb938fb@a22g2000hsc.googlegroups.com>...
> On Feb 19, 1:39=A0am, Steve <srjm72...@gmail.com> wrote:
> > Is there a simple way to find the distance between a
line segment and
> > a point? =A0I'm looking for the 2D case specifically,
but the more
> > general 3D case would also be nice to know...
> > Thanks.
> > -Steve
>
> Steve:
> Yep, the 3 D case is here:
> http://mathworld.wolfram.com/Point-LineDistance3-
Dimensional.html
> (See equation 4.)
>
> The 2D case is here:
> http://mathworld.wolfram.com/Point-LineDistance2-
Dimensional.html
> (See especially equation 11.)
>
> Glad to help,
> ImageAnalyst

"Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message <fsrkeb
$os2$1@fred.mathworks.com>...
> Yes thanks for your replies.
>
> However if I use the cross product and assume that the z
> axis have zero components I actually get some reuslts
> which are more than an order of magnitude bigger thant the
> case when I use the determinant to solve for two
> dimensions.
> Please what is happening to cause such a difference in
> results.
>
> Thanks
>
> Chuk
--------
  First of all, Chuk, let me apologize for the errors in the formulas I gave back
on Feb. 19, and for not noticing them this past Saturday. I cannot imagine
what I was thinking of. The 3D formula should read:

 d = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);

and the 2D versions ought to read:

 d = abs(det([Q2-Q1,P-Q1]))/norm(Q2-Q1); % for col. vectors
 d = abs(det([Q2-Q1;P-Q1]))/norm(Q2-Q1); % for row vectors.

  In this corrected form the 3D formula is identical to the formula (9) of the
website:

 http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

which ImageAnalyst mentioned.

  A note of caution! Formula (4) at that website, which ImageAnalyst also
mentioned, while being mathematically equivalent to its formula (9), is not as
computationally robust as (9) in cases where the triangle PQ1Q2 is nearly flat,
that is, where it has two angles nearly zero and one nearly pi.

  Here is a concrete example of such a loss of accuracy:

 Q1 = [0;0;0]; Q2 = [2;4;6]; P = [1.00001;1.99998;3.00001];

This point P will lie very close to the line Q1Q2 (actually very near its
midpoint.) We can then compare three different ways of computing the
orthogonal distance. First, use formula (4)

 d1 = sqrt(norm(Q2-Q1)^2*norm(P-Q1)^2-dot(Q2-Q1,P-Q1)^2)/norm(Q2-
Q1);

Then use my cross product formula which is also formula (9):

 d2 = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);

and finally, as a check, directly compute the nearest point, R, on line Q1Q2
and then compute its distance from P:

 R = (dot(P-Q2,Q1-Q2)*Q1+dot(P-Q1,Q2-Q1)*Q2)/dot(Q2-Q1,Q2-Q1);
 d3 = norm(R-P);

Now compare the answers using 'format long':

 [d1;d2;d3]
 ans =

   1.0e-04 *

   0.24494825921622
   0.24494897427992
   0.24494897427992

Formula (4) is off in the 7th place while the other two methods preserve
normal matlab accuracy.

Roger Stafford

Thanks Roger.
In the realm of GPS, latiudes and longitudes, the
difference in the result is quite significant in terms of
acuracy of distances in meters and centimeter.



Chuk

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1@fred.mathworks.com>...
> "Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message
<fsrkeb
> $os2$1@fred.mathworks.com>...
> > Yes thanks for your replies.
> >
> > However if I use the cross product and assume that
the z
> > axis have zero components I actually get some
reuslts
> > which are more than an order of magnitude bigger thant
the
> > case when I use the determinant to solve for two
> > dimensions.
> > Please what is happening to cause such a difference in
> > results.
> >
> > Thanks
> >
> > Chuk
> --------
> First of all, Chuk, let me apologize for the errors in
the formulas I gave back
> on Feb. 19, and for not noticing them this past
Saturday. I cannot imagine
> what I was thinking of. The 3D formula should read:
>
> d = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and the 2D versions ought to read:
>
> d = abs(det([Q2-Q1,P-Q1]))/norm(Q2-Q1); % for col.
vectors
> d = abs(det([Q2-Q1;P-Q1]))/norm(Q2-Q1); % for row
vectors.
>
> In this corrected form the 3D formula is identical to
the formula (9) of the
> website:
>
> http://mathworld.wolfram.com/Point-LineDistance3-
Dimensional.html
>
> which ImageAnalyst mentioned.
>
> A note of caution! Formula (4) at that website, which
ImageAnalyst also
> mentioned, while being mathematically equivalent to its
formula (9), is not as
> computationally robust as (9) in cases where the
triangle PQ1Q2 is nearly flat,
> that is, where it has two angles nearly zero and one
nearly pi.
>
> Here is a concrete example of such a loss of accuracy:
>
> Q1 = [0;0;0]; Q2 = [2;4;6]; P =
[1.00001;1.99998;3.00001];
>
> This point P will lie very close to the line Q1Q2
(actually very near its
> midpoint.) We can then compare three different ways of
computing the
> orthogonal distance. First, use formula (4)
>
> d1 = sqrt(norm(Q2-Q1)^2*norm(P-Q1)^2-dot(Q2-Q1,P-Q1)
^2)/norm(Q2-
> Q1);
>
> Then use my cross product formula which is also formula
(9):
>
> d2 = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and finally, as a check, directly compute the nearest
point, R, on line Q1Q2
> and then compute its distance from P:
>
> R = (dot(P-Q2,Q1-Q2)*Q1+dot(P-Q1,Q2-Q1)*Q2)/dot(Q2-
Q1,Q2-Q1);
> d3 = norm(R-P);
>
> Now compare the answers using 'format long':
>
> [d1;d2;d3]
> ans =
>
> 1.0e-04 *
>
> 0.24494825921622
> 0.24494897427992
> 0.24494897427992
>
> Formula (4) is off in the 7th place while the other two
methods preserve
> normal matlab accuracy.
>
> Roger Stafford
>
>

Thanks Roger.
In the realm of GPS, latiudes and longitudes, the
difference in the result is quite significant in terms of
acuracy of distances in meters and centimeter.



Chuk

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1@fred.mathworks.com>...
> "Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message
<fsrkeb
> $os2$1@fred.mathworks.com>...
> > Yes thanks for your replies.
> >
> > However if I use the cross product and assume that
the z
> > axis have zero components I actually get some
reuslts
> > which are more than an order of magnitude bigger thant
the
> > case when I use the determinant to solve for two
> > dimensions.
> > Please what is happening to cause such a difference in
> > results.
> >
> > Thanks
> >
> > Chuk
> --------
> First of all, Chuk, let me apologize for the errors in
the formulas I gave back
> on Feb. 19, and for not noticing them this past
Saturday. I cannot imagine
> what I was thinking of. The 3D formula should read:
>
> d = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and the 2D versions ought to read:
>
> d = abs(det([Q2-Q1,P-Q1]))/norm(Q2-Q1); % for col.
vectors
> d = abs(det([Q2-Q1;P-Q1]))/norm(Q2-Q1); % for row
vectors.
>
> In this corrected form the 3D formula is identical to
the formula (9) of the
> website:
>
> http://mathworld.wolfram.com/Point-LineDistance3-
Dimensional.html
>
> which ImageAnalyst mentioned.
>
> A note of caution! Formula (4) at that website, which
ImageAnalyst also
> mentioned, while being mathematically equivalent to its
formula (9), is not as
> computationally robust as (9) in cases where the
triangle PQ1Q2 is nearly flat,
> that is, where it has two angles nearly zero and one
nearly pi.
>
> Here is a concrete example of such a loss of accuracy:
>
> Q1 = [0;0;0]; Q2 = [2;4;6]; P =
[1.00001;1.99998;3.00001];
>
> This point P will lie very close to the line Q1Q2
(actually very near its
> midpoint.) We can then compare three different ways of
computing the
> orthogonal distance. First, use formula (4)
>
> d1 = sqrt(norm(Q2-Q1)^2*norm(P-Q1)^2-dot(Q2-Q1,P-Q1)
^2)/norm(Q2-
> Q1);
>
> Then use my cross product formula which is also formula
(9):
>
> d2 = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and finally, as a check, directly compute the nearest
point, R, on line Q1Q2
> and then compute its distance from P:
>
> R = (dot(P-Q2,Q1-Q2)*Q1+dot(P-Q1,Q2-Q1)*Q2)/dot(Q2-
Q1,Q2-Q1);
> d3 = norm(R-P);
>
> Now compare the answers using 'format long':
>
> [d1;d2;d3]
> ans =
>
> 1.0e-04 *
>
> 0.24494825921622
> 0.24494897427992
> 0.24494897427992
>
> Formula (4) is off in the 7th place while the other two
methods preserve
> normal matlab accuracy.
>
> Roger Stafford
>
>

Roger,

Does htere exist a similar closed formula for finding the
nearest distance to a circle with three points specified
or we may have to apeal to the idea of a langragian
mulitplier or similar contrivance?

Sincerely,

Chuk.

"Roger Stafford"
<ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1@fred.mathworks.com>...
> "Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message
<fsrkeb
> $os2$1@fred.mathworks.com>...
> > Yes thanks for your replies.
> >
> > However if I use the cross product and assume that
the z
> > axis have zero components I actually get some
reuslts
> > which are more than an order of magnitude bigger thant
the
> > case when I use the determinant to solve for two
> > dimensions.
> > Please what is happening to cause such a difference in
> > results.
> >
> > Thanks
> >
> > Chuk
> --------
> First of all, Chuk, let me apologize for the errors in
the formulas I gave back
> on Feb. 19, and for not noticing them this past
Saturday. I cannot imagine
> what I was thinking of. The 3D formula should read:
>
> d = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and the 2D versions ought to read:
>
> d = abs(det([Q2-Q1,P-Q1]))/norm(Q2-Q1); % for col.
vectors
> d = abs(det([Q2-Q1;P-Q1]))/norm(Q2-Q1); % for row
vectors.
>
> In this corrected form the 3D formula is identical to
the formula (9) of the
> website:
>
> http://mathworld.wolfram.com/Point-LineDistance3-
Dimensional.html
>
> which ImageAnalyst mentioned.
>
> A note of caution! Formula (4) at that website, which
ImageAnalyst also
> mentioned, while being mathematically equivalent to its
formula (9), is not as
> computationally robust as (9) in cases where the
triangle PQ1Q2 is nearly flat,
> that is, where it has two angles nearly zero and one
nearly pi.
>
> Here is a concrete example of such a loss of accuracy:
>
> Q1 = [0;0;0]; Q2 = [2;4;6]; P =
[1.00001;1.99998;3.00001];
>
> This point P will lie very close to the line Q1Q2
(actually very near its
> midpoint.) We can then compare three different ways of
computing the
> orthogonal distance. First, use formula (4)
>
> d1 = sqrt(norm(Q2-Q1)^2*norm(P-Q1)^2-dot(Q2-Q1,P-Q1)
^2)/norm(Q2-
> Q1);
>
> Then use my cross product formula which is also formula
(9):
>
> d2 = norm(cross(Q2-Q1,P-Q1))/norm(Q2-Q1);
>
> and finally, as a check, directly compute the nearest
point, R, on line Q1Q2
> and then compute its distance from P:
>
> R = (dot(P-Q2,Q1-Q2)*Q1+dot(P-Q1,Q2-Q1)*Q2)/dot(Q2-
Q1,Q2-Q1);
> d3 = norm(R-P);
>
> Now compare the answers using 'format long':
>
> [d1;d2;d3]
> ans =
>
> 1.0e-04 *
>
> 0.24494825921622
> 0.24494897427992
> 0.24494897427992
>
> Formula (4) is off in the 7th place while the other two
methods preserve
> normal matlab accuracy.
>
> Roger Stafford
>
>

"Chukwuemeka Igwe" <chukigwe@yahoo.com> wrote in message <ft2m2v
$gf5$1@fred.mathworks.com>...
> Roger,
>
> Does htere exist a similar closed formula for finding the
> nearest distance to a circle with three points specified
> or we may have to apeal to the idea of a langragian
> mulitplier or similar contrivance?
>
> Sincerely,
>
> Chuk.
---------
  The main problem there is to find the center and radius of such a circle.
Once found, the distance you request is merely the absolute difference
between the distance from the given point to the center and the radius of the
circle. There is certainly no need for Lagrange multipliers.

  On the Mathworld website:

 http://mathworld.wolfram.com/Circle.html

there is a solution of the circle problem in equations (28) through (34).

  A method of finding the circle using matlab is the following. Let p1 =
(x1,y1), p2 = (x2,y2), and p3 = (x3,y3) be three points in 2D space, each
represented by a two-element row vector. Then a circle through these three
points has its center at the location given by vector c with radius r as given in
the following:

 t = p2-p1; u = p3-p1; v = p3-p2;
 w = abs(det([t;u]));
 c = p1+(dot(t,t)*dot(u,v)*u-dot(u,u)*dot(t,v)*t)/(2*w^2);
 r = 1/2*norm(t)*norm(u)*norm(v)/w;

Then you can get your required distance as:

 d = abs(norm(P-c)-r);

where P is the given point.

Roger Stafford

Hey, do you know how how you can find out if P is either on
one or the other side of the line.

I ask because i wanna define a so called support polygon which
is defined by 3 points X1, X2, X3 (3 footpoints)
the Point P represents the horizontal projection of the
center of gravity.
The system is called stable if the point P is inside the
support polygon and greater than 0. This means I first start
to check the distances of the perpendicular to the vectors
defined by X1,X2,X3 and than check if they are inside the
polygon(triangle). The should be positive inside and
negative outside

Laurent

if you have a line in the explicit form
y=m*x+q,

then if Py > m*Px+q
you are above the line, otherwise you are below...

Ale
--
Alessandro Mura
Istituto Nazionale di Astrofisica - IFSI
http://pptt4.ifsi-roma.inaf.it/~mura/index.html

"alessandro mura" <fake@address.com> wrote in message
<fukr2u$lil$1@aioe.org>...
> if you have a line in the explicit form
> y=m*x+q,
>
> then if Py > m*Px+q
> you are above the line, otherwise you are below...

too bad when the line is vertical...

"Laurent Huberty" <hubertyl@student.ethz.ch> wrote in message <fukprj$6ih
$1@fred.mathworks.com>...
> Hey, do you know how how you can find out if P is either on
> one or the other side of the line.
>
> I ask because i wanna define a so called support polygon which
> is defined by 3 points X1, X2, X3 (3 footpoints)
> the Point P represents the horizontal projection of the
> center of gravity.
> The system is called stable if the point P is inside the
> support polygon and greater than 0. This means I first start
> to check the distances of the perpendicular to the vectors
> defined by X1,X2,X3 and than check if they are inside the
> polygon(triangle). The should be positive inside and
> negative outside
>
> Laurent
-------------
  The point P = (x,y) lies inside triangle ABC, where A = (x1,y1), B = (x2,y2),
and C = (x3,y3) if

 det([1 x y;1 x1 y1;1 x2 y2]),

 det([1 x y;1 x2 y2;1 x3 y3]), and

 det([1 x y;1 x3 y3;1 x1 y1])

all have the same sign. Otherwise it lies outside.

Roger Stafford

>> you are above the line, otherwise you are below...
>
> too bad when the line is vertical...
>

just use the other explicit form
x=m2* y+q2

in this case....:-)



Ale



--
Alessandro Mura
Istituto Nazionale di Astrofisica - IFSI
http://pptt4.ifsi-roma.inaf.it/~mura/index.html

"alessandro mura" <fake@address.com> wrote in message <fulhq1$osq
$1@aioe.org>...
> >> you are above the line, otherwise you are below...
> > too bad when the line is vertical...
> just use the other explicit form
> x=m2* y+q2
> in this case....:-)
> Ale
---------
  It's much easier to test the sign of det([1 x y;1 x1 y1;1 x2 y2]). That doesn't
require testing for vertical or horizontal cases.

Roger Stafford