Найти перекрытие между коллинеарными линиями

Имея два коллинеарных отрезка 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
  }
}

Теперь, нет ли более простого решения для этого?

Обновление: есть еще один способ... сравнить сумму длин обоих сегментов с расстоянием между крайними точками. Если последнее меньше, существует перекрытие.


coordinates algorithm geometry computational-geometry line-segment
person Agnel Kurian    schedule 31.03.2013    source источник

Ответы (2)


arrow_upward
19
arrow_downward

Убедитесь, что 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
person Edoot    schedule 04.04.2013
comment
Великолепно! Добро пожаловать в СО!! - person Agnel Kurian; 04.04.2013

arrow_upward
4
arrow_downward

Убедитесь, что A<B, C<D и A<=C (что можно сделать простой заменой). Затем:

  • если B<C, сегменты не пересекаются
  • если B=C, то пересечение является единственной точкой B=C
  • если B>C, то пересечением является отрезок [C, min(B, D)]
person Timothy Shields    schedule 31.03.2013
comment
Что вы имеете в виду под A ‹ B? с помощью A.x и B.x? для равных х, кто вы можете гарантировать, что? - person AlexWien; 14.11.2014
comment
A,B — первый сегмент, C,D — второй сегмент. - person Flavius; 28.07.2020