🔒 Locked

Do 2 parallel line segments overlap, and where?

Started by Boris Karloff Nov 16, 2003 at 4:56 PM 10 replies 10.4k views

Original Post

Nov 16, 2003 at 4:56 PM

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?

SpaceDude

Nov 16, 2003 at 7:09 PM

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]

oliii

Nov 17, 2003 at 4:03 AM

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;
}

Boris Karloff

Nov 17, 2003 at 7:53 AM

Thanks to you both. I ended up using Spacedude''s solution, as I found it less complicated and does the job in only a handful of if-statements..

Working now. Many thanks!

Boris Karloff

Nov 18, 2003 at 5:43 PM

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?

Neosmyle

Nov 18, 2003 at 5:53 PM

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.

SpaceDude

Nov 18, 2003 at 6:09 PM

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/

Boris Karloff

Nov 19, 2003 at 4:17 AM

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!

MrScout

Nov 20, 2003 at 8:21 PM

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

Platinum314

Nov 24, 2003 at 10:31 AM

Depends on what geometric axioms you want to use.

Boris Karloff

Nov 24, 2003 at 1:23 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.