Simplest Detection of two lines intersecting -[RESOLVED]-

[Electroman]

What would be the simplest way to detect if two lines are crossing. This would be only given four coordinates and that the first two join to make one of the lines and the second two form the other line.

i.e.
Line 1: (x₁,y₁) to (x₂,y₂)
Line 2: (x₃,y₃) to (x₄,y₄)

I have an idea but its coming up with loads of cases where I would need to make alterations to the formula.

I just need to simplify it to be able to Say: If Case1 AND Case2 AND Case3 AND ... AND Case(n) Then Intersects.

Thanx.

[Electroman]

I believe this is it, I haven't optimised it yet but I thought I would post it before I did so its not so hard to see what I've done. I'll do a Picture or two in the morning to help explain it and show what the variables all are, as its getting quite late here.

If X2 - X1 = 0 Then
    'This means that Line C is flat...
    
    If Y3 < Y1 Then
        'Y3 is above Line C...
        
        If Y4 > (Mb * (X4 - X3)) + Y3 And X4 > ((Y4 - Y3) / Ma) + X3 Then
            CollisionLand = True
            Exit Function
        End If
        
    ElseIf Y3 > Y1 Then
        'Y3 is below line C...
        
        If Y4 < (Ma * (X4 - X3)) + Y3 And X4 < ((Y4 - Y3) / Mb) + X3 Then
            CollisionLand = True
            Exit Function
        End If
        
    Else
        'Y3 is on Line C...
        
        If X1 < X2 Then
            If X3 > X1 And X3 < X2 Then
                CollisionLand = True
                Exit Function
            End If
        Else
            If X3 < X1 And X3 > X2 Then
                CollisionLand = True
                Exit Function
            End If
        End If
    End If
Else
    
    If Y3 < (Mc * (X3 - X1)) + Y1 Then
        'Y3 is above Line C...
        
        If Y4 > (Mb * (X4 - X3)) + Y3 And X4 > ((Y4 - Y3) / Ma) + X3 Then
            CollisionLand = True
            Exit Function
        End If
        
    [b]ElseIf Y3 > (Mc * (X3 - X1)) + Y1 Then[/b]
        'Y3 is below line C...
        
        If Y4 < (Ma * (X4 - X3)) + Y3 And X4 < ((Y4 - Y3) / Mb) + X3 Then
            CollisionLand = True
            Exit Function
        End If
        
    Else
        'Y3 is ON line C...
        
        If X1 < X2 Then
            If X3 > X1 And X3 < X2 Then
                CollisionLand = True
                Exit Function
            End If
        Else
            If X3 < X1 And X3 > X2 Then
                CollisionLand = True
                Exit Function
            End If
        End If
    End If
End If

EDIT: Changed a < that was the wrong way round and made it bold.

[Electroman]

I made a little test app and it has a slight error so I'll fix that then post then change the code.

[MXK]

EDIT: nvm

[Electroman]

Originally posted by MXK
EDIT: nvm

[MXK]

I wrote a different implementation, but if you got one already then it's not much use. It was C++ anyway as I stopped writing VB as soon as I learned C++.

[Electroman]

Originally posted by MXK
I wrote a different implementation, but if you got one already then it's not much use. It was C++ anyway as I stopped writing VB as soon as I learned C++.

Could I see it anyway because this is becoming a pain in the ass.
I know C++ but I've only been using it a few months.

[MXK]

Sure, keep in mind that I wrote it in about 10 mins and haven't tested it, so can't make guarantees about how well it will work, but the logic looks ok to me.

struct line{
	int x1;
	int x2;
	int y1;
	int y2;
};

void swap(line &l){
	int xt=l.x1;
	int yt=l.y1;
	l.x1=l.x2;
	l.y1=l.y2;
	l.x2=xt;
	l.y2=yt;
}

bool check(line l1, line l2){
	//Make sure that all x1 are <= x2
	if( l1.x1 > l1.x2)
		swap(l1);
	if( l2.x1 > l2.x2)
		swap(l2);

	// Not in the same X
	if( l1.x2 < l2.x1 || l1.x1 > l2.x2)
		return false;
	
	//Find slopes - a
	int a1 = (l1.y2 - l1.y1) / (l1.x2 - l1.x1);
	int a2 = (l2.y2 - l2.y1) / (l2.x2 - l2.x1);

	//Find b in y=ax+b
	int b1 = -1 * a1 * l1.x1 + l1.y1
	int b2 = -1 * a2 * l2.x1 + l2.y1

	//Find intersection
	int xb1;
	int xb2;

	if( l1.x1 < l2.x1){
		xb1=l2.x1;
	}else{
		xb1=l1.x1;
	}

	if( l1.x2 > l2.x2){
		xb2=l2.x2;
	}else{
		xb2=l1.x2;
	}

	// See if the y values cross on range [xb1, xb2]
	if( a1*xb1+b1 < a2*xb1+b2 && a1*xb2+b1 > a2*xb2+b2 )
		return true;
	if( a1*xb1+b1 > a2*xb1+b2 && a1*xb2+b1 < a2*xb2+b2 )
		return true;

	return false;
}

[Electroman]

Thanx there, it doesn't seem to work always though, like say for example:
X1: 60
Y1: 170
X2: 270
Y2: 100
X3: 150
Y3: 200
X4: 200
Y4: 80

Which Looks like:


Theres also the case of division by zero on calculating a1 & a2.
These aren't too much of a problem in my case as I'm calculating a collision between meshes of lines which means the likelyhood that two of the colliding lines work is better than just trying to detect only two lines colliding.

[Electroman]

I worked it out to it doesn't work if Line2 has a negitive gradient.

I'm gonna try and fix it now....

[Electroman]

Ignore my last post I had missed out a Exit Function so the True Value got override by a False , doh.

I think for the case where division by zero I might just slightly off set one of the points.

[TheAlchemist]

hey guys,
the only time 2 lines dont intersect at some point is when they're parallel. I don't know, perhaps what you're trying to do is check if the intersect in a particular locality.
otherwise checking if they're parallel is quite simple:
-> Compute the gradient of each of the lines seperately
( m = change in y/ change in x)
-> if they are not equal then lines intersect.

dunno if thats what ur lookin for.

[MXK]

These aren't equations of lines with infinite length. They both a have an X range which is why after creating equations for each line I'm checking that range only.