Skip to main content
GameDev.net gamedev.net
🔒 Locked

2D line intersection problem

Started by Darc Jun 22, 2004 at 7:37 PM 10 replies 2k views
Original Post
Darc
Darc
hey all, I used the code from the article at http://www.gamedev.net/reference/articles/article423.asp but it doesn't seem to work properly. I really don't understand this type of math at all (and I mean I have 0 understanding of any of it) but I would really like a function that could return the intersection point between two lines. Any help would be greatly appreciated.
Samith
Samith
I would use this method.

That one is easier to understand and deals with vertical lines better.
jflanglois
jflanglois
OK, first off, what do you mean it doesn't work? Give an example of how you are trying to use it.

Here is an example of it working:

int main() {	float *x = new float(-1.0), *y = new float(-1.0);	Intersect_Lines( 0, 0, 10, 10, 0, 10, 10, 0, x, y );	cout << *x << endl << *y << endl;	system( "pause" );	return 0;}


I'm a bit too jetlagged at the moment to give you an opinion on the method used.
jflanglois
jflanglois
I've got one for you using the method in the link kindly posted by Samith.

#include <iostream>using namespace std;struct point {	bool valid;	float x, y;};point intersect( float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4 ) {	point inter;	float udenom = ( y4 - y3 ) * ( x2 - x1 ) - ( x4 - x3 ) * ( y2 - y1 );	if ( udenom == 0 ) {		inter.valid = false;		return inter;	}	inter.valid = true;	inter.x = x1 + ( ( x4 - x3 ) * ( y1 - y3 ) - ( y4 - y3 ) * ( x1 - x3 ) ) / udenom * ( x2 - x1 );	inter.y = y1 + ( ( x2 - x1 ) * ( y1 - y3 ) - ( y2 - y1 ) * ( x1 - x3 ) ) / udenom * ( y2 - y1 );	return inter;}int main() {	point inter;	if ( ( inter = intersect( 0, 0, 10, 10, 0, 10, 10, 0 ) ).valid == false )		cout << "Lines do not intersect or are equal." << endl;	else cout << inter.x << endl << inter.y << endl;	system( "pause" );    return 0;}


Seems to work pretty well. I haven't tested it extensively yet though...

[edit] little simplification.
[edit2] Another simplification, stupid me...

[disclaimer] This is probably not the best implementation.

[Edited by - jflanglois on June 22, 2004 9:54:28 PM]
jacksaccountongamedev
jacksaccountongamedev
Perhaps you are confusing the term 'line' with 'line segment'. When talking of a line in mathematics you are referring to a line of infinite length - it never ends and simply continues on in opposite directions. However, a line segment is, as the title suggests, a segment of a line - a line of finite length. Usually a line segment is defined by a starting and end point.
The code given is designed to test the intersection between two 2d lines, of which will always exist unless the lines are exactly parallel. Therefore the code will return intersection points beyond the end points of two line segments if the segments do not intersect.
The code can still be used. You simply need to first determine *if* the two segments given intersection. This can be done in several different ways - one easy method described bellow:

Given segment A0 - A1 and segment B0 - B1
If A0 and AI are on the same side of infinite line B0 - B1 or B0 and B1 are on the same side of infinite line A0 - A1 then not intersection exists. Otherwise and intersection does exist and the code in the article can thereby be used to determine the intersection point. Discovering if a point is on the positive or negative side of a line is a simple matter of checking the 2D cross product of ( Point - SegmentPoint0 ) with ( SegmentPoint1 - SegmentPoint0 ).
The problem with this method is when the points of one segment actually lie on the line formed by the other. This can be accounted for with a little more coding.

Anyhow - so you discover if the two segments intersect and if they do you determine the intersection point. Or that may not even be the problem, and I just threw ten minutes away typing something you already know?

Jackson Allan
Darc
Darc
I need the line intersection for firing projectiles (2d action game) and when they hit *solid* tiles, they explode, stop, and such, but I can't get the intersection quite right, here's my code, and it works *most* of the time (maybe 90%)

//rct = the Solid tile that the projectile hit//xPrev/yPrev = starting point of projectile//xPos/yPos = current point of projectileif(ProjectilePtr->m_MoveX > 0) {	if(LineIntersect(xPrev, yPrev, xPos, yPos, (float)rct.left, (float)-1e+10, (float)rct.left, (float)1e+10, &xPos, NULL))	{		xPos -= ProjectilePtr->m_Image.GetWidth() / 2;	}}if(ProjectilePtr->m_MoveX < 0) {	if(LineIntersect(xPrev, yPrev, xPos, yPos, (float)rct.right, (float)-1e+10, (float)rct.right, (float)1e+10, &xPos, NULL))	{		xPos -= ProjectilePtr->m_Image.GetWidth() / 2;	}}if(ProjectilePtr->m_MoveY > 0) {	if(LineIntersect(xPrev, yPrev, xPos, yPos, (float)-1e+10, (float)rct.top, (float)1e+10, (float)rct.top, NULL, &yPos))	{ 		yPos -= ProjectilePtr->m_Image.GetHeight() / 2;	}}if(ProjectilePtr->m_MoveY < 0) {	if(LineIntersect(xPrev, yPrev, xPos, yPos, (float)-1e+10, (float)rct.bottom, (float)1e+10, (float)rct.bottom, NULL, &yPos))	{		yPos -= ProjectilePtr->m_Image.GetHeight() / 2;	}}BOOL cProjectile::LineIntersect(float Ax,float Ay,float Bx,float By,						   float Cx,float Cy,float Dx,float Dy,						   float *xi,float *yi){	float q = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx);	float r = ((Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy)) / q;	if(r < 0.0f || r > 1.0f) 		return FALSE;	float s = ((Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)) / q;	if(s < 0.0f || s > 1.0f) 		return FALSE;	if(xi != NULL) 		*xi = Ax + (Bx-Ax) * r;	if(yi != NULL) 		*yi = Ay + (By-Ay) * r;	return TRUE;}
jflanglois
jflanglois
Sorry, forgot to login. Also, can the tiles move or not?
Darc
Darc
before I go on, thanks to all for replying so fast (why I love GameDev.net)

In the before mentioned code, the Tile is already tested to make sure its solid (impassible by anything), which is why I don't think it works. (Tiles do NOT move btw, there's a Camera class to make sure things are rendered in position)

My collision detection first checks to see if the projectile is on a solid tile, then it does line intersections to see where exactly it hit it, so it can draw the sprite (the subtracting of half the image's width, is to make the blast appear over the line where it hit, giving it a kool graphics effect)

What I'm thinking is, that I should probably test line intersections without making sure its on a solid tile in the first place (eliminating the issues of "skipping" as you mentioned) But testing each projectile's path against all the solid tiles seems inefficient and processing-costly, since the game involves guns that can fire up to 30-50 times per second. Is there a better way to do this?
Darc
Darc
sorry it took me a while to get back on this one (vacation)

I can't give a picture at the moment, not at my work computer, but the projectiles are not bound by any constraints. When the user clicks somewhere, the projectile is set to start at the player's position, and to stop where the user clicked. They are not bound by the tiles.

Topic Locked

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

Sign in to reply to this topic.