Skip to main content
gamedev.net
🔒 Locked

My line intersection code

Started by starstriker1 Nov 26, 2003 at 6:09 PM 6 replies 1.1k views
Original Post
starstriker1
starstriker1
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: 
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.
Trienco
Trienco
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.
f@dzhttp://festini.device-zero.de
starstriker1
starstriker1
(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?
Raptor85
Raptor85
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.

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; 
	}
}
starstriker1
starstriker1
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.
Trienco
Trienco
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.
f@dzhttp://festini.device-zero.de
starstriker1
starstriker1
I used raptors code, because it was quicker and easier to implement. However, I''ve bookmarked the linked site for future use, so I can make my own line intersection algorithim on another project.

Thanks.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.