Lines and Vectors Intersection

BlitzMax Forums/BlitzMax Programming/Lines and Vectors Intersection

Haramanai

(Posted 2005) [#1]

I hope I am not writing down something that allready had been posted, but here I go:
I am trying to get the intersection point of two lines but as we know lines in mathimatics starts from negative infinity and gos to positive infinty. I found how to get the intersection point of two lines in the great site MathWorld in the page : http://mathworld.wolfram.com/Line-LineIntersection.html
So I wroted a litle program to get this point. And interact a litle bit with the lines.
Here it is.

Strict

Framework brl.Math
Import BRL.StandardIO
Import BRL.Max2d
Import BRL.GLMax2D

Global x1:Int = 10
Global y1:Int = 10
Global x2:Int = 100
Global y2:Int = 160
Global x3:Int = 10
Global y3:Int = 100
Global x4:Int = 100
Global y4:Int = 60



Local xi = ( (x1 * y2 - x2 * y1) * (x3 - x4) - (x3 * y4 - x4 * y3) * (x1 - x2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )
Local yi = ( (x1 * y2 - x2 * y1) * (y3 - y4) - (x3*y4 - x4 * y3) * (y1 - y2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )


SetGraphicsDriver GLMax2DDriver()
Graphics 640 , 480 , 0

While Not KeyDown(Key_escape)
	Cls
	SetColor 255 , 0 , 0
	DrawLine x1 , y1 , x2 , y2
	SetColor 0 , 255 , 0
	DrawLine x3 , y3 , x4 , y4
	SetColor 0 , 0 , 255
	DrawLine xi , 0 , xi , 480
	DrawLine 0 , yi , 640 , yi
	keys()
	xi = ( (x1 * y2 - x2 * y1) * (x3 - x4) - (x3 * y4 - x4 * y3) * (x1 - x2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )
	yi = ( (x1 * y2 - x2 * y1) * (y3 - y4) - (x3*y4 - x4 * y3) * (y1 - y2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )


	
	Flip
	FlushMem
Wend
End

Function Keys()
	If KeyDown(Key_1)
		x1 = MouseX()
		y1 = MouseY()
	End If
	
	If KeyDown(Key_2)
		x2 = MouseX()
		y2 = MouseY()
	End If
	
	If KeyDown(Key_3)
		x3 = MouseX()
		y3 = MouseY()
	End If
	If KeyDown(Key_4)
		x4 = MouseX()
		y4 = MouseY()
	End If
	
End Function

Evrything its ok but I need to get the point only if there is intersection betwen the two virtual lines as drawn and not as real lines. Or I can say to get the vector vector Intersection.

Tibit

(Posted 2005) [#2]

I tried to break this one. I had some success but I didn't solve it. Something is still wrong.

Anyhow here is my modification of your code which shows if a point is on the line:

Strict

Framework brl.Math
Import BRL.StandardIO
Import BRL.Max2d
Import BRL.GLMax2D

Global x1:Int = 50
Global y1:Int = 200
Global x2:Int = 500
Global y2:Int = 200

Global x3:Int = 10
Global y3:Int = 100
Global x4:Int = 100
Global y4:Int = 60



Local xi = ( (x1 * y2 - x2 * y1) * (x3 - x4) - (x3 * y4 - x4 * y3) * (x1 - x2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )
Local yi = ( (x1 * y2 - x2 * y1) * (y3 - y4) - (x3*y4 - x4 * y3) * (y1 - y2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )


SetGraphicsDriver GLMax2DDriver()
Graphics 640 , 480 , 0

While Not KeyDown(Key_escape)
	
	SetColor 255 , 0 , 0 'RED
	DrawLine x1 , y1 , x2 , y2
	
'	SetColor 0 , 255 , 0 'GREEN
'	DrawLine x3 , y3 , x4 , y4
	
	keys()
	
	'If LinesCollide( xi , yi , x1 , y1, x2, y2, x3, y3, x4, y4) Then DrawText "POINT ON LINE!!!!  X= "+xi+"  Y= "+yi,20,30
	LinePointCollide( x1 , y1, x2, y2, MouseX(), MouseY() )
		
	SetColor 0 , 0 , 255 'Blue
'	DrawLine xi , 0 , xi , 480
'	DrawLine 0 , yi , 640 , yi	
	DrawOval xi-5,yi-5,10,10 'Draw a Oval where the lines intersect
	
	Flip;Cls;	FlushMem
Wend
End

'First X,Y is the X,Y of the intersection
'First line is: (x1, y1)  to (x2, y3)
'Second line is:(x3, y3)  to (x4, y4)
Function LinesCollide( xi Var, yi Var, x1 , y1, x2, y2, x3, y3, x4, y4)
	xi = ( (x1 * y2 - x2 * y1) * (x3 - x4) - (x3 * y4 - x4 * y3) * (x1 - x2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )
	yi = ( (x1 * y2 - x2 * y1) * (y3 - y4) - (x3*y4 - x4 * y3) * (y1 - y2) ) / ( (x1 - x2) * (y3 - y4) - (x3 - x4) * (y1 - y2) )
	If LinePointCollide( x1 , y1, x2, y2, xi, yi) And LinePointCollide( x3 , y3, x4, y4, xi, yi) Return True Else Return False
EndFunction

Function LinePointCollide( x1 , y1, x2, y2, PointX, PointY)

	Local LineX,LineY
	Local LineXR,LineYR
	Local LinePX,LinePY
	Local LinePXR,LinePYR	

	LineX  = x2 - x1 'x1 - x2
	LineY  = y2 - y1 'y1 - y2
	
	LineXR = x1 - x2 'x2 - x1 
	LineYR = y1 - y2 'y2 - y1
		
	LinePX  = PointX - x1
	LinePY  = PointY - y1

	LinePXR = PointX - x2
	LinePYR = PointY - y2
	
	
	
	'Line End to Point
	SetColor 0 , 255 , 0 ' GREEN

	'DrawLine x1,y1,x1 + LineX, y1 + LineY
	DrawLine x1,y1,PointX,PointY

	'Line Start To point
	SetColor 0 , 0 , 255 ' BLUE
	DrawLine x2,y2,PointX,PointY

'	DrawLine x2,y2,x2 + LineXR ,y2 + LineYR
	
	SetColor 255,255,255		
	
	
	
	Local R#,U#

	R# = ( LineX*LinePX + LineY*LinePX ) 'Dot product
	U# = ( Sqr(LineX*LineX + LineY*LineY) )*( Sqr( LinePX*LinePX + LinePY*LinePY ) )
	
	If U = 0 Return
	
	Local Angle# = ACos( (R/U) )

	DrawText "Angle LineStart to Point : "+Angle,20,80


	R# = ( LineXR*LinePXR + LineY*LinePXR ) 'Dot product
	U# = ( Sqr(LineXR*LineXR + LineYR*LineYR) )*( Sqr( LinePXR*LinePXR + LinePYR*LinePYR ) )
	
	If U = 0 Return
	
	Local AngleR# = ACos( (R/U) )
	DrawText "Angle LineEnd   to Point : "+AngleR,20,110

	If Angle = 0 And AngleR = 0 Then Return True Else Return False

EndFunction



Function Keys()
	If KeyDown(Key_1)
		x1 = MouseX()
		y1 = MouseY()
	End If
	
	If KeyDown(Key_2)
		x2 = MouseX()
		y2 = MouseY()
	End If
	
	If KeyDown(Key_3)
		x3 = MouseX()
		y3 = MouseY()
	End If
	If KeyDown(Key_4)
		x4 = MouseX()
		y4 = MouseY()
	End If
	
End Function

I tried to think in the terms of vectors and you should really make your calculations a little more clear :)

It's impossible to follow your vector math (no offence), but as it works, what can I say.. Nice Work! My point on line might be the solution, yet my point on line doesn't seem to work unless the line is horizontal, which is strange - I mean it is all vector math.. (I need some help here)

Anyhow my idea for solving this very problem was a little different (I haven't chack that math site yet). My idea was to calculate the normal of the line. And with the help of the normal I could calculate the perpendicular distance to the line - in other words the closest distance to the line from this point. (This is what your function does - it check if we collide with an infinite line)

If you run the modifyed example you can see that I calculate the angles from each of the end points of the line to the point we want to check. If both angles are 0 then the point is on the line.

It would be great if we could get this to work, I'm so sick and tired of vector math right now ;)

Warpy

(Posted 2005) [#3]

Here you go

Strict

Framework brl.Math
Import BRL.StandardIO
Import BRL.Max2d
Import BRL.GLMax2D

Global x1:Int = 10
Global y1:Int = 10
Global x2:Int = 100
Global y2:Int = 160
Global x3:Int = 10
Global y3:Int = 100
Global x4:Int = 100
Global y4:Int = 60



Local xi
Local yi 
Local lambda#				'distance of intersection along first line 
Local mu#					'distance of intersection along second line
Local dx1#,dy1#,dx2#,dy2#	'direction vectors of the lines

SetGraphicsDriver GLMax2DDriver()
Graphics 640 , 480 , 0

While Not KeyDown(Key_escape)
	Cls
	
	
	dx1# = x2-x1
	dy1# = y2-y1
	dx2# = x4-x3
	dy2# = y4-y3
	lambda# = ( y3 - y1 + (dy2/dx2)*( x1 - x3 )) / ( dy1 - dy2*dx1/dx2 )
	If lambda#>=0 And lambda#<=1 'if intersection lies on first line
		mu# = ( x1 + dx1*lambda - x3 ) / dx2 
		If mu#>=0 And mu#<=1 'if intersection also lies on second line
			xi = x1 + lambda*dx1
			yi = y1 + lambda*dy1
			SetColor 0 , 0 , 255
			DrawLine xi , 0 , xi , 480
			DrawLine 0 , yi , 640 , yi
		EndIf
	EndIf

	SetColor 255 , 0 , 0
	DrawLine x1 , y1 , x2 , y2
	SetColor 0 , 255 , 0
	DrawLine x3 , y3 , x4 , y4
	keys()

	
	Flip
	FlushMem
Wend
End

Function Keys()
	If KeyDown(Key_1)
		x1 = MouseX()
		y1 = MouseY()
	End If
	
	If KeyDown(Key_2)
		x2 = MouseX()
		y2 = MouseY()
	End If
	
	If KeyDown(Key_3)
		x3 = MouseX()
		y3 = MouseY()
	End If
	If KeyDown(Key_4)
		x4 = MouseX()
		y4 = MouseY()
	End If
	
End Function

(long-winded and confusing explanation follows. Get a real maths teacher to teach you if you need to understand this)

Vector lines: consider a line as the set of vectors defined by a starting point plus an arbitrary multiple of another vector (the direction vector).
So with two lines L1 and L2, starting at A and B with direction vectors r and s, respectively:

A point on line L1 = A + r*lambda
i.e. L1x = Ax + rx*lambda
L1y = Ay + ry*lambda
A point on line L2 = B + s*mu
i.e. L2x = Bx + sx*lambda
L2y = By + sy*lambda

When they intersect, L1 = L2, so

A + r*lambda = B + s*mu

that is,

Ax + rx*lambda = Bx + sx*mu [1]
and
Ay + ry*lambda = By + sy*mu [2]

With a bit of rearranging of [1]:

(Ax- Bx + rx*lambda)/sx = mu

And sticking that back into [2]

Ay + ry*lambda = By + sy*(Ax - Bx + rx*lambda)/sx

Collecting all the lambda terms to the left:

lambda*( ry -sy*rx/sx ) = ( By - Ay +sy*(Ax - Bx)/sx )

And finally

lambda = ( By - Ay + sy*(Ax-Bx)/sx ) / ( ry - sy*ry/sx )

So what does lambda mean? lambda = 0 at the start of the line (Ax,Ay) [=(x1,y1) in your code] and it equals 1 at the end of the line (Ax+rx,Ay+ry) [=(x2,y2) in your code] because the length of the direction vector is the same as the length of the line. So the point of intersection is in the first line when 0<=lambda<=1, and if you solve for mu, the same thing applies for the second line. Some more rearranging gets you the intersection point.

Hope this helps.

Tibit

(Posted 2005) [#4]

Brilliant!

Thank you sooo much!

Cleaned up. Function for testing collision between two lines with a simple example.

Strict

Framework BRL.Max2d
Import BRL.GLMax2D

'Test Lines
Local x1:Int = 10
Local y1:Int = 10
Local x2:Int = 100
Local y2:Int = 160
Local x3:Int = 10
Local y3:Int = 100
Local x4:Int = 100
Local y4:Int = 60

Local LastMouseX,LastMouseY,MouseDX#,MouseDY#

Local InterSectionX#, InterSectionY#

SetGraphicsDriver GLMax2DDriver()
Graphics 640 , 480 , 0

While Not KeyDown(Key_escape)
	Cls
	
	If KeyDown(Key_1)
		x1 = MouseX()
		y1 = MouseY()
	End If
	
	If KeyDown(Key_2)
		x2 = MouseX()
		y2 = MouseY()
	End If
	
	If KeyDown(Key_3)
		x3 = MouseX()
		y3 = MouseY()
	End If
	If KeyDown(Key_4)
		x4 = MouseX()
		y4 = MouseY()
	End If	

	If LinesCollide(InterSectionX, InterSectionY, x1, y1, x2, y2, x3, y3, x4, y4 )
		SetColor 0 , 0 , 255
		DrawLine InterSectionX, 0 , InterSectionX, 480
		DrawLine 0 , InterSectionY, 640 , InterSectionY		
	EndIf
	
	SetColor 255 , 0 , 0
	DrawLine x1 , y1 , x2 , y2
	SetColor 0 , 255 , 0
	DrawLine x3 , y3 , x4 , y4

	DrawText "DX : "+MouseDX+"  DY: "+MouseDY, 20,100

	LastMouseX = MouseX()
	LastMouseY = MouseY()

	Flip
	FlushMem
Wend
End

Here is the Magic Function:

Function LinesCollide( xi# Var , yi# Var, x1#, y1#, x2#, y2#, x3#, y3#, x4#, y4#)

	Local L1d:Float			'distance of intersection along first line 
	Local L2d:Float			'distance of intersection along second line
	Local L1x#,L1y#,L2x#,L2y#	'direction vectors of the lines

	L1x = x2-x1
	L1y = y2-y1
	L2x = x4-x3
	L2y = y4-y3
		
	L1d = ( y3 - y1 + (L2y/L2x)*( x1 - x3 )) / ( L1y - L2y*L1x/L2x )
	
	If L1d >=0 And L1d <=1 'if intersection lies on first line
		L2d  = ( x1 + L1x*L1d - x3 ) / L2x 
		If L2d >=0 And L2d <=1 'if intersection also lies on second line
			xi = x1 + L1d*L1x
			yi = y1 + L1d*L1y
			Return True
		EndIf
	EndIf
	Return False			
	
EndFunction

USE:

Check a bullets velocity vector against a another line. This could be a wall or another objects speed vector. Which would mean that no two object would be able to overlap even if they both travel in light speed. Also this is perfect for Beem weapons. It also makes implentation of bounce and slide against line-walls simpler.

About bouncing:

r = 2*n*AngleBetweenVectors( n, v ) - v

r is the resulting bounce.
n is the normal of the surface (the line).
v is the velocity vector of the object in question.

Which would be the easiest way to get the normal of the line? In other word a vector perpendicular (in this function) to the line vector?

Having the normal also means we can see which side of the line we are on, in case that would matter.

Unanswered questions:
What is the best way to handle object that have a size ontop of their velocity vector? For example think a ball against a wall or a rect against a wall. I was thinking about having my maps built up with "collide" lines which you bounce/hit/slide against. This solution allows for slim walls with garanteed collision.

sswift

(Posted 2005) [#5]

There's already a function in the code archive that does this. I know because I wrote it. :-) You shoudl really check there when you need a math funciton like this there's lots of such functions.

Tibit

(Posted 2005) [#6]

That's typical. I hate the code archives because it is a pain to search and browse. Why is there not a simple database which you can quire for all code involving different subjects instead of a few general main areas.

EDIT-
Na didn't find your entry in the code archives..
Can you link?

sswift

(Posted 2005) [#7]

Click my username for my code archives entries. Look for lines intersect or ray intersect or line segment. I forget which I called it. I think it was ray, because my function can handle lines, rays, and line segments.

Warpy

(Posted 2005) [#8]

wave - that's a good point. del.icio.us tagging of the code archives would be useful indeed... I might have a play around with that idea

sswift's line normal code is here - http://www.blitzbasic.com/codearcs/codearcs.php?code=450

Your unanswered question:
You'll need to keep track of the old position of your object, so before you apply the velocity, set
ox = x
oy = y
Then once you've applied the velocity, check the line position -> position + normal for intersection with each line , where the normal vector is facing outwards. This time you still need 0<=lambda<=0, but if mu <= size, then the object has touched or crossed the line.
At the point where the object first touched the line mu = size, so with some rearranging of the stuff in my last post:

mu = size = (Ax + rx*lambda - Bx) / sx 'Ax = startpoint of line, rx = direction of line, Bx = ox, sx = normal vector of line.

And rearranging a bit more, you get the point of collision as:
xi = Ax + rx*lambda + size*sx
yi = Ay + ry*lambda + size*sy

So there you go :)
This is all very similar to what I've been doing lately, you'd better not be making a better game than me! ;)

Tibit

(Posted 2005) [#9]

Thanks Warpy! This has help me a lot!

Haramanai

(Posted 2005) [#10]

Thanks evryone.
At last I am unstacked.
I gues I must find my old Math books. And start to learn the english traslation of the Math words.