The vertical lines will cause challenges, recommend another approach: Parametrized lines L(t) = (Ax,Ay) + t*(Dx,Dy)
// Pseudo code
// D slope
D1 = (L1[1].x - L1[0].x, L1[1].y - L1[0].y)
D2 = (L2[1].x - L2[0].x, L2[1].y - L2[0].y)
// Parametric line
L1(t1) = (L1[0].x, L1[0].y) + t1*D1
L2(t2) = (L2[0].x, L2[0].y) + t2*D2
// Simultaneous equation
// Solve the 2 equations with 2 unknowns t1, t2
(D1.x -D2.x)(t1) = (L2[0].x – L1[0].x)
(D1.y -D2.y)(t2) = (L2[0].y – L1[0].y)
// If determinant is 0, lines are parallel. Special handling
// Else if 0.0 <= t0 & t1 <= 1.0, lines intersect
Details
L1[0]
and L1[1]
are 2 points that define a segment. (OP uses L1.vertex[0].x
, I use the shorten L1..x notation
.) L1(t1)
is a function defines a line that goes through those two points as a function of t1
. Notice when t1
is 0, L1
is (L1[0].x, L1[0].y)
and when t1
is 1, (L1
is L1[1].x, L1[1].y)
. Similar for L2. Now we have 2 Parametric line equations as a function of t1
and t2
.
The next step is to find the values of t1
and t2
that generate the same (x,y)
point for both lines, in other words, the intersection. Thus:
D1.x = L1[1].x - L1[0].x
D1.y = L1[1].y - L1[0].y
D2.x = L2[1].x - L2[0].x
D2.x = L2[1].y - L2[0].y
L1[0].x + t1*D1.x = L2[0].x + t2*D2.x
L1[0].y + t1*D1.y = L2[0].y + t2*D2.y
// or
DX = L2[0].x - L1[0].x
DY = L2[0].y - L1[0].y
D1.x*t1 - D2.x*t2 = DX
D1.y*t1 - D2.y*t2 = DY
// or in matrix notation
(D1.x - D2.x)(t1) = (DX)
(D1.y - D2.y)(t2) = (DY)
//
d = D1.x*D2.y - (-D2.x)*(-D1.y)
// if d is 0, lines are parallel and need to determine if co-incident or distinct.
t1 = ( DX(-D2.y) - DY*(- D2.x) )/d
t2 = ( DX(-D2.x) - DY*(- D1.x) )/d
Finally we have t1
and t2
. If there are both in the range 0 to 1, then the intersection occurred in the original segments. This answers the question "if two finite lines (segments) cross each other?"