Line to circle collisions

Blitz3D Forums/Blitz3D Programming/Line to circle collisions

Braincell

(Posted 2005) [#1]

I needed a nice and easy circle to line collision function so i found one in the code archives. It required a type and 3 separate functions so i decided to simplify it for my needs. In case anyone is looking for something like this, here it is.

The original code is by Jeppe Nielsen.

It can also return the coordinates of the point of collision (uncomment the two lines and make the variables global).

Here's the function with very basic implementation:

;From original 2D Collision Example By Jeppe Nielsen 2004
;Modified by Lenn (August 2005)

Graphics 800,600,0,2

linex1#= 7
liney1# = 20
linex2#= 371
liney2# = 350

circlex#= 300
circley# = 200
circler# = 70

Line linex1, liney1, linex2, liney2
Oval circlex-circler, circley-circler, circler*2, circler*2

If LineToCircle( linex1, liney1, linex2, liney2, circlex, circley, circler) Then
Text 10,100, "Collided."
Else
Text 10,100, "Not collided."
End If 



WaitKey



Function LineToCircle( lx1#, ly1#, lx2#, ly2#, cx#, cy#, r#)

dx# = lx2 - lx1
dy# = ly2 - ly1
ld# = Sqr((dx*dx) + (dy*dy))
lux# = dx / ld
luy# = dy / ld
lnx# = luy
lny# = -lux
dx1# = cx - (lx1 - lux*r)
dy1# = cy - (ly1 - luy*r)
d# = Sqr((dx1*dx1) + (dy1*dy1))
dx1 = dx1 / d
dy1 = dy1/ d
dx2# = cx - (lx2 + lux * r)
dy2# = cy - (ly2 + luy*r)
d = Sqr((dx2*dx2) + (dy2*dy2))
dx2 = dx2  / d
dy2 = dy2 / d
dot1# = (dx1 * lux) + (dy1 * luy)
dot2# = (dx2 * lux) + (dy2 * luy)
px#=lx1-cx
py#=ly1-cy
distsq# = Abs((dx * py - px * dy)  / ld )

;You can get point of collision using these two variables (make them global)
;LineColX# = cx - lnx * sqr(distsq) 
;LineColY# = cy - lny * sqr(distsq)


Return (( dot1>=0 And dot2<=0) Or (dot1<=0 And dot2>=0)) And (distsq <= r)


End Function

By the way, i've looked into this myself and i couldnt find a more clever and quicker mathematical way of doing this (at least in blitz) so this is probably as fast as it can get. Oh and you cant exactly remove Sqr() because the dot needs negative values as well and squaring values will always make them positive as you know.

jfk EO-11110

(Posted 2005) [#2]

Thanks for sharing. i like simplifications :)

sswift

(Posted 2005) [#3]

"so this is probably as fast as it can get"

Famous last words. :-)

Function LineIntersectCircle(Line_X1#, Line_Y1#, Line_X2#, Line_Y2#, Circle_X#, Circle_Y#, Circle_Radius#)

	Local U#
	Local Px#, Py#
	Local Distance#

	; Calculate U# coordinate of nearest point on line to center of circle.
		U# = (Circle_X# - Line_X1#) * (Line_X2# - Line_X1#) + (Circle_Y# - Line_Y1#) * (Line_Y2# - Line_Y1#) 
		U# = U# / ((Line_X2# - Line_X1#)*(Line_X2# - Line_X1#) + (Line_Y2# - Line_Y1#)*(Line_Y2# - Line_Y1#)) 

	; Calculate coordinates of said point.
		Px# = Line_X1# + (U# * (Line_X2# - Line_X1#))
		Py# = Line_Y1# + (U# * (Line_Y2# - Line_Y1#))
		
	; Calculate the squared distance from the point on the line to the center of the circle.
		Distance# = (Px#-Circle_X#)*(Px#-Circle_X#) + (Py#-Circle_Y#)*(Py#-Circle_Y#)
		
	; If the closest point on the line to the center of the circle is nearer to the center of the circle than the circle's radius, then the line and circle have collided.
		If Distance# < (Circle_Radius#*Circle_Radius#)
			Return True
		Else
			Return False
		EndIf
		
End Function

Luke.H

(Posted 2005) [#4]

U# = U# / (Line_X2# - Line_X1#)*(Line_X2# - Line_X1#) + (Line_Y2# - Line_Y1#)*(Line_Y2# - Line_Y1#)

should be

U# = U# / ((Line_X2# - Line_X1#)*(Line_X2# - Line_X1#) + (Line_Y2# - Line_Y1#)*(Line_Y2# - Line_Y1#))

sswift

(Posted 2005) [#5]

Luke:
You're right, but in my defense, I coded that on the fly in reply to the thread without testing it... So if that is the only bug, then I can feel good about it. :-)

Function corrected!

MusicianKool

(Posted 2011) [#6]

I know it's old but I noticed something. Swift's code is an infinite line collision, and braincell's code is a line segment collision which is much more useful.