Beginner math question
Author
I need to efficiently find the intersection point of two line segments. I understand that this is a simple problem, and I've seen solutions online that are explained above my level. I'm really trying to really understand this, though.
In my mind, it makes sense to find the equation of each segment (as if it were an infinitely-extending line), then... what? At the end, I'd take the intersection point (if one exists) and test to see if it resides on one of the two segments (just by seeing if its 'x' was in the correct range. This function will be used hundreds/thousands of times each frame, so I want it to be reasonably quick. I want to try to avoid using sin/cos... not because of speed issues, but because I want to eliminate the use of floats.
//segment 1
s1.x1, s1.y1 = 0, 0
s1.x2, s1.y2 = 5, 5
//segment 2
s2.x1, s2.y1 = 1, 0
s2.x2, s2.y2 = 2, 5
//slope 1
m1 = (s1.y1 - s1.y2 ) / (s1.x1 - s1.x2)
//slope 2
m2 = (s2.y1 - s1.y2 ) / (s2.x1 - s2.x2)
//y-intercept 1
b1 = m1 * s1.x1 - s1.y1
//y-intercept 2
b2 = m2 * s2.x1 - s2.y1
//y = m * x + b, so x = (y - b) / m
//sooooo we need to find where (y1 - b1) / m1 = (y2 - b2) / m2... how?
Do you understand the parametric equation of a line? ie.
X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2-Y1)
or better yet:
l(t) = OP + t*U
If so, I can help explain it. Otherwise, I won't be much help.
X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2-Y1)
or better yet:
l(t) = OP + t*U
If so, I can help explain it. Otherwise, I won't be much help.
Quote:Original post by 020644
In my mind, it makes sense to find the equation of each segment (as if it were an infinitely-extending line), then... what?
First, understand that two (doubly-infinite) lines will intersect in one of three ways:
1. Never. In the two-dimensional case, this corresponds to parallel, but distinct lines.
2. Exactly once. The general case.
3. Infinitely many times. This is where the two lines are equal.
Spend as long as it takes to convince yourself that there are no other possibilities. Now, given your example, you test to see which of the three it is. Only case (2) gives a well-defined answer. Given this, we solve for the parameters of each line, at the intersection. All that remains is to check that each of the parameters is within the bounds of the definition of the line-segments.
In summary, the line-segments intersect at a point if and only if their corresponding lines do, and that both of the parameters are within range at the point of intersection. Be aware that the cases with a vertical (or near-vertical) line will require special treatment.
The problem can be simplified by transforming the frame-of-reference so that one line lies along the x-axis, but this will involve some trigonometry.
Quote:I want to try to avoid using sin/cos... not because of speed issues, but because I want to eliminate the use of floats.
This is a bad idea. You'll find it very difficult to represent the gradient of the lines without using decimal numbers (floating-point or otherwise).
Author
gekko:
After poking around online, I think I somewhat understand parametric equations. It's a way of defining the 'x' and 'y' of a graph in terms of time, instead of defining the 'y' in terms of 'x'.
I also understand your first example...
X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2-Y1)
...even though it seems like a longer line would seem to be moving "faster". Would that be an issue.
I don't understand your second example, however. Also, using parametric equations (which seem nifty), I still have to find the point-of-intersection knowing the line's formula, which still seems difficult.
Knowing the slope and y-intercept, I can find out whether the lines are parallel, the same, or could intersect once. I still don't understand how to solve for the intersection point.
I'm sorry for being so dense!!
After poking around online, I think I somewhat understand parametric equations. It's a way of defining the 'x' and 'y' of a graph in terms of time, instead of defining the 'y' in terms of 'x'.
I also understand your first example...
X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2-Y1)
...even though it seems like a longer line would seem to be moving "faster". Would that be an issue.
I don't understand your second example, however. Also, using parametric equations (which seem nifty), I still have to find the point-of-intersection knowing the line's formula, which still seems difficult.
Quote:Original post by TheAdmiralQuote:Original post by 020644
In my mind, it makes sense to find the equation of each segment (as if it were an infinitely-extending line), then... what?
First, understand that two (doubly-infinite) lines will intersect in one of three ways:
1. Never. In the two-dimensional case, this corresponds to parallel, but distinct lines.
2. Exactly once. The general case.
3. Infinitely many times. This is where the two lines are equal.
Spend as long as it takes to convince yourself that there are no other possibilities. Now, given your example, you test to see which of the three it is. Only case (2) gives a well-defined answer. Given this, we solve for the parameters of each line, at the intersection. All that remains is to check that each of the parameters is within the bounds of the definition of the line-segments.
In summary, the line-segments intersect at a point if and only if their corresponding lines do, and that both of the parameters are within range at the point of intersection. Be aware that the cases with a vertical (or near-vertical) line will require special treatment.
The problem can be simplified by transforming the frame-of-reference so that one line lies along the x-axis, but this will involve some trigonometry.Quote:I want to try to avoid using sin/cos... not because of speed issues, but because I want to eliminate the use of floats.
This is a bad idea. You'll find it very difficult to represent the gradient of the lines without using decimal numbers (floating-point or otherwise).
Knowing the slope and y-intercept, I can find out whether the lines are parallel, the same, or could intersect once. I still don't understand how to solve for the intersection point.
I'm sorry for being so dense!!
There is a really easy way to compute the intersection point of two 2D lines when you use homogeneous coordinates for the line.
Basically each 2D line can be defined with the following equation
ax + by + c = 0
Where a, b and c are the three parameters. The vector (a, b)T can be interpreted as the normal vector onto the line and c is the slope intercept. You can take those three parameters as a 3d vector (a, b, c)T.
The intersection point (again in homogenous coordinates) is then simply the 3d cross product between the two 3-vectors describing the line. This will yield another 3-vector (xw, yw, w)T. To get the actual 2d point you would have to divide xw and yw by w. This of course only works if w != 0, in which case there is no intersection. If all three of xw, yw and w are 0 then the lines were identical in the first place.
If you have two points on the line and want to compute the three homogenous parameters for the line connecting then you can also use the cross product:
(p1x, p1y, 1)T x (p2x, p2y, 1)T where p1x, p1y and p2x and p2y are the coordinates of the first and second point, respectively, will give you the homogeneous equation for the line.
The really nice thing when working in homogeneous coordinates is that you need a lot fewer conditionals.
Basically each 2D line can be defined with the following equation
ax + by + c = 0
Where a, b and c are the three parameters. The vector (a, b)T can be interpreted as the normal vector onto the line and c is the slope intercept. You can take those three parameters as a 3d vector (a, b, c)T.
The intersection point (again in homogenous coordinates) is then simply the 3d cross product between the two 3-vectors describing the line. This will yield another 3-vector (xw, yw, w)T. To get the actual 2d point you would have to divide xw and yw by w. This of course only works if w != 0, in which case there is no intersection. If all three of xw, yw and w are 0 then the lines were identical in the first place.
If you have two points on the line and want to compute the three homogenous parameters for the line connecting then you can also use the cross product:
(p1x, p1y, 1)T x (p2x, p2y, 1)T where p1x, p1y and p2x and p2y are the coordinates of the first and second point, respectively, will give you the homogeneous equation for the line.
The really nice thing when working in homogeneous coordinates is that you need a lot fewer conditionals.
Quote:Original post by 020644
gekko:
After poking around online, I think I somewhat understand parametric equations. It's a way of defining the 'x' and 'y' of a graph in terms of time, instead of defining the 'y' in terms of 'x'.
I also understand your first example...
X = X1 + t * (X2 - X1)
Y = Y1 + t * (Y2-Y1)
...even though it seems like a longer line would seem to be moving "faster". Would that be an issue.
I don't understand your second example, however. Also, using parametric equations (which seem nifty), I still have to find the point-of-intersection knowing the line's formula, which still seems difficult.
I was really hoping you would understand the second example.
l(t) = OP + t*U
It's a line (l), in vector form, with respect to t. OP is any point on a line, and U is a vector on the line. Plug in any value you want for t and you'll get another point on the line. If you look at my first example, it's actually the same thing.
l(t) |X1| + t * |X2-X1|
|Y1| |Y2-Y1|
Now use your imagination and imagine my vertical bars as big parentheses. Read across the top and you have your X, and the bottom for your Y.
OP is the starting point point (X1, Y1) and U is the vector that goes from the starting point of the line segment to the ending point (expressed as a position vector). It works really well in this case because when t = 0, you get the starting point, and when t = 1, you get the ending point. Therefore, you can determine the intersection of the whole line, and if 0 <= t <= 1 and 0 <= s <= 1, the segments intersect.
It's just a matter of solving for s and t. If they both are between 0 and 1, you can get the point by simply plugging in the value for s or t back into the equation (they'll both give the same point).
But I'm guessing you don't want to get into vectors, so this probably won't help.
trenki, your effort is applauded. However based on reading 020644's post I suspect he is not ready for cross products, vectors or homogeneous coordinates. A bit overkill. Also it looks like he is interested in segment intersection.
- 020644
To test if the segments intersect I would start as you did, find the line equations of the two lines from the four points. So find the slope of the line defined by first two points and then second two points.
Now that you have that you have solved for slope1 and slope2 you need to check if both lines intersect. Get the intercept as you do (change the signs e.g. b1 = m1 * - s1.x1 + s1.y1).
You can then check if they intersect at x = b2-b1/m1-m2. Be sure to check that m2 - m1 <> 0 else they are parallel.
A parametric equation of a line is given by:
x = x1 + t(x2 -x1) , y = y1 + t(y2 - y1) where t acts as a kind of slider of the point (x,y).
Since you have x1, x and x2 you can solve for t and check if t is between 0 and 1 on both lines (use the original 4 points to define the x1, y1,y2, etc.) If it is then you have an intersection, like gekko said.
So the psuedo code written for clarity is
So for your example they do intersect and at (1.25, 1.25) and both have t = 0.25
Also it may interest you that although you cant draw two parallel (same slope) lines that intersect on say a flat sheet of paper you can do so on a saddle or on a ball.
[Edited by - Daerax on November 26, 2007 12:05:42 AM]
- 020644
To test if the segments intersect I would start as you did, find the line equations of the two lines from the four points. So find the slope of the line defined by first two points and then second two points.
Now that you have that you have solved for slope1 and slope2 you need to check if both lines intersect. Get the intercept as you do (change the signs e.g. b1 = m1 * - s1.x1 + s1.y1).
You can then check if they intersect at x = b2-b1/m1-m2. Be sure to check that m2 - m1 <> 0 else they are parallel.
A parametric equation of a line is given by:
x = x1 + t(x2 -x1) , y = y1 + t(y2 - y1) where t acts as a kind of slider of the point (x,y).
Since you have x1, x and x2 you can solve for t and check if t is between 0 and 1 on both lines (use the original 4 points to define the x1, y1,y2, etc.) If it is then you have an intersection, like gekko said.
So the psuedo code written for clarity is
line_eq (x1,y1) (x2,y2) = (m, m * -x1 + y1) where slope (x1,y1) (x2,y2) = (y2 - y1) / (x2 - x1) m = slope (x1,y1) (x2,y2)intersect (x1,y1) (x2,y2) (x3,y3) (x4,y4) = (x,y) where line1 = line_eq (x1,y1) (x2,y2) line2 = line_eq (x3,y3) (x4,y4) m1 = fst line1 b1 = snd line1 m2 = fst line2 b2 = snd line2 x = (b2 - b1) / (m1 - m2) y = m1 * x + b1t_val (x1,y1) (x2,y2) (x3,y3) (x4,y4) = ((x - x1) / (x2 - x1),(x - x3) / (x4 - x3)) where x = fst (intersect (x1,y1) (x2,y2) (x3,y3) (x4,y4))seg_intersect (x1,y1) (x2,y2) (x3,y3) (x4,y4) = (t_val1 >= 0 && t_val1 <= 1) && (t_val2 >= 0 && t_val2 <= 1) where t = t_val (x1,y1) (x2,y2) (x3,y3) (x4,y4) t_val1 = fst t t_val2 = snd tSo for your example they do intersect and at (1.25, 1.25) and both have t = 0.25
Also it may interest you that although you cant draw two parallel (same slope) lines that intersect on say a flat sheet of paper you can do so on a saddle or on a ball.
[Edited by - Daerax on November 26, 2007 12:05:42 AM]
Author
First of all, I've bookmarked this thread (as well as several online math resources), and rated up everyone as high as I could. I need to learn this stuff, and I will continue to do so.
However, while planning my project, I realized that every intersection-test involved at least one line that is either perpendicular to the x- or y-axis, which makes finding the intersection trivial! I'm glad I made that mistake, though, because it inspired me to learn this and to take some math classes that I otherwise wouldn't have taken.
Thanks for the help, everyone!
However, while planning my project, I realized that every intersection-test involved at least one line that is either perpendicular to the x- or y-axis, which makes finding the intersection trivial! I'm glad I made that mistake, though, because it inspired me to learn this and to take some math classes that I otherwise wouldn't have taken.
Thanks for the help, everyone!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
