Rechercher un chevauchement entre des lignes colinéaires

Question

Étant donné deux segments de ligne colinéaires AB et CD, comment trouver s'ils se chevauchent? Comment puis-je localiser les points de début et de fin du chevauchement?

Voici l'approche que j'utilise. Je suis d'abord veiller à ce qu'un < B et 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 
    } 
} 

Maintenant, est pas là une solution plus simple de le faire? Mise à jour: il existe une autre façon de comparer la somme des longueurs des deux segments avec la distance entre les points les plus éloignés. Si ce dernier est le moindre, le chevauchement existe.

Answer 1

Assurez 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

Assurez-vous A<B, C<D et A<=C (ce que vous pouvez faire par simple échange). Puis:

• si B<C, les segments sont disjoints
• si B=C, l'intersection est le seul point B=C
• si B>C, l'intersection est le segment [C, min(B, D)]