algorithm - 查找共线线之间的重叠

Question

给定两条共线线段 AB 和 CD，我如何找到它们是否重叠？如何定位重叠的起点和终点？

以下是我正在使用的方法。我首先要确保 A < B 和 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
  }
}

现在，没有更简单的解决方案来做到这一点吗？

更新：还有另一种方法......将两个段的长度之和与最外点之间的距离进行比较。如果后者较小，则存在重叠。

Answer 1

确保 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

Answer 2

确保A<B、C<D和A<=C（您可以通过简单的交换来实现）。然后：

• 如果B<C, 段是不相交的
• 如果B=C，则交点为单点B=C
• 如果B>C，则交点为线段[C, min(B, D)]