Archived

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

yanuart

2D lines intersection

Recommended Posts

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..

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Well, you have eight comparisons using the bouding box method. The conditional-AND (&&) can be changed to the bitwise-AND(&) (I think that gives you a millionth of a second or two). I can''t tell you how much faster it would be unless I were to profile it. Programmers are inherently lazy, so you will understand if I don''t profile

Share this post


Link to post
Share on other sites