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$.

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 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;
}

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

Check if a point belongs on a line segment

Check if A, B and C are aligned?

Check if C is between A and B ?

C++ source code

See also