Return to Answer

For integer coordinates in the range \$ -1000 \ldots 1000 \$, all the calculations can be done without overflow. Generally, for coordinates in a range \$ -M \ldots M \$, the computed values are bounded by \$ 8M^2\$ in absolute value, so you can choose the required type accordingly.

The idea is to describe the line segment from \$(a_x, a_y) \$ to \$ (b_x, b_y) \$ in its parametric form $$ (x, y) = (a_x, a_y) + u (b_x - a_x, b_y - a_y) ,円 \quad \text{where } 0 \le u \le 1 ,円. $$ Then the intersection of two line segments is a solution of the linear equation system $$ (b_x - a_x) u - (d_x - c_x) v = c_x - a_x \\ (b_y - a_y) u - (d_y - c_y) v = c_y - a_y $$ with \$ 0 \le u \le 1 \$ and \$ 0 \le v \le 1 \$. In the general case, the solution is given by $$ u = \frac {\Delta_x} \Delta ,円 , \quad v = \frac {\Delta_y} \Delta $$ with the determinants $$ \Delta = \begin{vmatrix} b_x - a_x & d_x - c_x \\ b_y - a_y & d_y - c_y \end{vmatrix} ,円 , \quad \Delta_x = \begin{vmatrix} c_x - a_x & d_x - c_x \\ c_y - a_y & d_y - c_y \end{vmatrix} ,円 , \quad \Delta_y = \begin{vmatrix} c_x - a_x & b_x - a_x \\ c_y - a_y & b_y - a_y \end{vmatrix} $$ If \$ \Delta = 0\$ then the line segments are parallel. Otherwise there is a unique solution \$u, v \$ to the linear equation system, and it easy to check if the solutions fall in the range \$ [0, 1] \$ without actually performing the division.

static void checkIntersection(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy) {
 int det = (bx - ax)*(dy - cy) - (by - ay)*(dx - cx);
 if (det != 0) {
 /*
 * Lines intersect. Check if intersection point is on both segments:
 */
 int detx = (cx - ax)*(dy - cy) - (cy - ay)*(dx - cx);
 int dety = (cx - ax)*(by - ay) - (cy - ay)*(bx - ax);
 if (det < 0) {
 // Normalise to det>0 to simplify the following check.
 det = -det;
 detx = -detx;
 dety = -dety;
 }
 if (detx >= 0 && detx <= det && dety >= 0 && dety <= det) {
 System.out.println("INTERSECT");
 } else {
 System.out.println("NO NOT INTERSECT");
 }
 } else {
 /*
 * Lines are parallel (or identical):
 */
 System.out.println("PARALLEL");
 }
}

The idea is to describe the line segment from \$(a_x, a_y) \$ to \$ (b_x, b_y) \$ in its parametric form $$ (x, y) = (a_x, a_y) + u (b_x - a_x, b_y - a_y) ,円 \quad \text{where } 0 \le u \le 1 ,円. $$ Then the intersection of two line segments is a solution of the linear equation system $$ (b_x - a_x) u - (d_x - c_x) v = c_x - a_x \\ (b_y - a_y) u - (d_y - c_y) v = c_y - a_y $$ with \$ 0 \le u \le 1 \$ and \$ 0 \le v \le 1 \$. In the general case, the solution is given by $$ u = \frac {\Delta_u} \Delta ,円 , \quad v = \frac {\Delta_v} \Delta $$ with the determinants $$ \Delta = \begin{vmatrix} b_x - a_x & d_x - c_x \\ b_y - a_y & d_y - c_y \end{vmatrix} ,円 , \quad \Delta_u = \begin{vmatrix} c_x - a_x & d_x - c_x \\ c_y - a_y & d_y - c_y \end{vmatrix} ,円 , \quad \Delta_v = \begin{vmatrix} c_x - a_x & b_x - a_x \\ c_y - a_y & b_y - a_y \end{vmatrix} $$ If \$ \Delta = 0\$ then the line segments are parallel. Otherwise there is a unique solution \$u, v \$ to the linear equation system, and it easy to check if the solutions fall in the range \$ [0, 1] \$ without actually performing the division.

static void checkIntersection(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy) {
 int det = (bx - ax)*(dy - cy) - (by - ay)*(dx - cx);
 if (det != 0) {
 /*
 * Lines intersect. Check if intersection point is on both segments:
 */
 int detu = (cx - ax)*(dy - cy) - (cy - ay)*(dx - cx);
 int detv = (cx - ax)*(by - ay) - (cy - ay)*(bx - ax);
 if (det < 0) {
 // Normalise to det>0 to simplify the following check.
 det = -det;
 detu = -detu;
 detv = -detv;
 }
 if (detu >= 0 && detu <= det && detv >= 0 && detv <= det) {
 System.out.println("INTERSECT");
 } else {
 System.out.println("NO NOT INTERSECT");
 }
 } else {
 /*
 * Lines are parallel (or identical):
 */
 System.out.println("PARALLEL");
 }
}

static void checkIntersection(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy) {
 int det = (bx - ax)*(dy - cy) - (by - ay)*(dx - cx);
 int detx = (cx - ax)*(dy - cy) - (cy - ay)*(dx - cx);
 int dety = (cx - ax)*(by - ay) - (cy - ay)*(bx - ax);
 if (det != 0) {
 /*
 * Lines intersect. Check if intersection point is on both segments:
 */
 if (det < 0) {
 // Normalise to det>0 to simplify the following check.
 det = -det;
 detx = -detx;
 dety = -dety;
 }
 if (detx >= 0 && detx <= det && dety >= 0 && dety <= det) {
 System.out.println("INTERSECT");
 } else {
 System.out.println("NO NOT INTERSECT");
 }
 } else {
 /*
 * Lines are parallel (or identical):
 */
 System.out.println("PARALLEL");
 }
}

static void checkIntersection(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy) {
 int det = (bx - ax)*(dy - cy) - (by - ay)*(dx - cx);
 if (det != 0) {
 /*
 * Lines intersect. Check if intersection point is on both segments:
 */
 int detx = (cx - ax)*(dy - cy) - (cy - ay)*(dx - cx);
 int dety = (cx - ax)*(by - ay) - (cy - ay)*(bx - ax);
 if (det < 0) {
 // Normalise to det>0 to simplify the following check.
 det = -det;
 detx = -detx;
 dety = -dety;
 }
 if (detx >= 0 && detx <= det && dety >= 0 && dety <= det) {
 System.out.println("INTERSECT");
 } else {
 System.out.println("NO NOT INTERSECT");
 }
 } else {
 /*
 * Lines are parallel (or identical):
 */
 System.out.println("PARALLEL");
 }
}