Check if a point belongs on a line segment

Lets consider \(S \) a line segment defined by its extrimity points \(A \) and \(B\). We want to know if a third point \(C \) belongs on the segment \(S\).

Illustration of a point belonging to a line segment

This can be checked in two steps.

Check if A, B and C are aligned?

First check if \(A\), \(B \) and \(C \) are aligned, i.e. if the vectors \(\vec{AB} \) and \(\vec{AC} \) are colinear. Use the cross product:

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

The cross product of \(\vec{AB} \) and \(\vec{AC} \) equal to 0 means that the vectors are colinear or that the points \(A \) and \(B \) or \(A \) and \(C \) coincide. If the cross product is not equal to zero, the point doesn't belongs on the segment.

Check if C is between A and B ?

Assuming the points \(A\) , \(B \) and \(C \) are aligned, we now want to know if the point \(C \) is between \(A \) and \(B\) . It can be verified by checking if the dot product of \(\vec{AB} \) and \(\vec{AC} \) is positive and less than the dot product of \(\vec{AB} \) and \(\vec{AB}\). Calculate \( K_{AC} \) and \(K_{AB} \) according to:

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

Depending on \(K_{AC} \) and \(K_{AB}\), five cases may happen:

Test Result
\(K_{AC}<0 \) The point is not between \(A \) and \(B\)
\(K_{AC}>K_{AB} \) The point is not between \(A \) and \(B\)
\(K_{AC}=0 \) The points \(C \) and \(A \) coincide
\(K_{AC}=K_{AB} \) The points \(C \) and \(B \) coincide
\(0<K_{AC}<K_{AB} \) The point \(C \) belongs on the line segment \(S\)

C++ source code

/*!
 * \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;
}

See also


Last update : 11/29/2018