Need some math
BlitzPlus Forums/BlitzPlus Programming/Need some math
| ||
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 ... |
| ||
Yes. |
| ||
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 |
| ||
I'd swear I posted a function to do this in the code archives somewhere... Hm... |
| ||
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. :) |