PDA

View Full Version : intersection of 2 lines



A027298
06-21-2002, 03:46 AM
Freax,

Does anybody of yous know a very fast way, to determine, if 2 lines (x1y1x2y2, x3y3x4y4) intersect (in 2D)? I'd appreciate it.

Quaternion
06-21-2002, 04:00 AM
two lines or two segments?

if you really meant lines, then if their slopes aren't equal they intersect.

if you meant segments (probably) then I don't know a better way than calculating the intersection point and then check if it on the segments.

A027298
06-21-2002, 04:09 AM
I meant two segments:

1st segment: (x1, y1) (x2, y2)
2nd segment: (x3, y3) (x4, y4)

Algorithm to determine, if those segments intersecht.

I have a solution for this, but it seems to be pretty slow.

Won
06-21-2002, 05:36 AM
Here's the first thing that popped into my head. I don't even know if it's correct, but it's the morning and I'm feeling lazy.

I think you can use a dot product to figure out which side a point is on a line. Then, for segment A, figure out where the endpoints
lie for segment B. If the segments are on oppposite sides, do the same thing with the roles reversed. I think that would yield the correct results, but you might need to handle the degenerate case where one or both of the segments of B are colinear with A or vice versa.

To do the dot product thing, say you have a segment (x1, y1) -> (x2, y2) and a point x3 y3. compute (x2-x1, y2-y1) dot (x3-x1, y3-y1) and look at the sign. I bet you can do this bloody fast on an MMX unit, because you can probably do a bunch of tests in parallel and even avoid all the conditionals.

-Won

Michael Steinberg
06-21-2002, 06:31 AM
Won, that is as it is incorrect. The lines need to be seen as planes intersecting the x,y plane in the line. And then take the normals of these planes (direction doesnt matter obviously).

Won
06-21-2002, 08:09 AM
You are correct, of course. It totally slipped my mind. The equation I have written for the dot product should be:

(y1-y2, x2-x1) dot (x3-x1, y3-y1)

(x2-x1, y2-y1) gives a vector parallel to the segment instead of perpendicular to it.

-Won

PS is it just me or are some Fridays as bad as Mondays?

A027298
06-21-2002, 08:24 AM
@Won: I do not have a segment and a point, I have 2 segments and I want to check, if those segments intersect or not. If they intersect I don't need to now where they intersect. I need a function like that:

bool intersect(Seg a, Seg b) {
// return true if they intersect,
// otherwise false
}

~A027298

Michael Steinberg
06-21-2002, 08:31 AM
What won wrote was totally correct, and it doesnt yield the point of intersection. The segments are built by two points or am i totally mistaken? So his way will work out.

Won
06-21-2002, 08:53 AM
So Fridays are as bad as Mondays, Mike? http://www.opengl.org/discussion_boards/ubb/smile.gif

A027298 (how did you pick that handle, anyway?): you need to look at both my posts. The second was a correction to the first.

Here it is again...

Say you have two segments A and B. You look at the endpoints of B. If they are on opposite sides of A, the check the endpoints of A against B. If both are true, then the segments intersect.

The general way to see what side of a line (hyperplane) a point lies on is with a dot product against the normal of the line (hyperplane). I describe this in my above post.

Good luck, Won

A027298
06-21-2002, 10:50 AM
Thanks Won, now I got it, have a good one.

TGIW!!!!!!!!!!!!