Largest circle that will fit into a corner

Share your advanced PureBasic knowledge/code with the community.
Seymour Clufley
Addict
Addict
Posts: 1233
Joined: Wed Feb 28, 2007 9:13 am
Location: London

Largest circle that will fit into a corner

Post by Seymour Clufley »

This code uses the incircle concept which finds the largest circle that will fit inside a triangle. Two functions are built on top of that:

CircleInCornerByRadius()
Distance from corner is irrelevant. The circle is computed to have the specified radius.

CircleInCornerByDistance()
Circle radius is irrelevant. The circle is computed to have the specified distance between its edge and the corner.

Each function takes three coordinates (*p1, *p2, *p3) to define the corner at *p2, as well as either the required distance or required radius. The functions could easily be augmented to take, instead of three coordinates, the position and angle of the corner - but I don't need that so I've written them this way.

Demo code below. Press SPACE to cycle through, ESCAPE to quit, and R (radius of 100, distance variable) and D (distance of 100, radius variable) to switch between the two functions.

Code: Select all

;- GENERIC FUNCTIONS

Procedure.d Difference(a.d,b.d)
  
  If a=b
      ProcedureReturn 0
  EndIf
  If a>b
  	ProcedureReturn a-b
  EndIf
  ProcedureReturn b-a
  
EndProcedure




;- GEOMETRY FUNCTIONS

Structure PointD
  x.d
  y.d
EndStructure

Procedure.d DistanceBetweenTwoPoints(*a.PointD,*b.PointD)
  xdif.d = Difference(*a\x,*b\x)
  ydif.d = Difference(*a\y,*b\y)
  ProcedureReturn Sqr((xdif*xdif)+(ydif*ydif))
EndProcedure


Procedure.d DegreeAngleBetweenTwoPoints(*o.PointD,*b.PointD)
  calcAngle.d = Degree(ATan2(*b\x-*o\x,*b\y-*o\y))
  If calcAngle<0
    calcAngle = 360-Abs(calcAngle)
  EndIf
  ProcedureReturn calcAngle
EndProcedure


Procedure.b RadianCoordsFromPoint(*base.PointD,radia.d,distance.d,*c.PointD)
  *c\x = (Cos(radia)*distance)+*base\x
  *c\y = (Sin(radia)*distance)+*base\y
EndProcedure

Procedure.b DegreeCoordsFromPoint(*base.PointD,degrees.d,distance.d,*c.PointD)
  RadianCoordsFromPoint(*base,Radian(degrees),distance,*c)
EndProcedure


Macro CopyPoint(cpp1,cpp2)
  cpp2\x=cpp1\x
  cpp2\y=cpp1\y
EndMacro


Procedure.b MidPoint(*pnt1.PointD,*pnt2.PointD,*mp.PointD)
  deg.d = DegreeAngleBetweenTwoPoints(*pnt1,*pnt2)
  dist.d = DistanceBetweenTwoPoints(*pnt1,*pnt2)
  DegreeCoordsFromPoint(*pnt1,deg,dist/2,*mp)
EndProcedure




;- VECTOR DRAWING FUNCTIONS

Procedure.b VectorBox(x.d,y.d,w.d,h.d,clr.i)
  ResetPath()
  AddPathBox(x,y,w,h)
  ClosePath()
  VectorSourceColor(clr)
  FillPath()
EndProcedure

Procedure.b VectorCircleOutline(cx.d,cy.d,r.d,clr.i,girth.i=2)
  ResetPath()
  AddPathCircle(cx,cy,r)
  VectorSourceColor(clr)
  StrokePath(girth)
EndProcedure




;- SPECIAL FUNCTIONS

Structure CircleD
  r.d
  c.PointD
EndStructure


Procedure.b TriangleIncircle(*p1.PointD,*p2.PointD,*p3.PointD,*c.CircleD)
  
  dist_a.d = DistanceBetweenTwoPoints(*p2,*p3)
  dist_b.d = DistanceBetweenTwoPoints(*p3,*p1)
  dist_c.d = DistanceBetweenTwoPoints(*p1,*p2)
  s.d = dist_a+dist_b+dist_c ; perimeter
  
  *c\c\x = ((dist_a**p1\x) + (dist_b**p2\x) + (dist_c**p3\x)) / s
  *c\c\y = ((dist_a**p1\y) + (dist_b**p2\y) + (dist_c**p3\y)) / s
  
  s/2 ; half-perimeter
  area.d = Sqr(s*(s-dist_a)*(s-dist_b)*(s-dist_c))
  *c\r = area / s
  
EndProcedure


Procedure.b CircleInCornerByDistance(*p1.PointD,*p2.PointD,*p3.PointD,corner_gap.d,*k.CircleD)
  
  TriangleIncircle(*p1,*p2,*p3,*k)
  gap.d = DistanceBetweenTwoPoints(*k\c,*p2) - *k\r
  
  If Difference(gap,corner_gap)>0.1
    CopyPoint(*p1,cp1.PointD)
    CopyPoint(*p2,cp.PointD)
    CopyPoint(*p3,cp2.PointD)
    deg1.d = DegreeAngleBetweenTwoPoints(@cp,@cp1)
    deg2.d = DegreeAngleBetweenTwoPoints(@cp,@cp2)
    dist1.d = DistanceBetweenTwoPoints(@cp,@cp1)
    dist2.d = DistanceBetweenTwoPoints(@cp,@cp2)
    If gap<corner_gap
      ; move circle farther from corner
      Repeat
        dist1+0.1
        dist2+0.1
        DegreeCoordsFromPoint(@cp,deg1,dist1,@cp1)
        DegreeCoordsFromPoint(@cp,deg2,dist2,@cp2)
        TriangleIncircle(@cp1,@cp,@cp2,*k)
        gap.d = DistanceBetweenTwoPoints(*k\c,@cp) - *k\r
      Until Difference(gap,corner_gap)<0.1
    Else
      ; move circle closer to corner
      Repeat
        dist1-0.1
        dist2-0.1
        DegreeCoordsFromPoint(@cp,deg1,dist1,@cp1)
        DegreeCoordsFromPoint(@cp,deg2,dist2,@cp2)
        TriangleIncircle(@cp1,@cp,@cp2,*k)
        gap.d = DistanceBetweenTwoPoints(*k\c,@cp) - *k\r
      Until Difference(gap,corner_gap)<0.1
    EndIf
  EndIf
  
EndProcedure


Procedure.d CircleInCornerByRadius(*p1.PointD,*p2.PointD,*p3.PointD,r.d,*k.CircleD)
  
  TriangleIncircle(*p1,*p2,*p3,*k)
  
  If Difference(*k\r,r)>0.1
    CopyPoint(*p1,cp1.PointD)
    CopyPoint(*p2,cp.PointD)
    CopyPoint(*p3,cp2.PointD)
    deg1.d = DegreeAngleBetweenTwoPoints(@cp,@cp1)
    deg2.d = DegreeAngleBetweenTwoPoints(@cp,@cp2)
    dist1.d = DistanceBetweenTwoPoints(@cp,@cp1)
    dist2.d = DistanceBetweenTwoPoints(@cp,@cp2)
    If *k\r<r
      ; move circle farther from corner
      Repeat
        dist1+0.1
        dist2+0.1
        DegreeCoordsFromPoint(@cp,deg1,dist1,@cp1)
        DegreeCoordsFromPoint(@cp,deg2,dist2,@cp2)
        TriangleIncircle(@cp1,@cp,@cp2,*k)
      Until Difference(*k\r,r)<0.1
    Else
      ; move circle closer to corner
      Repeat
        dist1-0.1
        dist2-0.1
        DegreeCoordsFromPoint(@cp,deg1,dist1,@cp1)
        DegreeCoordsFromPoint(@cp,deg2,dist2,@cp2)
        TriangleIncircle(@cp1,@cp,@cp2,*k)
      Until Difference(*k\r,r)<0.1
    EndIf
  EndIf
  
  ProcedureReturn Difference(*k\r,r) ; returns gap between corner and the circle's edge, in case this info is useful
  
EndProcedure







iw = 1920
ih = 1000
win = OpenWindow(#PB_Any,0,0,iw,ih,"",#PB_Window_ScreenCentered|#PB_Window_BorderLess)
space=5 : AddKeyboardShortcut(win,#PB_Shortcut_Space,space)
esc=6 : AddKeyboardShortcut(win,#PB_Shortcut_Escape,esc)
key_r=7 : AddKeyboardShortcut(win,#PB_Shortcut_R,key_r)
key_d=8 : AddKeyboardShortcut(win,#PB_Shortcut_D,key_d)
cnv = CanvasGadget(#PB_Any,0,0,iw,ih)
cnt.PointD : cnt\x=iw/2 : cnt\y=ih/2




Repeat
  ; randomise the corner
  Dim pnt.PointD(3)
  offset.d = Random(360)
  For p = 1 To 3
    dist = Random(ih/2,100)
    DegreeCoordsFromPoint(@cnt,offset+(360 / 3 * p),dist,@pnt(p))
  Next p
 
  ; compute
  If mode=0
    CircleInCornerByRadius(@pnt(1),@pnt(2),@pnt(3),100,@k.CircleD)
  Else
    CircleInCornerByDistance(@pnt(1),@pnt(2),@pnt(3),100,@k.CircleD)
  EndIf
 
  StartVectorDrawing(CanvasVectorOutput(cnv))
  ; clear the screen
  VectorBox(0,0,VectorOutputWidth(),VectorOutputHeight(),RGBA(50,50,50,255))
  ; draw the "corner"
  Midpoint(@pnt(1),@pnt(3),@mp.PointD)
  VectorSourceCircularGradient(pnt(2)\x,pnt(2)\y,DistanceBetweenTwoPoints(@pnt(2),@mp))
  VectorSourceGradientColor(RGBA(255,255,255,255),0)
  VectorSourceGradientColor(RGBA(255,255,255,64),0.5)
  VectorSourceGradientColor(RGBA(255,255,255,0),1)
  MovePathCursor(pnt(1)\x,pnt(1)\y)
  AddPathLine(pnt(2)\x,pnt(2)\y)
  AddPathLine(pnt(3)\x,pnt(3)\y)
  ClosePath()
  FillPath()
  ; draw the circle
  VectorCircleOutline(k\c\x,k\c\y,k\r,RGBA(Random(128),Random(128),Random(128),255))
  StopVectorDrawing()
 
  Repeat : Until WaitWindowEvent(5)=#PB_Event_Menu
  Select EventMenu()
    Case key_r
      mode = 0
    Case key_d
      mode = 1
    Case esc
      Break
  EndSelect
ForEver
JACK WEBB: "Coding in C is like sculpting a statue using only sandpaper. You can do it, but the result wouldn't be any better. So why bother? Just use the right tools and get the job done."