Calculation of intersection of two line segments

problem

Known line segments P1P2 and Q1Q2, Determine whether they have intersections , If you have any , Find the intersection point .

1. Judge whether line segments intersect

Pictured , Judge whether line segments intersect , It can be carried out through a series of experiments .

Rapid rejection experiment

If the P1P2 and Q1Q2 Rectangles that are diagonal do not intersect , be P1P2 It must not intersect
Only when
min(p1.x,p2.x) <= max(q1.x,q2.x)
min(q1.x,q2.x) <= max(p1.x,p2.x)
min(p1.y,p2.y) <= max(q1.y,q2.y)
min(q1.y,q2.y) <= max(p1.y,p2.y)
When all four formulas are satisfied , Two line segments can intersect , Otherwise, it will not intersect . This is Rapid rejection experiment .

Straddle experiment

According to the picture above , Even after passing the rapid rejection experiment , Two straight lines do not necessarily intersect , therefore , We need to further pass the so-called Straddle experiment Judge .
For this part, please refer to link

2. Calculation of intersection of line segments

set up $P_1(x_1,y_1),P_2(x_2,y_2),Q_1(x_3,y_3),Q_2(x_4,y_4)$, be $P_1{P}_2$ and $Q_1{Q}_2$ The intersection of is calculated as follows ：

The reason why I think the straddle experiment is of little significance , It is because there is no great difference between the calculation of the straddle experiment and that of the direct calculation of the intersection , We can calculate the intersection of straight lines directly , Then judge whether the intersection is on the line segment , The criteria for judgment are as follows :
$$max(x_1,x_2)\ge x_o\ge min(x_1,x_2)$$$$max(x_3,x_4)\ge x_o\ge min(x_3,x_4)$$