SFML community forums
Help => General => Topic started by: Gregory on November 06, 2010, 07:17:18 pm
-
Hey guys!? how can i check if have a intersect/collision of a line in a rectangle?
(http://img72.imageshack.us/img72/7492/semttuloha.jpg) (http://img72.imageshack.us/i/semttuloha.jpg/)
i made this code, but is very slow for a lot of lines and rectangles:
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?
-
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. ;-)
-
sorry, but i didn't understand what you spoke. can you give an example?
-
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:
-
i have 15 years, i get a code in internet that works, but i wanted make my code
-
Damn! 15 that's so young! :P
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 ?
-
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 ?
-
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 ?
-
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
-
oww, thank you, i will try! and not, i'm brazillian
-
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.
-
oww, thank you, i will try! and not, i'm brazillian
Damn! I lost ! Hahaha
-
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.
-
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"
-
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:
-
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
-
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!
-
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. :P
-
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)
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.