distance between point and line segment
Steve
a point? I'm looking for the 2D case specifically, but the more
general 3D case would also be nice to know...
Thanks.
-Steve
Roger Stafford
c21e-4ebf-853...@41g2000hsc.googlegroups.com>...
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
Chukwuemeka Igwe
<ellieandr...@mindspring.com.invalid> wrote in
message <fpdqru$8lg$1...@fred.mathworks.com>...> c21e-4ebf-8530-
352f15...@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
>
This fromual needs that the point be specified for the z
axis.
Do you use z= 0 or z =1?
Chuk
Chukwuemeka Igwe
<ellieandr...@mindspring.com.invalid> wrote in
message <fpdqru$8lg$1...@fred.mathworks.com>...
352f15...@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
on the same side or oposite sides of the line?
Thanks for your help
Chuk
Roger Stafford
$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
ImageAnalyst
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
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 <imagea...@mailinator.com> wrote in
message <d122bed7-41d5-446a-8b0a-
e786bd...@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,
Roger Stafford
$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
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"
<ellieandr...@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1...@fred.mathworks.com>...
Chukwuemeka Igwe
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"
<ellieandr...@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1...@fred.mathworks.com>...
Chukwuemeka Igwe
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"
<ellieandr...@mindspring.com.invalid> wrote in
message <fsrvq5$5cu$1...@fred.mathworks.com>...
Roger Stafford
$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
Laurent Huberty
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
alessandro mura
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
John D'Errico
<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...
Roger Stafford
$1...@fred.mathworks.com>...
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
alessandro mura
>> 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....:-)
Roger Stafford
$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
Grzegorz Knor
> "Chukwuemeka Igwe" <chuk...@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.
Question was about distance between point and line segment, not between point and line.
Solution could be as follows:
=============================
x1 = Q1(1);
y1 = Q1(2);
x2 = Q2(1);
y2 = Q2(2);
x0 = P(1);
y0 = P(2);
if (min(x1,x2)<=x0 && max(x1,x2)>=x0) || (min(y1,y2)<=y0 && max(y1,y2)>=y0)
% if point is in "range" of line segment
d = abs((x2-x1)*(y1-y0)-(x1-x0)*(y2-y1))/sqrt((x2-x1)^2+(y2-y1)^2);
else
d = min(sqrt((x2-x0)^2+(y2-y0)^2),sqrt((x1-x0)^2+(y1-y0)^2));
end
=============================
And my question is how to vectorize this code? Suppose that I have one line segment and n points. I can use loop or arrayfun, but is there another way to do this?
best regards
Grzegorz
Grzegorz Knor
======================================
x1 = 1;
y1 = 2;
x2 = 2;
y2 = 3;
line([x1 x2],[y1 y2],'Color','k')
P = rand(100,2)*4;
x0 = P(:,1);
y0 = P(:,2);
hold on
plot(x0,y0,'.')
idx = (min(x1,x2)<=x0 & max(x1,x2)>=x0) | (min(y1,y2)<=y0 & max(y1,y2)>=y0);
d = zeros(size(x0));
d(idx) = abs((x2-x1).*(y1-y0(idx))-(x1-x0(idx)).*(y2-y1))./sqrt((x2-x1).^2+(y2-y1).^2);
d(~idx) = min(sqrt((x2-x0(~idx)).^2+(y2-y0(~idx)).^2),sqrt((x1-x0(~idx)).^2+(y1-y0(~idx)).^2));
======================================
Somebody have better idea?
Grzegorz
Andres Acosta
Hey Roger and everybody. I think the answer to this question is trivial but i just want to be sure: i'd like to find not just the distance between the point and the line, but also the vector perpendicular to the line AND collinear to the point.
Regards
Andres Acosta
I have to specify that that i mean the 2D case
Roger Stafford
> Question was about distance between point and line segment, not between point and line.
> Solution could be as follows:
> =============================
> x1 = Q1(1);
> y1 = Q1(2);
> x2 = Q2(1);
> y2 = Q2(2);
> x0 = P(1);
> y0 = P(2);
>
> if (min(x1,x2)<=x0 && max(x1,x2)>=x0) || (min(y1,y2)<=y0 && max(y1,y2)>=y0)
> % if point is in "range" of line segment
> d = abs((x2-x1)*(y1-y0)-(x1-x0)*(y2-y1))/sqrt((x2-x1)^2+(y2-y1)^2);
> else
> d = min(sqrt((x2-x0)^2+(y2-y0)^2),sqrt((x1-x0)^2+(y1-y0)^2));
> end
> =============================
>
> And my question is how to vectorize this code? Suppose that I have one line segment and n points. I can use loop or arrayfun, but is there another way to do this?
>
> best regards
> Grzegorz
Grzegorz, you are correct that the original request in this thread was for the distance from a point to a line segment. Apparently no-one in the thread picked up on this.
However, the method you have proposed to do so is incorrect. It selects a region consisting of crossed vertical and horizontal bands as being that for the use of the point-to-line distance formula, but that isn't the one that should be used. What you need are two parallel lines orthogonal to the line segment and passing through the two respective endpoints. The area between these lines is that in which the point-to-line orthogonal distance formula should be used. Outside these lines the distance should be that between the point and the corresponding line segment endpoint.
This would be accomplished by (using your notation):
if (x2-x1)*(x0-x1)+(y2-y1)*(y0-y1) >= 0
if (x2-x1)*(x0-x2)+(y2-y1)*(y0-y2) <= 0 % P is between the lines
d = abs((x2-x1)*(y0-y1)-(y2-y1)*(x0-x1))/sqrt((x2-x1)^2+(y2-y1)^2);
else % P is outside on the Q2 side
d = sqrt((x0-x2)^2+(y0-y2)^2);
end
else % P is outside on the Q1 side
d = sqrt((x0-x1)^2+(y0-y1)^2);
end
where the three 'd' values are the same as your values but the "if" expressions are different.
(Note: I think this problem has been discussed many times before in this group.)
Roger Stafford
Roger Stafford
>
> Regards
Using Q1 = [x1,y1] and Q2 = [x2,y2] for the segment endpoints and P0 = [x0,y0] for the third point to be projected orthogonally onto the segment, do this:
V = ((x2-x1)*(y0-y1)-(y2-y1)*(x0-x1))/((x2-x1)^2+(y2-y1)^2) * ...
[(y2-y1),-(x2-x1)];
P = [x0,y0] + V; x = P(1); y = P(2);
Then V will be the vector pointing orthogonally from P0 to the point P = [x,y] on the (extended) line of the segment. The length (norm) of V will be the orthogonal distance of P0 from the line.
Note that this is an orthogonal projection onto the extended line of the segment, and the point P will always lie on the line but could fall outside the segment portion.
Roger Stafford
Matthew
this is exactly what i need to do, but in 3D. how can i modify it? ANy thoughts?
Achim Schweikard
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Distance between a point and a line, line given by two points u and v
% u is a point on the line, and v is the direction vector of the line
% i.e. l = u + lambda*v
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function d = point_to_line(a, u, v)
lambda0 = ((a -u) * v') / (v * v');
d = (a - u - lambda0*v)*(a - u - lambda0*v)';
end
Work in any dimension.
"Roger Stafford" wrote in message <fsrvq5$5cu$1...@fred.mathworks.com>...