Problem:
Input: The line L is given as input in the form of two points
lying on the line. The line segment S is given as input in the form of
its two end points.
Output: We return the type of intersection:
line passes through the line segment
line does not intersect the line segment
line contains the line segment
line passes through an end point of the segment
Algorithm:
Firstly the side-operator(L,S) should be zero which means that the line L and the line containing the line segment are either parallel or they intersect. Next we need to find out wheter the line L intersects the line segment S or not.
Consider any point P which is not in the plane formed by line segment S and the line L. Construct directed lines L1 and L2 as shown in the figure above. Let,
s1 = side-operator(L,L1)
s2 = side-operator(L,L2)
Then if,
s1 and s2 have different signs (one <0 and other >0) : line
does not intersect the line segment
s1 and s2 have same sign ( >0 or <0) : line
passes through the line segment
s1 = s2 = 0 : line contains the line segment
One out of s1, s2 is zero : line passes through
an end point of the segment