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.

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);

var a = { x:0, y:1 };
var b = { x:0, y:1 };
alert(JSON.stringify(a)==JSON.stringify(b));

if (t1.x1==t2.x1 && t1.y1==t2.y1) return false;
...

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.

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