Archived

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

Boris Karloff

Do 2 parallel line segments overlap, and where?

Recommended Posts

I''m trying to figure out some basic line-collision stuff, and most of it works pretty well, using the good old y=mx + b equation, where m is the slope and b is the point where the line intersects the y-axis. Anyhoo, all this works out pretty well, except on parallel lines. Now, most texts I''ve found argue that parallel line segments do not intersect. In other words, if the slope of both segments is equal, then the lines are parallel and will never intersect. True, but if the line segments are both part of the -same- infinite line, they might overlap each other. What I want to know is if, and where, that happens. Now, figuring out if two line segments are parallel is easy, as in that case m1 is equal to m2. (or the x-values must all be the same, in which case the line segments are exactly vertical) Figuring out if they''re both part of the same infinite line is also easy: if they are parallel AND both intercepts are equal (they intersect the y-axis at the same point), they are part of the same line, and this is the -only- case where they might overlap, right? Now, I''m stuck. I can''t figure out how to calculate if they overlap each other, and if so, where. The line segments both have a start and an end point, and I''d like to know when segment one encounters segment 2 for the first time, and where it encounters it for the last time. (Later on, I''d like to know when two objects traveling along the segments collide if they both travel at a given speed, but I figured that''s another topic.) Surely, there must be a relatively easy way to figure this out, and searching on various subjects has yielded no results, so far... Can anyone give me a hand on this subject?

Share this post


Link to post
Share on other sites
ok well if you're using y = mx + b equation to define your line, your lines can never be vertical...

so lets say you have
- line 1 start (x1, y1), end (x2, y2)
- line 2 start (x3, y3), end (x4, y4)

I'm also going to assume that x1 < x2 and x3 < x4...

to find out if they intersect

if (x1 <= x4 && x1 >= x3) // If x1 is between x3 and x4
{
// The lines intersect
}

if (x2 <= x4 && x2 >= x3) // If x2 is between x3 and x4
{
// The lines intersect
}

if (x3 <= x2 && x3 >= x1) // If x3 is between x1 and x2
{
// The lines intersect
}

if (x4 <= x2 && x4 >= x1) // If x4 is between x1 and x2
{
// The lines intersect
}

does that makes sense? its not much harder to find out where the overlap is... the overlap section will always start and end at one of the line segment's ends.

[edited by - SpaceDude on November 16, 2003 8:10:34 PM]

Share this post


Link to post
Share on other sites
you should drop the y = mx + b, and use

P is on line (O, D) (origin O, direction D) if


P = O + t.D (that works for both 2D and 3D)


parametric form (O is point on the line, D is direction of the line)

if (V0 and V1 are point on the line)


P = V0 + t . (P1 - P0),


P is on the segment [P0, P1] if t = [0, 1]

and lines (A, D) and (B, E) are parallel if


(D x E) / (|D| * |E|) < threshold

(D x E).(D x E) / (D.D * E.E) < (threshold * threshold)


x : cross product
. : dot product

and further, similarly, they are colinear if


F = (B - A),

(F x E).(F x E) / (F.F * E.E) < (threshold * threshold)



now, to find if the segments overlap, what you do is find spans of the two segments along a direction.

consider segments (V0, V1), (Q0, Q1), that you KNOW the lines are colinear.



D = (V1 - V0);

minv = V0 . D;
maxv = V1 . D;

q0 = Q0 . D;
q1 = Q1 . D;

minq = min(q0, q1);
maxQ = max(q0, q1);

if (maxq < minv || minq > maxv)
segments do not overlap;

Vector P0, P1; // the overlap segment


if (minv > minq)
P0 = V0;
else
{
if (q0 < q1)
P0 = Q0;
else
P0 = Q1;
}

if (maxv < maxq)
P1 = V1;
else
{
if (q0 > q1)
P1 = Q0;
else
P1 = Q1;
}




Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Two line segments that lie on the same (infinite) line intersect if and only if the axis-aligned bounding boxes of the line segments intersect. (Assuming the boundary of the box is considered part of the box.)

This is basically what "SpaceDude" is doing in his test, only that he has excessively many tests in his, uh, test. Using the same assumptions, namely:

#so lets say you have
#- line 1 start (x1, y1), end (x2, y2)
#- line 2 start (x3, y3), end (x4, y4)
#
#I''m also going to assume that x1 < x2 and x3 < x4...

the test is best written as:

if (x2 < x3 || x1 > x4) return NO_INTERSECTION;
if (y2 < y3 || y1 > y4) return NO_INTERSECTION;
return INTERSECTION;

If you don''t know that x1 < x2 and x3 < x4, you need a few extra tests to establish which coordinate components are the smallest/largest.


You should, however, take oliii''s suggestion seriously. The ''y = mx + b'' form of a line is an abomination and should NEVER be used. Assuming you have two points, A and B, the "correct" way of defining a line through the points is as:

L(t) = A + t*(B - A)

This is the _parametric equation_ of a line. If you let D = B - A be a direction vector, then this form is equivalent to the form oliii gave.

Christer Ericson
Sony Computer Entertainment, Santa Monica

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
You should, however, take oliii''s suggestion seriously. The ''y = mx + b'' form of a line is an abomination and should NEVER be used.



Hmm, and why is that?

I''m not actually using y=mx+b to define the line: the start and end coordinates define the line. I''m only using the y=mx+b formula to determine where two non-parallel lines intersect. I''m defining both m and b from the start and end coordinates of the line.
It works like a charm, and is pretty cheap. I see no reason not to use it. So why is it such an abomination?

Share this post


Link to post
Share on other sites
y = mx + b does not apply to geometric space. It is simply the form of a linear function - f(x) = mx + b. It cannot represent vertical lines and there is no easy conversion to three dimensions.

Share this post


Link to post
Share on other sites
Depends what you''re using it for... best to keep things simple, and if you know that you''ll never want to represent vertical lines then why not use y=mx+c ?

However, if you want some info on how to do it parametrically:

http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/


Share this post


Link to post
Share on other sites
quote:
Original post by SpaceDude
Depends what you''re using it for... best to keep things simple, and if you know that you''ll never want to represent vertical lines then why not use y=mx+c ?



Exactly my point. I''m not planning to ever move this code to 3d (there''s simply no point in this specific case), and it works like this, so I''d rather use a simple, perhaps dodgy way that works in this case, than a complicated, error-prone ''right'' way that offers no advantages over the other method right now.

But, I''ll check out that link in more detail later on. I hope the Google cache is up to date... the server appears to be kind of down.

Thanks for your help!

Share this post


Link to post
Share on other sites
... You sill can''t represent a vertical line with y=mx+b.
furthermore, if the slopes of the lines are the same, unless they got a point in common, they don''t intersect. (In 2-space!!!!!!)

But using y=mx+b you still can''t represent a vertical line - you''ll divide by zero!

Now I''m not gonna lecture you over the evils of y=mx+b, but I''ll just tell ya to watch for division by zero. :-/

Scout



All polynomials are funny - some to a higher degree.
Furthermore, polynomials of degree zero are constantly funny.

Share this post


Link to post
Share on other sites
quote:
Original post by MrScout
furthermore, if the slopes of the lines are the same, unless they got a point in common, they don''t intersect. (In 2-space!!!!!!)



I know, but if they have a point in common, they''ll overlap, in which case there''s still chance of collision.

quote:
Original post by MrScout
But using y=mx+b you still can''t represent a vertical line - you''ll divide by zero!

Now I''m not gonna lecture you over the evils of y=mx+b, but I''ll just tell ya to watch for division by zero. :-/



I know. It''s easily fixed by testing if the start and end x or y are the same. If that''s the case, just set the slope to a really high number. As long as the world dimensions don''t get exorbitantly high, that''ll work fine.

It''s a bit of a hack, but it works well in this particular case, and is far more comprehensible, and thus less error-prone.

In this specific case, mind you.

Share this post


Link to post
Share on other sites