Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

CutterSlade

Distance between point and line

This topic is 5754 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This will sound REAL stupid, but I just can´t remember: what is the formula to find the distance between a point and a line, given the 2 coordinates of the point, and two points of the line (or the linear equation)?

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
the distance between two points:

square root of [ (x1-x2)^2+(y1-y2)^2 ]

Share this post


Link to post
Share on other sites
Anonymous Poster''s answer isn''t actually unrelated. If you don''t care that the distance you calculate is the closest distance from the point to the line, then just find the distance between the point and one of the points on the line. That is a distance from the point to the line.

If, on the other hand, you want the closest distance, you have to do some more complex geometry. Here you go.

If the line is from A to B, and the point is P, then do this:

line_direction = AB = (B-A)/length(B-A)

Let,

AP = P - A

The component of AP that lies along the line is:

AP_parallel_to_line = AB*dotproduct(AP, AB)

Now, find the component of AP that is normal to the line:

AP_normal_to_line = AP - AP_parallel_to_line

The closest distance is simply the length of AP_normal_to_line.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
i don''t really know the theory behind it, but i have some code. which i didn''t write, obviously! magic-software (.com) did (they rock! ).

right here, at the top. or directly here.

hope that helps you.

---
shurcool
wwdev

Share this post


Link to post
Share on other sites
In 2D, there is an easier solution, with the general equation of the line:

Ax + By + C = 0 for any point on the line

Ax + By + C = distance for points around the line (if A² + B² = 1)

Short post because you probably mean 3D.

Cédric

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well, so far I have seen 1 1/2 correct ways of doing this, when there are at least 2 that I know of. grhodes_at_work pegged the DOT product method of finding the distance which also spits out the closest point on the line (well, actually a t value that you can use to find the closest point and find the distance between them).

A faster way (CPU wise) is to use a Cross product method, which spits out the distance (and that''s it). It doesn''t actually give you the point, but there are less steps and cycles involved.

The CROSS product not only gives you vector normal to both on the vectors inputted, but the magnitude of the resultant vector is the area of the parallelogram shaped by the vectors that where used. Divide the magnitude by the base (line segment) and you will get the height (distance) from the point to the line.

If you plan to use the prewritten functions: Remember the difference in speeds and choose the algorithym that best fits your needs .

Share this post


Link to post
Share on other sites
Actually, I''m doing this in 2D, it''s just that the Dot-Product method worked, but now that I see your Cedric, I think it may be better for what I need Could you explain it a little better (what do you mean by A^2 + B^2 = 1?)
Thanks in advance

Share this post


Link to post
Share on other sites
Wow, sorry about my triple-post, my connection is freaking out!

[grhodes_at_work: I deleted the 2 extra posts.]

[edited by - grhodes_at_work on September 16, 2002 3:55:01 PM]

Share this post


Link to post
Share on other sites
I wrote this ones allready, but then my browser wanted to go back and my finished post was gone. Nice.

While back i needed to find shortest distance between a point and a line. I found out that the shortest distance is the same as height of a triangle. I did this with a help of my friend, so if anyone has ideas how to make this faster or has faster function im realy intrested. I need to call this many times in a frame so making this faster would speed up my game seriously.

Anyway here''s the code:
Im sorry but its commented in Finnish and the variable names are in Finnish. It checks the shortest distance between the point (cx, cy) and the line (ax,ay)-(bx,by).


  
double kolmionkorkeus(double ax, double ay, double bx, double by, double cx, double cy) {

/*
C
/ \
/ | \
/____|____\
A B

*/

//pituus = length


double pituusAB, pituusAC, pituusBC;
pituusAB = sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
pituusAC = sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy));
pituusBC = sqrt((bx-cx)*(bx-cx)+(by-cy)*(by-cy));

if ((pituusAB > pituusAC)&&(pituusAB > pituusBC)) {

double korkeus, k1, k2, alfa;

//(ax,ay) - (bx,by) this is the line

//(cx,cy) this is the point

// k1,k2 = kulmakertoimia (i don''t know what this is in english)


k1 = (ay - by) / (ax - bx);
k2 = (cy - ay) / (cx - ax);

alfa = atan((k1 - k2) / (1+ k1*k2));
korkeus = abs(sin(alfa)*pituusAC);


return korkeus;
} else {

if (pituusAC < pituusBC) {
return pituusAC;
} else {
return pituusBC;
}

}

}

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!