The Cheapest Way To Find If (But Not Where) Two Line Segments Intersect

Not long ago, I detailed the computationally cheapest way (that I know) to find a ray-plane intersection.  A similar, but simpler problem popped up, which I could model as trying to find the intersection of line segments.  I believe this is also the cheapest way to solve this problem.


In a 2 dimensional plane, we have the coordinates (x,y) for each of the points A, B, C, and D; these are the ends of two line segments, AB and CD.


We can discover if these intersect using the properties of the inner product of vectors. Essentially, the dot product between segment AB and the vector AC will be the opposite sign of the dot product of AB and AD if the two points are on opposite sides of the line segment. The same holds true for CD, CA, and CB. If the endpoints of each segment are on opposite sides of the other segment, the two segments intersect. Otherwise, they do not. This boils down to a few multiplications–no trig functions, and no square roots.

Using vector notation:

\vec{AB} = \vec{B}-\vec{A}, \vec{AB}_\perp = \left\lbrace\vec{AB}(2),-\vec{AB}(1)\right\rbrace

\vec{CD} = \vec{D}-\vec{C}, \vec{CD}_\perp = \left\lbrace\vec{CD}(2),-\vec{CD}(1)\right\rbrace

\vec{AC} = \vec{C} - \vec{A}; \vec{AD} = \vec{D} - \vec{A}; \vec{CA} = -\vec{AC}; \vec{CB} = \vec{B} - \vec{C}

If and only if $latex \left(\vec{AB}_\perp^T \vec{AC}\right) \left(\vec{AB}_\perp^T \vec{AD}\right) < 0 $ and $latex \left(\vec{CD}_\perp^T \vec{CA}\right) \left(\vec{CD}_\perp^T \vec{CB}\right) < 0 $, the line segments intersect. By my count, that is 14 additions and 10 multiplications.  Here is the code in C: [cpp] static bool segIntersect( double A[], double B[], double C[],double D[]) { double AB[2], ABp[2],  AC[2], AD[2], CA[2], CB[2], CD[2], CDp[2]; for( i=0; i &lt; 2; i++ ) { AB[i] = B[i] - A[i]; AC[i] = C[i] - A[i]; AD[i] = D[i] - A[i]; CA[i] = -AC[i]; CB[i] = B[i] - C[i]; CD[i] = D[i] - C[i]; } ABp[0] = -AB[1]; ABp[1] = AB[0]; CDp[0] = -CD[1]; CDp[1] = CD[0]; double test1 = (ABp[0]*AC[0]+ABp[1]*AB[1]) * (ABp[0]*AD[0]+ABp[1]*AD[1]); double test2 = (CDp[0]*CA[0]+CDp[1]*CA[1]) * (CDp[0]*CB[0]+CDp[1]*CB[1]); if( test1 < 0 && test2 < 0 ) return true; else return false; } [/cpp]