Do 2 parallel line segments overlap, and where?
Author
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?
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]
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]
you should drop the y = mx + b, and use
P is on line (O, D) (origin O, direction D) if
parametric form (O is point on the line, D is direction of the line)
if (V0 and V1 are point on the line)
P is on the segment [P0, P1] if t = [0, 1]
and lines (A, D) and (B, E) are parallel if
x : cross product
. : dot product
and further, similarly, they are colinear if
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.
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 segmentif (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;}
Author
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!
Working now. Many thanks!
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
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
Author
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?
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.
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/
However, if you want some info on how to do it parametrically:
http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/
Author
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!
... 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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
