Tuesday, 22 May 2018

How to check if two line segments are crossed?

this is a mathematical question, not programming, but since I am working on some 3D developing, i have to deal with lots of mathematical calculation, one of the most difficult questions is: How to check two lines are crossed?

like this:















Given line segments p1p2 and p3p4, how to check if they are crossed?

well, to answer this question, I reviewed my mathematical knowledge learned almost 25 years ago,  completely forgot. Now i give out the answer, how to check, what formula you have to use:

first we have to define some rules, P1, P2, P3, P4 they are all vector 2 points, which means they all have x and y coordinate value
P1(x,y), P2(x,y), P3(x,y), P4(x,y)

Tow points can define a line, the line formula is like this:
(x-x1)/(x2-x1) = (y-y1)/(y2-y1)
So the line defined by line segment P1P2 can be written like this:
(x-P1.x)/(P2.x-P1.x) = (y-P1.y)/(P2.y-P1.y)

the same reason,  the line defined by line segment P3P4 can be written like this:
(x-P3.x)/(P4.x-P3.x) = (y-P3.y)/(P4.y-P3.y)

now we have a perfect binary equations
(x-P1.x)/(P2.x-P1.x) = (y-P1.y)/(P2.y-P1.y)
(x-P3.x)/(P4.x-P3.x) = (y-P3.y)/(P4.y-P3.y)

the alternative way is:
(P2.y-P1.y)x+(P1.x-P2.x)y = P1.x(P2.y-P1.y) + P1.y(P1.x-P2.x)
(P4.y-P3.y)x+(P3.x-P4.x)y = P3.x(P4.y-P3.y) + P3.y(P3.x-P4.x)

to get x and y, please reference the binary equation solver, here I give out the solution only
given:





here:
b1 = (P1.x-P2.x);
c2=P3.x(P4.y-P3.y) + P3.y(P3.x-P4.x);
b2=(P3.x-P4.x);
c1=P1.x(P2.y-P1.y) + P1.y(P1.x-P2.x);
a2=(P4.y-P3.y)x+(P3.x-P4.x);
a1=(P2.y-P1.y)x+(P1.x-P2.x)

based on all these conditions, we can calculate the cross point of the two lines, than check the range

defined cross point (x,y)
if (x between P1.x and P2.x) and (y between P1.y and P2.y) and (x between P3.x and P4.x) and (y between P3.y and P4.y)
than we can see, these two line segments are crossed, otherwise, there is no cross

based on the logic above, I believe you can easily design your code to check cross






No comments:

Post a Comment