2D Ray/Line Circle intersection

[D.J.Peters]

I used often Ray Sphere intersection in 3D (FBRaytracer etc.)
here are one solution in 2D

it returns 1 or 2 points of intersection (if any)

Joshy

Code: Select all

type VECTOR2D
  as single x,y
end type
const epsilon = 0.0001
function RayCircleIntersection(RayOrigin as Vector2D, _
                               RayDir    as Vector2D, _
                               CirclePos as Vector2D, _
                               Radius    as single, _
                               HPoints() as Vector2D) as integer
  dim as VECTOR2D diff
  dim as single r2,dot,dir2,d,ds,l

  diff.x = RayOrigin.x - CirclePos.x
  diff.y = RayOrigin.y - CirclePos.y
  r2 = Radius * Radius
  ' ray origin inside circle?
  If (diff.x * diff.x + diff.y * diff.y) <= r2 then
    ' normalize direction
    l=RayDir.x*RayDir.x + RayDir.y*RayDir.y 
    if l<>0.0 then
      l=1.0/sqr(l)
      RayDir.x*=l
      RayDir.y*=l
    end if
    HPoints(0).x = CirclePos.x+Radius*RayDir.x
    HPoints(0).y = CirclePos.y+Radius*RayDir.y
    Return 1
  EndIf

  dot  = RayDir.x * diff.x + RayDir.y * diff.y
  dir2 = RayDir.x * RayDir.x    + RayDir.y * RayDir.y
  d = dot * dot - Dir2 * (diff.x * diff.x + diff.y * diff.y - R2)
  If (d < 0.0) then
    return 0
  ElseIf d < epsilon then
    ' one point of intersection
    l = -dot / Dir2
    If (l < 0.0) Or (l > 1.0) then
      Return 0
    Else
      HPoints(0).x = RayOrigin.x + l * RayDir.x
      HPoints(0).y = RayOrigin.y + l * RayDir.y
      Return 1
    EndIf
  Else
    ' two points of intersection
    ds=sqr(d)
    ' first hit point (nearest) 
    l  = (-dot - ds) / Dir2
    dim as integer ret=0
    If (l >=0.0) and (l <= 1.0) then
      HPoints(ret).x = RayOrigin.x + l * RayDir.x
      HPoints(ret).y = RayOrigin.y + l * RayDir.y
      ret+=1
    end if
    ' second hit point 
    l = (-dot + ds) / Dir2
    If (l >=0.0) and (l <= 1.0) then
      HPoints(ret).x = RayOrigin.x + l * RayDir.x
      HPoints(ret).y = RayOrigin.y + l * RayDir.y
      ret+=1
    end if
    return ret
  EndIf
End function

const scr_w=640
const scr_h=480
screenres scr_w,scr_h

dim as VECTOR2d RayOrigin,RayDir,SphereCenter,HitPoints(1)
dim as single r
dim as integer nHits
while inkey=""
  with RayOrigin   :.x=rnd*scr_w:.y=rnd*scr_h:end with
  with RayDir      :.x=rnd*scr_w- RayOrigin.x:.y=rnd*scr_h - RayOrigin.y:end with
  with SphereCenter:.x=rnd*scr_w:.y=rnd*scr_h:end with
  R=20

  nHits = RayCircleIntersection(RayOrigin,RayDir,SphereCenter,R,HitPoints(0))
  if nHits>0 then
    cls
    line (RayOrigin.x,RayOrigin.y)-step(RayDir.x,RayDir.y),1
    circle (SphereCenter.x,SphereCenter.y),r,2
    for i as integer=0 to nHits-1
      circle (HitPoints(i).x,HitPoints(i).y),2,3+i
    next
    sleep 1000
  end if
  
wend

[dodicat]

Hi D.J.Peters
Here's a less mathematical method.

Code: Select all

'LUCKY STRIKE
Dim Shared As Integer xres,yres
Screen 19,32
Screeninfo xres,yres
Type circle2d
    As Double x,y ,rad
    As Uinteger colour
End Type
Type point2d
    As Double x,y
    As Uinteger colour
End Type
Type line2d
    As Double x1,y1,x2,y2
    As Uinteger colour
End Type
Declare Function r(first As Double, last As Double) As Double
Declare Sub intersect(_circle As circle2d,_line As line2d)
Declare Sub make_a_circle_and_line
Dim Shared As circle2d _circle
Dim Shared As line2d _line

'________________________________________
Do
    Randomize
    make_a_circle_and_line     'line through or near circle
    intersect _circle,_line
    Sleep 1000
    Cls
Loop Until Inkey=Chr(27)

'_____________________________________________

Function r(first As Double, last As Double) As Double
    Function = Rnd * (last - first) + first
End Function

Sub intersect(_circle As circle2d,_line As line2d)
    #macro incircle(cx,cy,radius,x,y)
    (cx-x)*(cx-x) +(cy-y)*(cy-y)<= radius*radius
    #endmacro
    Dim As point2d position
    Redim As point2d cross(0)
    Dim As Double dxl,dyl,temp,length,rad2=_circle.rad-1
    Dim As Integer flag
    length=Sqr((_line.x2-_line.x1)^2+(_line.y2-_line.y1)^2)
    dxl=(_line.x2-_line.x1)
    dyl=(_line.y2-_line.y1)
    temp=Sqr(dxl^2+dyl^2)
    dxl=dxl/temp
    dyl=dyl/temp
    For z As Double=0 To length
        position.x=_line.x1+z*dxl
        position.y=_line.y1+z*dyl
        If incircle(_circle.x,_circle.y,_circle.rad,position.x,position.y) Then
            If Not incircle(_circle.x,_circle.y,rad2,position.x,position.y) Then
                flag=flag+1
                Redim Preserve cross(flag)
                If flag=1 Then
                    cross(flag).colour=_circle.colour/2
                Else
                    cross(flag).colour=_circle.colour/3
                End If
                cross(flag).x=position.x
                cross(flag).y=position.y
                Circle(position.x,position.y),5,cross(flag).colour,,,,f
                z=z+length/100
            End If
        End If
    Next z
    if flag then
     Draw String (.1*xres,.2*yres+20*flag),"No.1 HIT ("+Str(Int(cross(1).x))+","+Str(Int(cross(1).y))+")",cross(1).colour
    If ubound(cross)<>1 Then Draw String (.1*xres,.2*yres+40*flag),"No.2 HIT ("+Str(Int(cross(Ubound(cross)).x))+","+Str(Int(cross(Ubound(cross)).y))+")",cross(Ubound(cross)).colour
    end if
End Sub

Sub make_a_circle_and_line
    Dim As point2d offcentre
    _circle.x=r(.1*xres,.9*xres):_circle.y=r(.1*yres,.9*yres):_circle.rad=r(.05,.15)*yres
    _circle.colour=Rgb(0,200,0)
    Dim As Double t1,t2
    Dim As Double dx,dy,dxl,dyl,temp
    dx=r(-50,50)
    dy=r(-50,50)
    offcentre.x=_circle.x+dx
    offcentre.y=_circle.y+dy
    _line.x1=r(.1*xres,.9*xres)
    _line.y1=r(.1*yres,.9*yres)
    dxl=(offcentre.x-_line.x1)
    dyl=(offcentre.y-_line.y1)
    temp=Sqr(dxl^2+dyl^2)
    dxl=dxl/temp
    dyl=dyl/temp
    _line.x2=_line.x1+xres*dxl
    _line.y2=_line.y1+yres*dyl
    _line.colour=Rgb(0,200,200)
    t1=Timer
    Circle(_circle.x,_circle.y),_circle.rad,_circle.colour
    Line (_line.x1,_line.y1)-(_line.x2,_line.y2),_line.colour
End Sub