COORDVAR Line_Sect(COORDVAR c1, COORDVAR c2, COORDVAR c3, COORDVAR c4)
{
//function designed to give the intersection point of two lines.
//Lines that eventually would intersect if infinite cause a to equal 0, otherwise its 1.
float b1, b2; //The slope of each line
float a1, a2; //The adjustment each line needs
COORDVAR ReturnInfo; //The information that will be returned by the function
//This whole algorith runs off sytems of equations and the fact that any straight lines can
//be written as y = a + (b * x)
if(c1.x - c2.x == 0)
c2.x += .001;
if(c3.x - c4.x == 0)
c4.x += .001;
//Find the slope of each line
//Slope of first line
b1 = (c1.y - c2.y) / (c1.x - c2.x);
//Check to make sure slope is non-zero
if(b1 == 0)
b1 = .001;
//slope of second line
b2 = (c3.y - c4.y) / (c3.x - c4.x);
//Check to make sure slope is non-zero
if(b2 == 0)
b2 = .001;
//Make sure lines aren''t perpendicular
if(b1 == b2)
b1 += .001;
//add the height adjustments
a1 = c1.y - (b1 * c1.x);
a2 = c3.y - (b2 * c3.x);
//Finally, find the intersection points
ReturnInfo.x = -(a1 - a2) / (b1 - b2);
ReturnInfo.y = a1 + (b1 * ReturnInfo.x);
//Check to make sure the lines intersect immediatly
if((c3.x - ReturnInfo.x) * (ReturnInfo.x - c4.x) < 0 && (c3.y - ReturnInfo.y) * (ReturnInfo.y - c4.y) < 0)
{
//"Intersect" should change to 0,0 and a should be set to 0
ReturnInfo.x = 0;
ReturnInfo.y = 0;
ReturnInfo.a = 0;
}
else
ReturnInfo.a = 1;
return(ReturnInfo);
}
Sorry if its a bit messy/amatuer, but I''m still learning.
My line intersection code
To make a short story even shorter, this code doesn''t work the way I''d like it to. It''s supposed to tell me if two lines intersect (and if they intersect immediatly)
I see two possible problems. One is that I simply have a bad algorithim. The other is that the code that checks to see if the collision point is on one of the lines. Either way, I don''t know how to efficiently fix them.
Here''s the code:
i stopped after the first half because of those +0.001 hacks that just dont look right to do. also, if both slopes are the same they are parallel not perpendicular.
try building your method on a less messy representation of lines (variables are 2d/3d/whatever-d coords, a and b are endpoints of the line, p is any point along the line and t is a factor).
p = a + t*(b-a);
your intersection will happen where both have the same p
a + t*(b-a) = c + s*(d-c)
t = (c.x-a.x+s*(d.x-c.x)) / (b.x-a.x)
s = (a.y-c.y+t*(b.y-a.y)) / (d.y-c.y)
you have two coords, meaning two equation and two unknowns (s and t), if you solve for either of it and plug it back in the original term of the corresponding line you get the point of intersection. also a negative t would mean it is before the start of your line and a t>1 means its behind the end point of your line.
try building your method on a less messy representation of lines (variables are 2d/3d/whatever-d coords, a and b are endpoints of the line, p is any point along the line and t is a factor).
p = a + t*(b-a);
your intersection will happen where both have the same p
a + t*(b-a) = c + s*(d-c)
t = (c.x-a.x+s*(d.x-c.x)) / (b.x-a.x)
s = (a.y-c.y+t*(b.y-a.y)) / (d.y-c.y)
you have two coords, meaning two equation and two unknowns (s and t), if you solve for either of it and plug it back in the original term of the corresponding line you get the point of intersection. also a negative t would mean it is before the start of your line and a t>1 means its behind the end point of your line.
(sigh)
I knew making those +.001 hacks were a poor choice.
You''ll have to excuse me, but your explanation didn''t make complete sense to me... could you elaborate?
I knew making those +.001 hacks were a poor choice.
You''ll have to excuse me, but your explanation didn''t make complete sense to me... could you elaborate?
i did it a fairly simple way, i found the intersection point using two equations (y1=(m1)(x1)+(b1), y2=(m2)(x2)+(b2), solving for the common y and x, simple algebra) and checked to see if it was within the bounds of the segments of both lines. It was failing for some time, and i couldnt understand why, but just this week i noticed i was checking the wrong bounds . Anyways, a gamedev member here pointed me to a better algorithm, it was in pseudo code but i wrote it out and it works GREAT.
intersect returns true if the segments meet, false if they dont.
intersect returns true if the segments meet, false if they dont.
struct point{ float x; float y;};struct line{ point p1; point p2;};float direction(point pi, point pj, point pk) { return (((pk.x-pi.x)*(pj.y-pi.y))-((pj.x-pi.x)*(pk.y-pi.y))); }bool on_segment(point pi, point pj, point pk) { if(min(pi.x,pj.x)<=pk.x&&pk.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=pk.y&&pk.y<=max(pi.y, pj.y)) { return true; } else { return false; }}bool intersect(line l1, line l2){ point p1,p2,p3,p4; p1=l1.p1; p2=l1.p2; p3=l2.p1; p4=l2.p2; float d1 = direction(p3, p4, p1); float d2 = direction(p3, p4, p2); float d3 = direction(p1, p2, p3); float d4 = direction(p1, p2, p4); if (((d1>0&&d2<0)||(d1<0&&d2>0))&&(((d3>0&&d4<0)||(d3<0&&d4>0)))) { return true; } else if((d1 == 0)&&on_segment(p3, p4, p1)) { return true; } else if((d2 == 0)&&on_segment(p3, p4, p2)) { return true; } else if((d3 == 0)&&on_segment(p1, p2, p3)) { return true; } else if((d4 == 0)&&on_segment(p1, p2, p4)) { return true; } else { return false; }}
The code is nice... but this is for my collision code, and it would be best if it gave me the position of the collision.
Or just an explanation about why my original code doesn''t work right would be fine.
Or just an explanation about why my original code doesn''t work right would be fine.
i definitely prefer the linked explanation, especially since its not leaving the dirty work to you ,-)
though i guess i should add this method is ok for 2d only because in 3d precision problems might cause two intersecting lines to slightly miss each other meaning you wont find a solution. calculating the minimum distance between them and see if its 0 or close to 0 might work better.
though i guess i should add this method is ok for 2d only because in 3d precision problems might cause two intersecting lines to slightly miss each other meaning you wont find a solution. calculating the minimum distance between them and see if its 0 or close to 0 might work better.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement