maths help : 2D line intersects 2D circle

Community Forums/General Help/maths help : 2D line intersects 2D circle

RemiD

(Posted 2016) [#1]

Hello,

I have found a function by col here : http://www.blitzbasic.com/Community/posts.php?topic=73517 (post #9)

and i have tried to convert it to Blitz3d, and also removed the things that i don't need (i only need to know if a 2D line intersects with a 2d circle), and it works most of the time but not always, see :
;removed useless code (with errors)

The base formula is good because it seems to return if an infinite line intersects with a circle, which is good but not exactly what i want. I want to know if a limited line (between 2 points) intersects with a circle.

Any suggestions to improve the procedure/function appreciated.

Thanks,

RemiD

(Posted 2016) [#2]

Ok i have added 2 checks :
if each point of the line is near enough the center of the circle (distance less than length of line + radius of circle)
;removed useless code

and again after 100 tries, it works in most cases but not in all cases, see :

(in this case, this should return false (does not intersect))

Trinosis

(Posted 2016) [#3]

Hi RemiD.

I have a bunch of intersection video's and source code i think would be of use to you.

All return true or false for intersection and the intersection point.

Line To Line Intersection.

Circle To Line Intersection.

Ellipse To Line Intersection.

The video's demonstrate their use for sliding collision.

And you can download the demo's and source code here in my Dropbox.
( You don't need to sign up to Dropbox in order to download the files, just skip the sign up process if asked )

https://www.dropbox.com/sh/7yo7113x0jsll4q/AAA_noRRvfPpSgF-cibv3toya?dl=0

RemiD

(Posted 2016) [#4]

@Trinosis>>Thanks, i will take a look. :)

RemiD

(Posted 2016) [#5]

I am not looking for a circle to line collisions system but rather for a line intersects circle formula, not sure if i can use this...

RemiD

(Posted 2016) [#6]

I am trying to understand some math formulas on different websites, and i have to admit that trying to understand egyptians symbols is easier than this :-O

Why do the math formulas are written in such a weird way ? They could be written like with programming syntax it would be easier to grasp...

RemiD

(Posted 2016) [#7]

OoOh i think i found a way !

col	(Posted 2016) [#8]

Well done, you're nearly there but you missed a final step.
As the result of the equation is a parametric then you need to check if the intersection points are between 0.0 and 1.0.

Ox, Oy are the origin of the line to check for intersection
Dx, Dy is a vector from Ox, Oy to end of the line to check for intersection
Cx, Cy are the centre coords of the circle
Radius is... ;-)

Function IntersectLineCircle(Ox:Float,Oy:Float,Dx:Float,Dy:Float,Cx:Float, Cy:Float,Radius:Float)
	Local DiffX:Float = Ox - Cx
	Local DiffY:Float = Oy - Cy
	
	Local A:Float = (Dx * Dx) + (Dy * Dy)
	Local B:Float = (DiffX * Dx) + (DiffY * Dy)
	Local Coeff# = (DiffX * DiffX) + (DiffY * DiffY) - (Radius*Radius)
	
	Local Intersecting# = B * B - A * Coeff
	If Intersecting < 0.0 Return False
	
	Local sqrIntersecting = Sqr(Intersecting)
	Local InvA# = 1.0 / A
	Local I0:Float = (-B - sqrIntersecting ) * InvA
	Local I1:Float = (-B + sqrIntersecting ) * InvA
	
	If I0 > 0.0 And I0 < 1.0 Return True
	If I1 > 0.0 And I1 < 1.0 Return True

	Return False
EndFunction

RemiD

(Posted 2016) [#9]

@Col>>thanks !

Your function seems to work correctly for the case that the infinite line would intersect with the circle but the limited line (between 2 points) would not.

However, now, if the 2 points of the line are inside the circle, the function returns false (as if the line does not intersect with the circle)

;2DLineIntersects2DCircle
Graphics 640,480,32,2

SeedRnd(MilliSecs())

;circle properties
CRadius% = Rand(30,90)
CX% = Rand(0+CRadius,GraphicsWidth()-1-CRadius) : CY% = Rand(0+CRadius,GraphicsHeight()-1-CRadius)

;line properties
LAX% = Rand(CX-CRadius,CX+CRadius) : LAY% = Rand(CY-CRadius,CY+CRadius)
LBX% = Rand(CX-CRadius,CX+CRadius) : LBY% = Rand(CY-CRadius,CY+CRadius)

While Not KeyHit(1)
	
 If( KeyHit(57)=1 )
  ;line properties
  LAX% = Rand(0,GraphicsWidth()-1) : LAY% = Rand(0,GraphicsHeight()-1)
  LBX% = Rand(0,GraphicsWidth()-1) : LBY% = Rand(0,GraphicsHeight()-1)
  ;circle properties
  CRadius% = Rand(30,90)
  CX% = Rand(0+CRadius,GraphicsWidth()-1-CRadius) : CY% = Rand(0+CRadius,GraphicsHeight()-1-CRadius)
 EndIf

 MilliStart% = MilliSecs()
 For n% = 1 To 1000 Step 1
  Result% = LineIntersectsCircle(LAX,LAY,LBX,LBY,CX,CY,CRadius)
 Next
 LineIntersectsCircleMilliTime% = MilliSecs() - MilliStart

 SetBuffer(BackBuffer())
	
 ClsColor(000,000,000)
 Cls()
 
 ;draw line
 Color(255,255,255)
 Line(LAX,LAY,LBX,LBY)

 ;draw circle
 Color(255,255,255)
 Oval(CX-CRadius,CY-CRadius,CRadius*2,CRadius*2,False)

 Color(255,255,255)
 Text(0,0,"LineIntersectsCircleMilliTime = "+Float(LineIntersectsCircleMilliTime)/1000)
 If( Result = True )	
  Color(255,000,000)
  Text(GraphicsWidth()/2-StringWidth("Intersects")/2,GraphicsHeight()/2,"Intersects")
 Else If( Result = False )	
  Color(000,255,000)
  Text(GraphicsWidth()/2-StringWidth("Does not Intersect")/2,GraphicsHeight()/2,"Does not Intersect")	
 EndIf
	
 Flip(1)
	
Wend

End()

Function LineIntersectsCircle%(Ax#,Ay#,Bx#,By#,Cx#,Cy#,CRadius#) ;by Col

 Vx# = Bx - Ax
 Vy# = By - Ay

 DiffX# = Ax - Cx
 DiffY# = Ay - Cy
	
 A# = (Vx * Vx) + (Vy * Vy)
 B# = (DiffX * Vx) + (DiffY * Vy)

 Coeff# = (DiffX * DiffX) + (DiffY * DiffY) - (CRadius*CRadius)
	
 Intersecting# = B * B - A * Coeff

 If( Intersecting < 0.0 )
  Return False
 EndIf	

 sqrIntersecting# = Sqr(Intersecting)
 InvA# = 1.0 / A
 I0# = (-B - sqrIntersecting ) * InvA
 I1# = (-B + sqrIntersecting ) * InvA
	
 If( I0 > 0.0 And I0 < 1.0 )
  Return True
 EndIf

 If( I1 > 0.0 And I1 < 1.0 )
  Return True
 EndIf

 Return False

End Function

see :

This is not a problem for what i want, but just to be aware of it...

(a simple improvement would be to check if the 2 points of the line are near enough the circle center (at a distance less than the radius), if yes, the line is inside the circle and thus intersects with the circle)

Thanks for sharing !

col	(Posted 2016) [#10]

Your function seems to work correctly for the case that the infinite line would intersect with the circle but the limited line (between 2 points) would not.

Ooops, sorry about that.

Function IntersectLineCircle(Ox:Float,Oy:Float,Dx:Float,Dy:Float,Cx:Float, Cy:Float,Radius#)
	Local DiffX:Float = Ox - Cx
	Local DiffY:Float = Oy - Cy
	
	Local A:Float = (Dx * Dx) + (Dy * Dy)
	Local B:Float = (DiffX * Dx) + (DiffY * Dy)
	Local Coeff# = (DiffX * DiffX) + (DiffY * DiffY) - (Radius*Radius)
	
	Local Intersecting# = B * B - A * Coeff
	If Intersecting < 0.0 Return False
	
	Local sqrIntersecting = Sqr(Intersecting)
	Local InvA# = 1.0 / A
	Local I0:Float = (-B - sqrIntersecting ) * InvA
	Local I1:Float = (-B + sqrIntersecting ) * InvA

	If (I0 > 0.0 And I0 < 1.0) Return True
	If (I1 > 0.0 And I1 < 1.0) Return True
	If (I0 =< 0.0 And I1 >= 1.0) Return True
EndFunction

RemiD

(Posted 2016) [#11]

Ok, this seems to work well in all cases now.

(you have to add :

If(I0 =< 0.0 And I1 >= 1.0) 
 Return True
endif

at the end of the function in post #9 )

Thanks !

Kryzon

(Posted 2016) [#12]

I'm trying to understand the code in that routine Col posted. It seems to be using the quadratic formula.

But this part here:

Local Intersecting# = B * B - A * Coeff

...is the "discriminant", or (b^2 - 4.a.c) from the quadratic formula
I don't understand why it removed the 4. It's probably an optimisation given these line-circle circumstances.

This answer in StackExchange preserves the 4 (and gives some insight into why the problem can be solved this way):
http://gamedev.stackexchange.com/a/18339