Hi, maybe someone can help with algorithm ? I have a line segment between 2 points - (x1, y1), (x2, y2), and i have a square - top(y), bottom(y), left(x), right(x), and i need to find out if line segment intersects with square. If i’m thinking correctly, there should be 3 parts :
line can be inside a square,
line can intersect with 1 or 2 lines of square,
line can be touching one of square lines.
Or maybe it could be simpler, like if at least one end of line is inside square or is at least touching it, then it intersects ?
If L1 and L2 are the points of the line
P1, P2 and P3 are three corners of your square, which needs not be a square but can also be a parallelogram. The following works only on planar squares ( All 4 points have to be on the plane defined by any 3 points of the square )
Your line’‘s equation is L1 + a*(L2-L1), with ‘‘a’’ being any number
Your planes’’ equation is P1 + b*(P2-P1) + c*(P3-P1), again with ‘‘b’’ and ‘‘c’’ being any number
Those equations give you all the points on a line or a plane.
Therefore you’'ll have to solve
L1 + a*(L2-L1) = P1 + b*(P2-P1) + c*(P3-P1) , which is
a*(L2-L1) + b*(P1-P2) + c*(P1-P3) = P1 - L1
if a is in 0…1 the points L1 and L2 are on different sides of the square
if b and c are in 0…1 the infinite line based on L1 and L2 intersects the square