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\).

Illustration of a point belonging to a line segment

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 lenght 
    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 : 11/06/2018