2D lines intersection
Author
For ex. I have 2 lines in 2D, Line1 (x1,y1)-(x2,y2) and Line2(a1,b1)-(a2,b2)
how do I know if those two intersect ?? I''m trying to apply this so that I know if for ex. wether a movement will cross a line or not, and I mean crossing and not colliding..
thx..
This is a really simple problem. Look at Googles. You have to solve the line equations to find the collision point of the two lines (when they are prolonged to infinity) and then check if the point is part of both line by finding its t with these equations:
x = x0 + (x1 - x0) * t
y = y0 + (y1 - y0) * t
If 0 < t < 1 for a given point, then the point is part of the line.
I know my answer is pretty general, but look at the ressources around you. A lot of people recommend MathWorld and I know Dr.Math is pretty good, especially for geometry.
Cédric
[edited by - cedricl on May 6, 2002 7:57:49 PM]
x = x0 + (x1 - x0) * t
y = y0 + (y1 - y0) * t
If 0 < t < 1 for a given point, then the point is part of the line.
I know my answer is pretty general, but look at the ressources around you. A lot of people recommend MathWorld and I know Dr.Math is pretty good, especially for geometry.
Cédric
[edited by - cedricl on May 6, 2002 7:57:49 PM]
If you let da=(a2-a1), db=(b2-b1), dx=(x2-x1) and dy=(y2-y1) then t in the above equation for the point of intersection would be (da*(b1-y1)-db*(a1-x1))/(dy*da-db*dx). If the denominator is zero then your lines are parallel and the lines either overlap or do not intersect. If the numerator is same sign as the denominator and the numerator is smaller than the denominator then 0<=t<=1 in which case your line segments intersect. If you want to know where they intersect then calculate t and plug it into the above equation. If t is negative or greater than 1 the lines intersect, but the line segments do not.
Just curious, but after we find the intersection point, can we create 2D bounding boxes for the segments, and then check to see if the intersection point is contained within both bounding boxes? I''m just wondering if that''s a plausable way of detecting if the intersection point is on both segments. I''m thinking yes, but it might take longer.
I would say that it''s a good way because it allows vertical and horizontal lines to be treated easily, whereas when trying to find the t of a point on the line, you have to check the slope to make sure that it''s not 0.
y = 5t + 2
x = 0t + 3
It doesn''t make a big difference IMO.
Cédric
y = 5t + 2
x = 0t + 3
It doesn''t make a big difference IMO.
Cédric
You lost me there. Is that t a typo? With parametric equations you have to check that the lines are not parallel. It doesn''t matter what the "slope" is as long as it isn''t the same for both. If they are parallel then you have to check if they are the same line. If they are the same line then you can use zipsters method to find the segment common to both segments if any.
That t wasn't a typo. I was talking about the method to find if point P is part of both line segments. What I meant is that Zipster's method looks like:
find intersection of lines P
if(P.x > segment1.x1 && P.x < segment1.x2 && P.y > segment1.y1 && P.y < segment.y2 && ... same for segment2
as opposed to
if(segment1.x1 - segment1.x2 != 0) then
t = x / (x2 - x1)
else
t = y / (y2 - y1)
... same for segment2
Anyway, that's how I envision both solutions. I think Zipster's approach (if I understand it correctly) is simpler than finding the t because there is no special case if segment.x1 == segment.x2. In fact, the bounding box would work with points whereas the parametric approach would require yet another test to avoid a null division.
Of course, if finding the intersection point involves finding the t, then there is no point in doing all this.
Cédric
[edited by - cedricl on May 13, 2002 7:25:19 PM]
find intersection of lines P
if(P.x > segment1.x1 && P.x < segment1.x2 && P.y > segment1.y1 && P.y < segment.y2 && ... same for segment2
as opposed to
if(segment1.x1 - segment1.x2 != 0) then
t = x / (x2 - x1)
else
t = y / (y2 - y1)
... same for segment2
Anyway, that's how I envision both solutions. I think Zipster's approach (if I understand it correctly) is simpler than finding the t because there is no special case if segment.x1 == segment.x2. In fact, the bounding box would work with points whereas the parametric approach would require yet another test to avoid a null division.
Of course, if finding the intersection point involves finding the t, then there is no point in doing all this.
Cédric
[edited by - cedricl on May 13, 2002 7:25:19 PM]
Ok, I think I follow. If you found the intersection of the bounding boxes then clipped the segments to that intersection you could tell if the lines intersect. If the ends of both segments are corners of the intersection then they intersect. The center of the intersection is one point of intersection for the segments. If they connect the same corners then there is more than one point of intersection, both clipped segments are the same and represent the overlap between the segments. I think that would take some creativity to say the least to get that faster than seven subtractions, four multiplications, one compare/branch and one divide.
That's not what I wrote 
. Come on, LilBudyWizer, it's really dumb: if you already know that P is on the line of segment1, then P is on segment1 if and only if P is part of the bounding box of segment1.
Is this faster than finding t? I have no idea.
Cédric
P.S.: I didn't want to be mean/condescending; your posts are great and I'm just surprised that we have troubles understanding each other.
[edited by - cedricl on May 14, 2002 8:42:50 AM]
. Come on, LilBudyWizer, it's really dumb: if you already know that P is on the line of segment1, then P is on segment1 if and only if P is part of the bounding box of segment1.Is this faster than finding t? I have no idea.
Cédric
P.S.: I didn't want to be mean/condescending; your posts are great and I'm just surprised that we have troubles understanding each other.
[edited by - cedricl on May 14, 2002 8:42:50 AM]
Just because it sounds like I''m responding to your post does that mean I actually am 
See, that is what confuses you is that I just throw out ideas that I think might have potential, but that I don''t feel like running with.
See, that is what confuses you is that I just throw out ideas that I think might have potential, but that I don''t feel like running with.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
