Line in box collision

[Gregory]

Hey guys!? how can i check if have a intersect/collision of a line in a rectangle?




i made this code, but is very slow for a lot of lines and rectangles:

Code: [Select]

bool line_collision(int x1, int y1,int x2,int y2,const gameobj& other,int precise) {
    int x,y,angle,dist;
    angle = point_direction(x1,y1,x2,y2);
    dist = point_distance(x1,y1,x2,y2);
    for(int i = 0 ; i < dist ; i+=precise) {
        x = (x1-cos(angle*(DEG))*i);
        y = (y1-sin(angle*(DEG))*i);
        if (x >= other.x + other.rect.Left and x <= other.x + other.rect.Right) {
            if (y >= other.y + other.rect.Top and y <= other.y + other.rect.Bottom) {
                return 1;
            }
        }
    }
    return 0;
}

i think that have others ways to do this, can you help me?

[Hiura]

Hi!

Your code is O(n) where n~(line length / precise) so yes it's slow. Everything is about this loop. You can do without it and have a function=O(m) where m is the number of side of your box :

Let l=ax+b and m(i)=c(i)x+d with x,a,b,c(i) and d in R. Hence l and m(i) are in R. l is the equation for the line and m(i) is the equation of the i-th side of the box.

- for each side of the box do
-- find the intersection between the i-th side of the box and the line by solving the equation system l=m(i)
-- check if the solution of the system is "out" of the side or not.

BTW use true/false instead of 1/0 even if it means the same for the computer : it is much more readable for human like us. ;-)

[Gregory]

sorry, but i didn't understand what you spoke. can you give an example?

[Hiura]

Well, it requires some maths so tell my what your maths level (ie. age, school, country, ...) is so I can turn the explanation around to be understandable.  :wink:

[Gregory]

i have 15 years, i get a code in internet that works, but i wanted make my code

[Hiura]

Damn! 15 that's so young!  


So, the first thing you need to know is what is a line. Check that out for the basis : [1]

Here we're going to use only to thing :
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).

In fact our line f is a linear equation [4].

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

Now you know how to create any line. :wink:

The next step is to take two lines, let's say f and g which are y=a*x + b and y=c*x + d, respectively, and find their intersection [5].

To do that we have to solve the linear system given by f and g. It may sound very complicated but it's quite easy in fact.

This idea is very basic : we want to find the couple (x,y) such that y = a*x + b = c*x + d. (Remember we know a, b, c and d.) Hence a*x - c*x = d - b.

a*x - c*x can be written as x * (a - c) thus if we divide both side of a*x - c*x = d - b by (a - c) we have x = (d - b) / (a - c).

Now we know the value of x but we still don't know what is y. To know it we go back to y = a*x + b and «simply» compute y.

Now you know where the two line f and g intersect. But in our square we don't have line but segments [6]. Thus we have to check if our intersection (x,y) is «in» our segment or «out». This check is very easy :

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. Then you only check if x is between m1 and n1 and between i1 and j1. Or you check y. Checking x AND y is useless because if x is «in» then y is also «in» and vice versa.

If you have some trouble with anything try first to make some sketching then if you still don't understand ask me. :wink:

Now to check if your line go through your box you have to check each side.

Have FUN !

(NB : most part of wiki articles are out of our scope. Don't be afraid of what you're going to read there. Everything you'll need is explained here.)

[1] http://en.wikipedia.org/wiki/Line_(geometry)
[2] http://en.wikipedia.org/wiki/Slope
[3] http://en.wikipedia.org/wiki/Y-intercept
[4] http://en.wikipedia.org/wiki/Linear_equation
[5] http://en.wikipedia.org/wiki/Line_intersection
[6] http://en.wikipedia.org/wiki/Line_segment

PS : just wondering : are you German ?

[NoIdea]

Isnt a line equation more like ax + by = c ?
The easiest is to transform the line in the rectangle's coordinate system. Then, your rectangle is an AABB box. Easy isn't it ?

[Canadadry]

Isnt a line equation more like ax + by = c ?
The easiest is to transform the line in the rectangle's coordinate system. Then, your rectangle is an AABB box. Easy isn't it ?

You are not helping.... This is the same,you just have written it differently, a line has infinite different equation. But you know that, do you?

What's the point? Don't you see he just want to make his own code, he just need to understand how that's work.

Why do you every need to show us how much you know ?

[NoIdea]

Because ax+c doesn't deal with vertical lines !
Furthermore, once the rectangle is an AABB box, it's even simpler !
Equation of one of the sides becomes x=bottom or top or y=left or right

[Gregory]

oww, thank you, i will try! and not, i'm brazillian

[Hiura]

Because ax+c doesn't deal with vertical lines !

So does ax + by = c . As they mean the same, you can do this :

ax + by = c -> by = c - ax = a'x + c -> y = (a'x + c) / b = a''x + c' with b in R* = R\{0} (all value but 0).

Equation of one of the sides becomes x=bottom or top or y=left or right

What do you mean ?

ANYWAY :

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

PS : next time take the same amount of time I took to write all of this down.

[Hiura]

oww, thank you, i will try! and not, i'm brazillian

Damn! I lost ! Hahaha

[Groogy]

oww, thank you, i will try! and not, i'm brazillian

Damn! I lost ! Hahaha

Auuw I'll go with your way anyway XD
Cause that's the equation I remember from school which we called: "Straight Lines Equation"(Swe: Räta linjens ekvation)

Though never used it to detect if it intersects with a side of a polygon.

[NoIdea]

Ax + by = c means that when b = 0, the line is vertical.
As for the length of my messages, i'm writting with my phone which isn't so convenient
A AABB box means axis aligned box and thus has very convenient line equations.

If i remember well, ax + by = c is the cartesian equation. The ax + b = c is in french called "équation réduite"

[Hiura]

Don't mix up «time» and «length».

So if a AABB box has no rotation what's the point ? It's too inflexible. Like the number of side. Even if it's «simpler» the gain is not interesting.

One more question : how can you find ax+by=c with two points ? Hard, isn't it ?   :roll: