Jump to content
  • Advertisement
Sign in to follow this  
GroZZleR

Line-Segment Intersections and Collinear Overlaps

This topic is 3810 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I'm in the position where I need to know if two line segments are intersecting or "overlapping", that is, two colinear lines that touch but aren't considered intersecting. (0,0)(10,0) "overlaps" (5,0)(15,0) but isn't considered intersecting (from what I've been able to find in my searches). All the code I've been able to find deals entirely with intersections and usually bails / returns false when it finds the lines are parallel. Is there a general solution that includes intersections AND collinear overlaps or should I implement one and then add special test-cases for parallel lines? Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
If the segments are parallel and overlapping, then they intersect; however, this does have to be handled differently than the more common case of non-parallel intersecting lines.

Once you've determined that the segments are colinear, you can then proceed as follows:

1. Project the four endpoints (two for each segment) onto the line passing through both segments

2. This should yield four parametric values (e.g. four values of 't')

3. Compute the overlap (if any) between these two parametric intervals

4. Use the endpoints of the interval of overlap (remember, these are scalar values) to compute the endpoints of the interval in 2-space

For step one, you can just project the endpoints onto either of the lines supporting the line segments. Some pseudocode:
// The segment endpoints are A, B, C, and D
vector2 dir = B - A;
float t1 = 0.f;
float t2 = 1.f;
float t3 = dot(C - A, dir) / dot(dir, dir);
float t4 = dot(D - A, dir) / dot(dir, dir);

// If the intervals [t1, t2] and [t3, t4] overlap, intervals_overlap()
// should return 'true' and store the overlap endpoints in 'start' and 'end':
float start, end;
if (intervals_overlap(t1, t2, t3, t4, start, end) {
// The endpoints of the overlap in 2-space:
vector2 p1 = A + start * dir;
vector2 p2 = A + end * dir;
}
That's off the top of my head, and it's quite possible that I've gotten it wrong (if so, perhaps someone will correct it, or maybe suggest a better method altogether).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!