Znajdź nakładanie się linii współliniowych

Question

Biorąc pod uwagę dwa współliniowe odcinki linii AB i CD, w jaki sposób mogę stwierdzić, czy nakładają się one na siebie? Jak zlokalizować punkt początkowy i końcowy zakładki?

Poniżej przedstawiono podejście, z którego korzystam. Ja pierwszy zapewnienie, że < B i 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 
    } 
} 

Teraz nie istnieje prostsze rozwiązanie, aby to zrobić?

Aktualizacja: jest inny sposób ... porównać sumę długości obu segmentów z odległością między najbardziej zewnętrznymi punktami. Jeśli ta ostatnia jest mniejsza, istnieje nakładanie się.

Answer 1

zapewnić < 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

Upewnij się, że A<B, C<D i A<=C (można to zrobić poprzez zwykłą zamiana). Następnie:

• jeśli B<C segmenty są rozłączne
• jeśli B=C, wówczas przecięcie jest jeden punkt B=C
• jeśli B>C, wówczas przecięcie jest segment [C, min(B, D)]