Line in box collision

[NoIdea]

An AABB box can have scale/rotation/translations thanks to opengl matrices. Just use transform to local

To find the equation, just use the determinant. Call u the vector defined by the two known points. Call A one of the known points. M of coordinate x,y is on the line if and only if the vector AM and u are colinear. Now, just use the determinant to get the equation. The determinant must be equal to 0.
Means that xy' - x'y = 0
<=> (x-A.x)*(B.y-A.y)-(B.x-A.x)*(y-A.y)=0
<=>(B.y-A.y)x+(A.x-B.x)y=A.xB.y-B.xA.y

[Hiura]

While I'm «losing» my time here I'm not porting SFML for OS X... So PLEASE take some time to post. It's very impudent of you, you know ? You should have understood now that we (or at least I) expect some good answer and not any shiftless answers. I may seem rude but I'm really getting tired of all of this...

You're speaking of AABB boxes but I still haven't got the idea. How it is used ?

And what if you don't have a box with four side but three, seven , ... ?

You also seem to have missed one vital aspect of the above discussion : we're looking for a simple and flexible solution.

Also you pointed out that y=ax+b doesn't allow to represent vertical line. You're right on that but that's not an issue : you only have to modify a little bit the algorithm like this :

(Remember : )

[...]

a) a line f is representable mathematically by y=a*x+b where a is the slope [2] of the line and b is the y-intercept of the line [3].
b) a line can be defined by two points O(o1, o2) and P(p1, p2).

[...]

From the point O and P we can find our a and b with these formulas :
a = (o2 - p2) / (o1 - p1)
b = o2 - a * o1 which is also b = p2 - a * p1

[...]

Let's say our two segments are delimited by two points M(m1, m2) N(n1, n2) and I(i1, i2), J(j1, j2), respectively.

Let's add that IJ is the segment of our side.

When the MN line is vertical we have m1-n1=0 thus we have the following cases :

-the IJ line is also vertical (i1-j1=0) and the two are not on top of each other (ie i1!=m1). Thus there is no intersection.

-the IJ line is also vertical and the two are on top of each other (ie i1=m1). Here we can say the intersection is in M (or N).

-the IJ line is not vertical. Thus we evaluate the second line with x=o1 and check if this value is between m2 and n2.

When the MN line is not vertical we have the following :

-if the IJ line is vertical we check if the intersection is between m1 and n1.

-if the IJ line is not vertical then you solve the system of equations and

check if x is between m1 and n1 and between i1 and j1. Or you check y.

So, please, give us a good answer! I'll never say that I'm always right : there are always better solutions. But construct a little bit your answer!

[lywald]

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.

[Disch]

I'm coming into this thread late.... and I only skimmed.

For line-line collision detection, you do not need to calculate the slope.  And in fact I would advise against it because you need to have special cases (vertical lines have undefined slope, so you have to treat them as a special case)


There a very simple and fast way to do this with linear algebra that I use all over the place in my current game project.

I'll share the code when I get home, but I'm at work right now.

EDIT:

Here's a modified version of the code I use.  The version I use has different output (tweaked for my needs)

Code: [Select]



inline double Dot(const Point& a,const Point& b)                        { return (a.x*b.x) + (a.y*b.y); }
inline double PerpDot(const Point& a,const Point& b)                    { return (a.y*b.x) - (a.x*b.y); }


bool LineCollision( const Point& A1, const Point& A2,
                    const Point& B1, const Point& B2,
                    Point* out                                )
{
    Point a(A2-A1);
    Point b(B2-B1);
    Point c(B2-A2);

    double f = PerpDot(a,b);
    if(!f)      // lines are parallel
        return false;

    double aa = PerpDot(a,c);
    double bb = PerpDot(b,c);

    if(f < 0)
    {
        if(aa > 0)     return false;
        if(bb > 0)     return false;
        if(aa < f)     return false;
        if(bb < f)     return false;
    }
    else
    {
        if(aa < 0)     return false;
        if(bb < 0)     return false;
        if(aa > f)     return false;
        if(bb > f)     return false;
    }

    if(out)
        *out = b * (1.0 - (aa / f)) + B1;
    return true;
}


Point is a typedef of sf::Vector2<double>.  You could also use sf::Vector2f if you want.

LineCollision returns true if lines intersect.  Also if 'out' is non-null, '*out' is set to the intersect point.