Do They Intersect?

Given two line segments, with specified endpoints, how can you determine if they intersect?  Consider one line segment running from (Ax,Ay) to (Bx,By) and another from (Cx,Cy) to (Dx,Dy).

Since this question doesn't have a precise answer, send a simple description of a method that would work.

If anyone writes a program, try to solve this: What is the probability of two line segments intersecting when their endpoints are chosen randomly from a 4x4 grid (shared endpoints and endpoints on lines are considered intersecting)? Zero length lines are not to be considered.

Extension: How would you solve the 3-D case?

Source: Reader Sudipta Das.

Solutions were received from Joseph Zbiciak, Bernon R. Erickson, Joseph DeVincentis, Saw L.B., Jimmy Chng Gim Hong, Alan O'Donnell, Richard L. Pratt, John Hewson, Jayavel Sounderpandian, Paul botham, Claudio Baiocchi, and Domen Puncer.  Most solutions followed the formula of "First find the intersection point, then see if that point is on both segments."  Bernie Erickson's example is below.  He points out that in 3-D, all four points must be on the same plane for the lines to intersect.   Domen Puncer provided another solution using vectors, also below.

From Bernie Erickson:
Solve for the intersection of the two lines (Assume that they stretch to infinity in both directions), and test whether the value of x at the intersection is between Ax and Bx and between Cx and Dx (you could instead test the value of y).  Formula:

x=((Dx-Cx)*(AxBy-BxAy)-(Bx-Ax)*(CxDy-DxCy))/((Dx-Cx)*(By-Ay)-(Bx-Ax)*(Dy-Cy))
y=((By-Ay)*(DxCy-CxDy)-(Dy-Cy)*(BxAy-AxBy))/((Dx-Cx)*(By-Ay)-(Bx-Ax)*(Dy-Cy))

A quick simulation in Excel shows about 23% intersection for the 4 by 4.

The 3D case is interesting.  Two lines intersecting has a similar algorithm, really a generalization.  Generalizing to the probability that two line segments in a cube intersect doesn't work very well.  The probability is zero since both lines would have to lie on a plane, and the probability that all four points lie on an infinitesimally thin plane is zero.  The problem could be generalized to bounded planes within a cube.

From Domen Puncer:
First line divides plane into 2 halves. If points of the second line aren't on the same subplain, then we check the same with line segments exchanged: Second line divides plane, and if points of first line are now too on different subplanes, then the line segments intersect.

How do we check if points are on the same subplain? If triangles ABC and ABD have the same orientation then C and D are on the same subplain. We can test this with vector product (if ABxAC and ABxAD have same sign / + or - /)

3D?  If the line segments intersect they must be on a same plain... now we have a 2D problem solvable by upper description.

Mail to Ken