y = mx + c
this is called the explicit form, v well known.
it says that any Y point is calculated from the X point. (explicit, distinctly stated.)
Ax + By + c = 0
this is called the implicit form, not v well known
it says that a line is all the (x,y)'s that are no distance away from this equation. you run your (x,y) through, and if it is 0 dist away, then that implies that it is part of the line.
Ax + By + c = 0
A,B,C are constants, so can be pre-calced
A = -Sin(theta)
B = Cos(theta)
C = X1Sin(theta) - Y1Cos(theta)
theta is the angle the line makes with x axis
(x1,y1) is any point on line.
note:
C = -1 * ( A.X1 + B.Y1)
which may help.
so now you have calculated your A,B,C for each line, the distance from the line is just
dist = A.x + B.y + C
man, what a messy post. shoulda just left you this url:
http://geometryalgorithms.com/algorithms.htm
i think its in february; oh, and careful, because their sin(theta) looks a bit funny, font probs.
Explicit also means Clear
Implicit also means entangled
hope it helps,
Fatray
[edited by - fatray on September 15, 2002 11:45:56 AM]
Distance between point and line
You can edit your posts and remove them (check the checkbox at the top).
To expand upon FatRay''s post, if you have a line of equation
y = ax + b
where a is the slope of the line. You can modify it to obtain the ''implicit'' form
ax - y + b = 0
Notice that the coefficients of x and y form the direction vector of the line. In this case, it is (a, -1). You have to normalize these coefficients, by dividing them by the length of the vector:
length = sqrt(a² + (-1)²) = sqrt(a² + 1)
now, we just divide both sides of the equation by length
(a / length) * x + (-1 / length) * y + (b / length) = 0
To simplify,
A = a / length
B = -1 / length
C = b / length
Ax + By + C = 0
Now, we have the distance formula right away: for any point (x,y)
Ax + By + C = distance
It''s a signed distance (it''s positive on one side of the line and negative on the other). Use the absolute value to remove this effect.
My post was probably unnecessarily lengthy, but it''s a really simple technique overall, and it''s faster than Graham''s method, AFAIK.
Cédric
To expand upon FatRay''s post, if you have a line of equation
y = ax + b
where a is the slope of the line. You can modify it to obtain the ''implicit'' form
ax - y + b = 0
Notice that the coefficients of x and y form the direction vector of the line. In this case, it is (a, -1). You have to normalize these coefficients, by dividing them by the length of the vector:
length = sqrt(a² + (-1)²) = sqrt(a² + 1)
now, we just divide both sides of the equation by length
(a / length) * x + (-1 / length) * y + (b / length) = 0
To simplify,
A = a / length
B = -1 / length
C = b / length
Ax + By + C = 0
Now, we have the distance formula right away: for any point (x,y)
Ax + By + C = distance
It''s a signed distance (it''s positive on one side of the line and negative on the other). Use the absolute value to remove this effect.
My post was probably unnecessarily lengthy, but it''s a really simple technique overall, and it''s faster than Graham''s method, AFAIK.
Cédric
quote:Original post by 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 .
Er, what? You think that performing a cross product then a division is faster than what Grahame wrote?
Ok, lets see...
Your method:
Calculating cross product: 6 multiplications, 4 subtractions 1 addition.
Dividing magnetude of result by magnetude of base: 6 multiplications, 4 additions, 2 square roots, and a division.
So, overall, your method costs: 12 multiplications, 1 division, 2 square roots, 4 subtractions and 5 additions.
Grahames method:
Calculating line direction: 3 subtractions, 1 square root, 3 multiplications, 3 additions and one division.
Calculating AP: 3 subtractions.
AP_Parallel_to_line: 6 multiplications, 2 additions. AP_normal_to_line: 3 subtractions.
Actual distance: 1 square root, 3 multiplications, 2 additions.
So, overall: 2 square roots, 12 multiplications, 1 division, 9 subtractions, 7 additions.
Ok... Perhaps you method is actually faster after all... Though there will be absolutely *no* descernable difference between the two anyway.
Death of one is a tragedy, death of a million is just a statistic.
Lol, thanks Cedricl, i was just re-reading my link and expanding my post, when you did.
its a good technique, because it looks quite tidy, and deals with vertical and horizontal lines easily, which is why i started to use it.
oh and its cheap, Two Mults and Two Adds for each distance calc.
thats gotta be worth storing three consts...
there's even some code at the bottom:
http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm#Lines
fatray
[edited by - fatray on September 15, 2002 11:59:07 AM]
its a good technique, because it looks quite tidy, and deals with vertical and horizontal lines easily, which is why i started to use it.
oh and its cheap, Two Mults and Two Adds for each distance calc.
thats gotta be worth storing three consts...
there's even some code at the bottom:
http://geometryalgorithms.com/Archive/algorithm_0102/algorithm_0102.htm#Lines
fatray
[edited by - fatray on September 15, 2002 11:59:07 AM]
quote:Original post by Anonymous Poster
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.
That''s actually a pretty clever solution!
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
