Need some math

BlitzPlus Forums/BlitzPlus Programming/Need some math

Miracle

(Posted 2003) [#1]

I'm looking for an algorithm that can tell me if point A,B is within a certain distance of line segment C,D - E,F in 2D. That's all I need, a yes or no answer. Finding the actual distance would be nice, but not necessary. Also, the fewer square roots the better.

Either Google's no help or I'm typing in the wrong thing ...

sswift

(Posted 2003) [#2]

Yes.

DJWoodgate

(Posted 2003) [#3]

Don't know how you missed it ;) The first thing google pulled for me was the necessary code from Paul Bourkes site.
Not sure if this is the most efficient though. Two square roots, though you can dispense with the second one if you test against distance squared.

Graphics 640,480,0,2
SetBuffer BackBuffer()
HidePointer

x1#=Rand(0,500)
y1#=Rand(0,300)
x2#=x1+Rand(300)
y2#=y1+Rand(200)

Repeat
	Cls
	
	If KeyHit(57) Then
	
		x1#=Rand(0,500)
		y1#=Rand(0,300)
		x2#=x1+Rand(300)
		y2#=y1+Rand(200)
	
	EndIf
	
	x3#=MouseX()
	y3#=MouseY()
	
	Color 255,255,255
	Line x1,y1,x2,y2
	
	; get length of line segment
	dx#=x2-x1 : dy#=y2-y1 : mag#=Sqr(dx*dx+dy*dy)
	
	
	u# = ( ((x3-x1)*(x2-x1)) + ((y3-y1)*(y2-y1)) ) / (mag*mag)
	
	xi# = x1+u*(x2-x1)
	yi# = y1+u*(y2-y1)

	; get nearest end if closest point outside segment
	If u<0 Then 
		cx# = x1 : cy#=y1
	ElseIf u>1 Then
		cx# = x2 : cy#=y2
	Else ; or closest point on line
		cx# = xi : cy#=yi
	EndIf

	Color 255,0,0
	Rect x3-1,y3-1,2,2
	Line x3,y3,cx,cy
	
	dx#=x3-cx : dy#=y3-cy
	distance#=Sqr(dx*dx+dy*dy)
	
	Text 0,0,"Intersection at "+cx+", "+cy
	If u<0 Or u>1 Then 
		Text 0,12,"Closest point outside line segment"
	Else
		Text 0,12,"Scalar position along line = "+u
	EndIf
	Text 0,24,"Distance to line segment "+distance
	Flip
Until KeyDown(1)

In fact I think you can dispense with the first one as well, since you are dividing by mag squared to get the scalar. Hmmm maybe I am overlooking something here, but try this
dx#=x2-x1 : dy#=y2-y1 : mag#=dx*dx+dy*dy
u# = ( (x3-x1)*dx + (y3-y1)*dy ) / mag
xi# = x1 + u * dx
yi# = y1 + u * dy
instead of
dx#=x2-x1 : dy#=y2-y1 : mag#=Sqr(dx*dx+dy*dy)
u# = ( ((x3-x1)*(x2-x1)) + ((y3-y1)*(y2-y1)) ) / (mag*mag)
xi# = x1+u*(x2-x1)
yi# = y1+u*(y2-y1)

so

Graphics 640,480,0,2
SetBuffer BackBuffer()
HidePointer

Type Lineseg
Field x1,y1,x2,y2
End Type

numsegs=500

range=100

For i=1 To numsegs
	l.lineseg = New lineseg
	l\x1=320 : l\y1=240
	l\x2=Rand(0,640) : l\y2=Rand(0,480)
Next

Repeat
	Cls
	
	px=MouseX()
	py=MouseY()
	
	LockBuffer BackBuffer()
		
	For l.lineseg = Each lineseg
	
		If LineInRange(px,py,l\x1,l\y1,l\x2,l\y2,range) Then
			Color 255,255,0
		Else
			Color 255,255,255
		EndIf

	Line l\x1,l\y1,l\x2,l\y2

	Next
	
	UnlockBuffer BackBuffer()
	
	Color 255,0,0
	Plot px,py : Oval px-range,py-range,range*2,range*2,False
	
	Flip
	
Until KeyDown(1)


Function LineInRange(px#,py#,x1#,y1#,x2#,y2#,dist#)
	Local dx#,dy#,mag#,u#,cx#,cy#

	dx = x2 - x1 : dy = y2 - y1 : mag =dx*dx + dy*dy
	u = ( ((px-x1)*dx) + ((py-y1)*dy) ) / mag
	; get nearest end if closest point outside segment
	If u<0 Then 
		cx = x1 : cy = y1
	ElseIf u>1 Then
		cx = x2 : cy = y2
	Else ; or closest point on line
		cx = x1 + u * dx : cy = y1 + u * dy
	EndIf
	dx = px - cx : dy = py - cy
	If (dx*dx+dy*dy) <= (dist*dist) Then Return True Else Return False
End Function

sswift

(Posted 2003) [#4]

I'd swear I posted a function to do this in the code archives somewhere... Hm...

Miracle

(Posted 2003) [#5]

I thought you had too, sswift. I swear I saw it or something like it at one point.

Thank you, David, that's exactly what I needed. I've also bookmarked that code site so's not to have to bother you guys too much again. :)