Search code examples
algorithmgeometrycoordinatescomputational-geometryline-segment

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.


Solution

  • 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