Which side of a line segment is a point on?

BlitzMax Forums/BlitzMax Programming/Which side of a line segment is a point on?

zoqfotpik

(Posted 2012) [#1]

Is there a canned function for telling what side of a line segment a given point is on, and the distance from the segment?

col	(Posted 2012) [#2]

Look up 'dot product'. It will give you closest distance to the line, and which 'side'. Plus if you learn the theory of it, it will be best math friend!

Last edited 2012

matibee

(Posted 2012) [#3]

I agree with col. Learn some of this stuff, it's really not that bad, and you'll find it really useful.

Anyway, just to give you a head start here's some of my point/line related base code...


'======================================================================================================================
'======================================================================================================================
'	
'	pointPointDistance2d
'	--------------------
'
'======================================================================================================================
Function pointPointDistance2d:Double ( v1:Vector2d, v2:Vector2d )
	Return Sqr( ((v2.x - v1.x) * (v2.x - v1.x)) + ((v2.y - v1.y) * (v2.y - v1.y)) )
End Function
'======================================================================================================================
'======================================================================================================================
'	
'	pointDistanceToLineSegment2d
'	----------------------------
'
'		Closest point (in 2d) between a point and line segment (could be end point, start point or a point on the line)
'
'======================================================================================================================
Function pointDistanceToLineSegment2d:Double ( p:Vector2d, v1:Vector2d, v2:Vector2d )
	 ' get the vector of the line direction
	Local vLine:Vector2d = v2d(v2.x - v1.x, v2.y - v1.y )
	
	' get the closest point on the plane of the lane
	Local u:Double = ((p.x - v1.x) * ( v2.x - v1.x ) + ( p.y - v1.y ) * ( v2.y - v1.y ) ) ..
						/ ((vLine.x * vLine.x)+(vline.y*vline.y))
	
	' If the closest point on the plane is also on the line, u will be between 0.0 (the start) and (1.0) of the line
	If ( u < 0 )
		Return pointPointDistance2d( p, v1 ) ' closest point is the start point
	Else If ( u > 1.0 )
		Return pointPointDistance2d( p, v2 )	' closest point is the end point
	End If
	
	' closest point is on the line, find the actual intersection point
	Local vecInters:Vector2d = v1.NewCopy()
	vecInters.x :+ vLine.x * u
	vecInters.y :+ vLine.y * u
	Return pointPointDistance2d( vecInters, p ) ' return the distance
End Function
'======================================================================================================================
'======================================================================================================================
'	
'	pointDistanceToLine2d
'	---------------------
'
'		Closest distance to a line (AN INFINITE LINE!!) in 2d
'								 ------------------
'
'======================================================================================================================
Function pointDistanceToLine2d:Double ( p:Vector2d, v1:Vector2d, v2:Vector2d )
	 ' get the vector of the line direction
	Local vLine:Vector2d = v2d(v2.x - v1.x, v2.y - v1.y )
	
	' get the closest point on the plane of the lane
	Local u:Double = ((p.x - v1.x) * ( v2.x - v1.x ) + ( p.y - v1.y ) * ( v2.y - v1.y ) ) ..
						/ ((vLine.x * vLine.x)+(vline.y*vline.y))
	
	' for the closest point on the line, find the actual intersection point
	Local vecInters:Vector2d = v1.NewCopy()
	vecInters.x :+ vLine.x * u
	vecInters.y :+ vLine.y * u
	Return pointPointDistance2d( vecInters, p ) ' return the distance
End Function
'======================================================================================================================
'======================================================================================================================
'	
'	pointProjectedOntoLine2d
'	---------------------
'
'		Solves closest point on a line (AN INFINITE LINE!!) in 2d
'								     ------------------
'
'======================================================================================================================
Function pointProjectedOntoLine2d:Vector2d ( p:Vector2d, v1:Vector2d, v2:Vector2d )
	 ' get the vector of the line direction
	Local vLine:Vector2d = v2d(v2.x - v1.x, v2.y - v1.y )
	' get the closest point on the plane of the lane
	Local u:Double = ((p.x - v1.x) * ( v2.x - v1.x ) + ( p.y - v1.y ) * ( v2.y - v1.y ) ) ..
						/ ((vLine.x * vLine.x)+(vline.y*vline.y))
	Return v2d( v1.x + (vLine.x * u), v1.y + (vLine.y * u) )
End Function

you'll be interested in "pointDistanceToLineSegment2d".

A line segment has a start and an end point, the closest point to a line segment could be the start-point, the end-point or any point between the two.

To use the code above you'll also need my 2d vector type..

SuperStrict 
'======================================================================================================================
'======================================================================================================================
'
'	3dTypes.bmx
'	===========
'
'	All the types are specified in this file in order that the F L O A Ting point accuracy can be changed between
'	F L O A T  and  D O U B L E  by performing a simple find/replace
'	
'
'
'  	NewCopy vs Copy
'  	===============
'
'	C o p y			will take the values from the object passed in, to set its own internal values
'
' 	N e w C o p y 		shall always return a new object with the same values as the original
'
'
'======================================================================================================================
'======================================================================================================================

Const DOUBLE_PRECISION:Double = 0.00003:Double

Const TWOPI:Double  = Pi * 2.0:Double 
 

Function _fuzzycomp:Int( a:Double, b:Double, c:Double = DOUBLE_PRECISION )
	Return ((a + c >= b) And (a - c <= b) )
End Function 
'-----------------------------------------------------------------------------------------------------------------
Function _fuzzylessthanequals:Int( a:Double, b:Double, c:Double = DOUBLE_PRECISION )
	Return _fuzzycomp( a, b ) Or a < b
End Function 
'-----------------------------------------------------------------------------------------------------------------
Function _fuzzygreaterthanequals:Int( a:Double, b:Double, c:Double = DOUBLE_PRECISION )
	Return _fuzzycomp( a, b ) Or a > b
End Function 

'======================================================================================================================
'======================================================================================================================
Type Vector2d
	'-----------------------------------------------------------------------------------------------------------------
	Function Create:Vector2d( xx:Double, yy:Double )
		Local v:Vector2d = New Vector2d
		v.x = xx
		v.y = yy
		Return v
	End Function 
	'-----------------------------------------------------------------------------------------------------------------
	Function Read:Vector2d( f:TStream )
		Local v:Vector2d = New Vector2d
		Local b:Byte = ReadByte( f )
		Assert ( b And $E0 )
		If ( b = $E1 )
			v.x = ReadFloat( f )
			v.y = ReadFloat( f )
		Else If ( b = $E2 )
			v.x = ReadDouble( f )
			v.y = ReadDouble( f )
		End If 
		Return v
	End Function 
	'-----------------------------------------------------------------------------------------------------------------
	Method Write( f:TStream, accuracy:Byte = 2 )
		Assert ( accuracy = 1 Or accuracy = 2 )
		WriteByte( f, $E0 + accuracy )
		If ( accuracy = 1 ) ' all floats
			WriteFloat( f, x ) 
			WriteFloat( f, y )
		Else 
			WriteDouble( f, x ) 
			WriteDouble( f, y )
		End If 
	End Method
	'-----------------------------------------------------------------------------------------------------------------
	Method NewCopy:Vector2d()
		Return Create( x, y )
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Copy( v:Vector2d )
		x = v.x
		y = v.y
	End Method 	
	'-----------------------------------------------------------------------------------------------------------------
	Method Set( xx:Double, yy:Double )
		x = xx
		y = yy
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Add( other:Vector2d )
		x :+ other.x
		y :+ other.y
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Mult( other:Vector2d )
		x :* other.x
		y :* other.y
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Scale( s:Double )
		x :* s
		y :* s
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Length:Double ()
		Return Sqr( x * x + y * y )
	End Method 
	'-----------------------------------------------------------------------------------------------------------------
	Method Normalise()
		Local l:Double = Length()
		If ( l )
			x :/ l
			y :/ l
		End If 
	End Method
	'-----------------------------------------------------------------------------------------------------------------
	Method FuzzyCompare:Int ( b:Vector2d, tol:Double = DOUBLE_PRECISION )
		Return _fuzzycomp( x, b.x, tol ) And _fuzzycomp( y, b.y, tol )
	End Method
	'-----------------------------------------------------------------------------------------------------------------
	Method ToString:String()
		Return x + ", " + y
	End Method 
	'-----------------------------------------------------------------------------------------------------------------		
	Field x:Double, y:Double
End Type 
'======================================================================================================================
Function V2d:Vector2d( xx:Double, yy:Double )
	Return Vector2d.Create( xx, yy )
End Function
'======================================================================================================================
Function V2dDuplicate:Vector2d( v:Vector2d )
	Return v.NewCopy()
End Function 
'======================================================================================================================
Function V2dDot:Double( a:Vector2d, b:Vector2d )
	Return (a.x * b.x + a.y * b.y)
End Function 
'======================================================================================================================
Function V2dAdd:Vector2d( a:Vector2d, b:Vector2d )
	Return V2d( a.x + b.x, a.y + b.y )
End Function 
'======================================================================================================================
Function V2dSubtr:Vector2d( a:Vector2d, b:Vector2d )
	Return V2d( a.x - b.x, a.y - b.y )
End Function 
'======================================================================================================================
Function V2dMult:Vector2d( a:Vector2d, b:Vector2d )
	Return V2d( a.x * b.x, a.y * b.y )
End Function 
'======================================================================================================================
Function V2dScale:Vector2d( a:Vector2d, s:Double )
	Return V2d( a.x * s, a.y * s )
End Function 
'======================================================================================================================
Function V2dFuzzyCompare:Int( a:Vector2d, b:Vector2d, tol:Double = DOUBLE_PRECISION )
	Return a.FuzzyCompare( b, tol )
End Function

As you'll see it uses doubles not floats, but it's laid out in such a way that you can find/replace "Double" with "Float" (and vice versa) to switch from one to the other.

zoqfotpik

(Posted 2012) [#4]

I actually knew trig very well at one point, I just can't remember any of it. One of these days I want to spend four hours a day on math for a couple of years.

Thanks for the assistance.

Last edited 2012