CODEWITHSUNDEEP
algorithmgeometrycoordinatescomputational-geometryline-segment
Agnel Kurian
Agnel Kurian

Reputation: 59456

Find overlap between collinear lines

Given two collinear line segments AB and CD, how do I find if they overlap? How do I locate the start and end points of the overlap?

Below is the approach I am using. I am first ensuring that A < B and C < D.

if(pa < pc){
  if(pc < pb){
    if(pd < pb){
      //  overlap exists; CD falls entirely within AB
    }
    else {
      //  overlap exists; CB is the overlapping segment
    }
  }
  else {
    //  no overlap exists; AB lies before CD
  }
}
else {
  if(pa < pd){
    if(pb < pd){
      //  overlap exists; AB lies entirely within CD
    }
    else {
      //  overlap exists; AD is the overlapping segment
    }
  }
  else {
    //  no overlap exists; CD lies before AB
  }
}

Now, isn't there a simpler solution to do this?

Update:there is another way... compare the sum of the lengths of both segments with the distance between the outermost points. If the latter is the lesser, overlap exists.

Upvotes: 14

Views: 8703

Answers (2)

Edoot
Edoot

Reputation: 421

Ensure A<B, C<D:

if (pb - pc >= 0 and pd - pa >=0 ) { // overlap
    OverlapInterval = [ max(pa, pc), min(pb, pd) ] // it could be a point [x, x]
} // else: not overlap

Upvotes: 24

Timothy Shields
Timothy Shields

Reputation: 79441

Ensure A<B, C<D, and A<=C (which you can do by simple swapping). Then:

  • if B<C, the segments are disjoint
  • if B=C, then the intersection is the single point B=C
  • if B>C, then the intersection is the segment [C, min(B, D)]

Upvotes: 5

Related Questions