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