java - Line Segments Intersection(intersection Point) -

i have created function calculate intersection point of 2 line segment .

unfortunantly code below dosen't work if 1 of segment verticale

    public static point intersection(segment s1, segment s2) {     double x1 = s1.getp1().getx();     double y1 = s1.getp1().gety() ;     double x2 = s1.getp2().getx();     double y2 = s1.getp2().gety() ;     double x3 = s2.getp1().getx();     double y3 = s2.getp1().gety();     double x4 = s2.getp2().getx();     double y4 = s2.getp2().gety();      double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);     if (d == 0) {         return null;     }     double xi = ((x3 - x4) * (x1 * y2 - y1 * x2) - (x1 - x2) * (x3 * y4 - y3 * x4)) / d;     double yi = ((y3 - y4) * (x1 * y2 - y1 * x2) - (y1 - y2) * (x3 * y4 - y3 * x4)) / d;     point p = new point(xi, yi);     if (xi < math.min(x1, x2) || xi > math.max(x1, x2)) {         return null;     }     if (xi < math.min(x3, x4) || xi > math.max(x3, x4)) {         return null;     }     return p; } 

the problem when have vertical line segment , formula

double d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4); 

is equal 0 , method return null.

how can handle exception.

thank you

line intersection without special cases

coming background of projective geometry, i'd write points in homogeneous coordinates:

v1 = [x1, y1, 1] v2 = [x2, y2, 1] v3 = [x3, y3, 1] v4 = [x4, y4, 1] 

then both line joining 2 points , intersection of 2 lines can expressed using cross product:

[x5, y5, z5] = (v1 × v2) × (v3 × v4) 

which can dehomogenize find resulting point as

[x5/z5, y5/z5] 

without having deal special cases. if lines parallel, last point lead division zero, though, might want catch case.

restriction segments

the above infinite lines, though. might want keep code returns null if point of intersection falls outside bounding box. if want real segments, code incorrect: have point of intersection lies outside 1 of segments still inside bounding box.

a proper check can implemented using orientation-checking predicate. determinant of 3 of vectors vi given above have positive sign if triangle form has 1 orientation, , negative sign opposite orientation. points v3 , v4 lie on different sides of s1 if

det(v1, v2, v3) * det(v1, v2, v4) < 0 

and in similar way v1 , v2 lie on different sides of s2 if

det(v3, v4, v1) * det(v3, v4, v2) < 0 

so if both of these satisfied, have intersection between segments. if want include segment endpoints, change < ≤ in these inequalities.