public static boolean linesIntersect ( double x1 , double y1 , double x2 , double y2 , double x3 , double y3 , double x4 , double y4 ) { // A = (x2-x1, y2-y1) // B = (x3-x1, y3-y1) // C = (x4-x1, y4-y1) // D = (x4-x3, y4-y3) = C-B // E = (x1-x3, y1-y3) = -B // F = (x2-x3, y2-y3) = A-B // // Result is ((AxB) * (AxC) <= 0) and ((DxE) * (DxF) <= 0) // // DxE = (C-B)x(-B) = BxB-CxB = BxC // DxF = (C-B)x(A-B) = CxA-CxB-BxA+BxB = AxB+BxC-AxC x2 -= x1 ; // A y2 -= y1 ; x3 -= x1 ; // B y3 -= y1 ; x4 -= x1 ; // C y4 -= y1 ; double AvB = x2 * y3 - x3 * y2 ; double AvC = x2 * y4 - x4 * y2 ; // online if ( AvB == 0 && AvC == 0 ) { if ( x2 != 0 ) { return ( x4 * x3 <= 0 ) || ( ( x3 * x2 >= 0 ) && ( x2 > 0 ? x3 <= x2 || x4 <= x2 : x3 >= x2 || x4 >= x2 ) ) ; } if ( y2 != 0 ) { return ( y4 * y3 <= 0 ) || ( ( y3 * y2 >= 0 ) && ( y2 > 0 ? y3 <= y2 || y4 <= y2 : y3 >= y2 || y4 >= y2 ) ) ; } return false ; } double BvC = x3 * y4 - x4 * y3 ; return ( AvB * AvC <= 0 ) && ( BvC * ( AvB + BvC - AvC ) <= 0 ) ; }
Returns true if the specified two line segments intersect .