Sign in to follow this  

Line intersection algorithm?

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So, I'm in the middle of porting this algorithm from C++ to Javascript.  The biggest challenge is this line intersection code.  Sometimes it works, sometimes it doesn't.  In C++, it works fine, but for Javascript, it only works half of the time.  Since I still have lots to learn about Javascript, any other advice is welcome.

 

These are the relevant parts of the code:

function add_trail()
{
    /* Add a new line */
    var t = new trail_t( user.x, user.y, user.lx, user.ly );
    trails.push(t);
}

function identical_points( t1, t2 )
{
	var t1p1 = { x:t1.x1, y:t1.y1 };
	var t1p2 = { x:t1.x2, y:t1.y2 };
	var t2p1 = { x:t2.x1, y:t2.y1 };
	var t2p2 = { x:t2.x2, y:t2.y2 };
    
	if( t1p1 == t2p1 ) return true;
    if( t1p1 == t2p2 ) return true;
    if( t1p2 == t2p2 ) return true;
    if( t1p2 == t2p1 ) return true;
	
    return false;
}

function handle_trail_intersections()
{
    ...
    
	for( var i = trails.length; i--; )
	{
		for( var j = trails.length; j--; )
		{
			/* Do both of these lines already intersect? */
			if( trails[i].intersection && trails[j].intersection )
				continue;
			
			/* Do the lines have matching points? */
			if( identical_points( trails[i], trails[j] ) )
				continue;
				
			var p1 = { x:trails[i].x1, y:trails[i].y1 };
			var p2 = { x:trails[i].x2, y:trails[i].y2 };
			var p3 = { x:trails[j].x1, y:trails[j].y1 };
			var p4 = { x:trails[j].x2, y:trails[j].y2 };
			
			/* Check for an intersection */
			var intersect_point = check_for_intersection( p1, p2, p3, p4 );
			
			if( intersect_point.positive == true )
			{
				trails[i].intersection = true;
				trails[j].intersection = true;
				
				...
			}
		}
	}
}

And the actual line intersection function:

function check_for_intersection( p1, p2, p3, p4 )
{
	var intersection_data = { x:0, y:0, positive:false };
	var x = [], y = [];
	x[0] = p1.x;x[1] = p2.x;x[2] = p3.x;x[3] = p4.x;
	y[0] = p1.y;y[1] = p2.y;y[2] = p3.y;y[3] = p4.y;

	var d = (x[0] - x[1]) * (y[2] - y[3]) - (y[0] - y[1]) * (x[2] - x[3]);
	
	if( d == 0 ) return intersection_data;
    
	// Get the x and y
	var pre = (x[0]*y[1] - y[0]*x[1]), post = (x[2]*y[3] - y[2]*x[3]);
	var X = ( pre * (x[2] - x[3]) - (x[0] - x[1]) * post ) / d;
	var Y = ( pre * (y[2] - y[3]) - (y[0] - y[1]) * post ) / d;
    
	// Check if the x and y coordinates are within both lines
	if ( X < Math.min(x[0], x[1]) || X > Math.max(x[0], x[1]) ||
        X < Math.min(x[2], x[3]) || X > Math.max(x[2], x[3]) ) return intersection_data;
	if ( Y < Math.min(y[0], y[1]) || Y > Math.max(y[0], y[1]) ||
        Y < Math.min(y[2], y[3]) || Y > Math.max(y[2], y[3]) ) return intersection_data;
    
	intersection_data.x = X;
	intersection_data.y = Y;
	intersection_data.positive = true;
    
	return intersection_data;
}

So, do you think it's the line intersection function?  Or is it the way I'm handling the lines?  The trails[] list forms a line strip using the user's current and previous positions, and the goal is to detect when the lines are intersecting.  Once again, in C++, this works fine.  Not sure why it's problematic in Javascript.

 

On a side note, I'll get rid of the nested for loop later.  I didn't think about it until after writing the implementation.

 

Any ideas?  Thanks.

 

Shogun.

Edited by blueshogun96

Share this post


Link to post
Share on other sites

One thing that is not okay (at least not in general) is testing structures for equality by using the == operator. E.g. 

var a = { x:0, y:1 };
var b = { x:0, y:1 };
alert(a==b);
gives you false. As long as you use simple structures, you can go the following way:
var a = { x:0, y:1 };
var b = { x:0, y:1 };
alert(JSON.stringify(a)==JSON.stringify(b));
although, from a performance point of view, I'd just use
if (t1.x1==t2.x1 && t1.y1==t2.y1) return false;
...

It is still readable. (IMHO copying values just for readability is often counter-productive; for example in check_for_intersection(...), copying the point elements to separate array elements requires me to leave the well introduced semantics of points, introspect what is done, and rethink of the arrangement when analyzing the remaining function body; that makes IMHO no sense.)

 

However, if you suspect check_for_intersection(...) being wrong, do you have tried to write some unit test for it? E.g. pump a couple of defined points into it and compare the result of what you expect. Parallel lines with the same length and a different length, anti-parallel lines, identical lines, orthogonal and not orthogonal lines, and, of course, variants that cross and variants that do not cross. Presumably, if you have seen cases where the algorithm fails, you may have already an idea of what constellation of lines break the run.

Share this post


Link to post
Share on other sites

There's actually a way easier way of doing a line intersection test in 2D, and it's probably better if you're coding in Javascript since JS needs all the speedup it can get. There's a line-line intersection test section in the article below. Let me know if this helps.

 

http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536 

Share this post


Link to post
Share on other sites


A1x+B1y+C1 = A2x+B2y+C2



3x+B1y+C1 = 0
6x+B2y+C2 = 0



3/6 = 1/2
=====



t = (A1/A2);
p = -t;


A1x+B1y+C1 = 0
A2x+B2y+C2 = 0


A1x+B1y+C1 = 0
p * A2x + p * B2y + p * C2 = p * 0


A1x + p * A2 x + B1y + p * B2y + C1 + p*C2 = 0

now ( A1x + p * A2 x ) is 0

you end with

B1y + p * B2y + C1 + p*C2 = 0

then after you have y you calculate x

then

you check for collision

A1*(calculated x) +B1*(calculated y)+C1 = 0

if its equal to 0 you have collision

then after all you need to check if the point lies within segment 

 

(you can check first or second segment - lets say its first) to do this you check distance between start point of first segment and your result and distance from end point of this segment to the result if oth are <= distance between start and end you have collision


if second testing segment vector x is equal to 0 it will crack to make it work you just insert the Y of it to the equation (since Y i constant)

A1x+B1y+C1 = 0
A2x+B2y+C2 = 0

 

i am not sure if theres are more cases about segments parallel to the screen
 

 

of you have to check if they are parallel

Edited by WiredCat

Share this post


Link to post
Share on other sites

There's actually a way easier way of doing a line intersection test in 2D, and it's probably better if you're coding in Javascript since JS needs all the speedup it can get. There's a line-line intersection test section in the article below. Let me know if this helps.

 

http://www.gamedev.net/page/resources/_/technical/math-and-physics/advanced-intersection-test-methods-r3536 

 

I would take a look at something like this. Not like it would have to be a line for line port.

Share this post


Link to post
Share on other sites

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this