Vérifier qu’un point appartient à un segment

Considérons un segment $S $ défini par deux points $A $ et $B$. Le but ici est de savoir si un troisième point $C $ appartient au segment$S$.

Cette vérification est faite en deux étapes.

Est-ce que A, B et C sont alignés ?

La première étape consiste à vérifier si $A$, $B $ et $C $ sont alignés, i.e. si les vecteurs $\vec{AB} $ et $\vec{AC} $ sont colinéaires. Cela peut facilement être testé en calculant le produit vectoriel suivant :

$$ \vec{AB} \times \vec{AC}=0 $$

Si le produit vectoriel de $\vec{AB} $ et $\vec{AC} $ eest égal à zéro, cela implique que les vecteurs sont colinéaires ou que les points $A $ et $B $ ou $A $ et $C $ sont coincidents. Si le produit vectoriel est différent de zéro, le point n’appartient pas au segment.

Est-ce que C se trouve entre A et B ?

En supposant que les points $A$ , $B $ et $C $ ont alignés, il ne nous reste plus qu’à tester si le point $C $ est situé entre $A $ et $B$ . Cela peut être vérifié en testant si le produit scalaire des vecteurs $\vec{AB} $ et $\vec{AC} $ est positif et inférieur au produit scalaire de $\vec{AB} $ et $\vec{AB}$. Calculer $ K_{AC} $ et $K_{AB} $ selon la formule suivante :

$$ K_{AC}={\vec{AB} . \vec{AC}} $$ $$ K_{AB}={\vec{AB} . \vec{AB}} $$

Selon les valeurs de $K_{AC} $ et $K_{AB}$, cinq cas peuvent se présenter:

Test	Resultat
$K_{AC}<0 $	Le point n'est pas entre $A $ et $B$
$K_{AC}>K_{AB} $	Le point n'est pas entre $A $ et $B$
$K_{AC}=0 $	Les points $C $ et $A $ sont confondus
$K_{AC}=K_{AB} $	Les points $C $ et $B $ sont confondus
$0<K_{AC}<K_{AB} $	Le point $C $ appartient au segment $S$

Code source C++

/*!
 * \brief rOc_segment::isPointOnSegment check if a point is inside the current segment
 * \param point coordinates of the point to test
 * \return  ROC_SEGMENT_INTERSEC_NONE if the point doesn't lay with the segment
 *          ROC_SEGMENT_INTERSEC_EXTREMITY_P1 if the point is merged with P1
 *          ROC_SEGMENT_INTERSEC_EXTREMITY_P2 if the point is merged with P2
 *          ROC_SEGMENT_INTERSEC_CROSS if the point belongs to the segment (extremity no included)
 */
char rOc_segment::isPointOnSegment(rOc_point point)
{
    // A and B are the extremities of the current segment
    // C is the point to check

    // Create the vector AB
    rOc_vector AB=this->vector();
    // Create the vector AC
    rOc_vector AC=rOc_vector(this->point1(),point);

    // Compute the cross product of VA and PAP
    // Check if the three points are aligned (cross product is null)
    if (!( AB.cross(AC).isNull())) return ROC_SEGMENT_INTERSEC_NONE;

    // Compute the dot product of vectors
    double KAC = AB.dot(AC);
    if (KAC<0) return ROC_SEGMENT_INTERSEC_NONE; 
    if (KAC==0) return ROC_SEGMENT_INTERSEC_EXTREMITY_P1; 

    // Compute the square of the segment length 
    double KAB=AB.dot(AB); 
    if (KAC>KAB) return ROC_SEGMENT_INTERSEC_NONE;
    if (KAC==KAB) return ROC_SEGMENT_INTERSEC_EXTREMITY_P2;

    // The point is on the segment
    return ROC_SEGMENT_INTERSEC_CROSS;
}

Voir aussi

Dernière mise à jour : 07/12/2019

Test	Resultat
\(K_{AC}<0 \)	Le point n'est pas entre \(A \) et \(B\)
\(K_{AC}>K_{AB} \)	Le point n'est pas entre \(A \) et \(B\)
\(K_{AC}=0 \)	Les points \(C \) et \(A \) sont confondus
\(K_{AC}=K_{AB} \)	Les points \(C \) et \(B \) sont confondus
\(0<K_{AC}<K_{AB} \)	Le point \(C \) appartient au segment \(S\)