Messages

1

General / Line in box collision

« on: November 09, 2010, 05:22:48 pm »

Here's how I'd do it.
Let's call:
- x1/x2 for left and right sides coordinate of the box. (x2 = x1 + width)
- y1/y2 for top/bottom. (y2 = y1 + height)
You get x1/y1 from the box coordinates.
- Start and End are the starting and ending points of your line, with each an x/y.

And the line equation is: f(x) = ax + b
With some maths:
a = (yEnd - yStart) / (xEnd - xStart)
b = yStart - a*xStart

Now if you look, every points of the line must be on the same side of the box between x1 and x2.
So evaluate:
f(x1) > y1 && f(x2) > y1
OR
f(x1) < y2 && f(x2) < y2

If it's true then there is no intersection.
It works because the function is monotone, a straight line.
I think there must be more cost-efficient solutions though.

Also, to avoid dividing by 0, I'd put this before everything:
if (xEnd - xStart == 0) return (x1 > xStart && xStart < x2) && (max(yStart,yEnd) < y2 || min(yStart,yEnd) > y1);
Also there are the cases where f(x1) and/or f(x2) are not on the actual segment...
Well forget this solution, not simple enough.