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