Oriented bounding box

[Seymour Clufley]

This procedure finds the smallest bounding box for a given set of points, at a given angle. You can specify any angle.

Demo code (press SPACE to cycle through and ESCAPE to quit):

Code: Select all

Macro DefeatThis(a,b)
  If a>b
      a=b
  EndIf
EndMacro
Macro BeatThis(a,b)
  If b>a
      a=b
  EndIf
EndMacro




Structure PointD
  x.d
  y.d
EndStructure

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




Procedure.b ComputePolygonCentroid(points.i,Array vertex.PointD(1),*centroid.PointD)
  signedArea.d = 0
  x0 = 0; Current vertex X
  y0 = 0; Current vertex Y
  x1 = 0; Next vertex X
  y1 = 0; Next vertex Y
  a = 0 ;  Partial signed area
  
  ; for all points except last
  For i = 1 To points-1
    x0 = vertex(i)\x
    y0 = vertex(i)\y
    x1 = vertex(i+1)\x
    y1 = vertex(i+1)\y
    a = x0*y1 - x1*y0
    signedArea + a
    *centroid\x + (x0 + x1)*a
    *centroid\y + (y0 + y1)*a
  Next
  
  ; do last vertex
  x0 = vertex(points)\x
  y0 = vertex(points)\y
  x1 = vertex(1)\x
  y1 = vertex(1)\y
  a = x0*y1 - x1*y0
  signedArea + a
  *centroid\x + (x0 + x1)*a
  *centroid\y + (y0 + y1)*a
  
  signedArea * 0.5
  *centroid\x / (6*signedArea)
  *centroid\y / (6*signedArea)
EndProcedure




Procedure.b DegreeRotatePointAroundPoint(*p.PointD,*rc.PointD,degrees.d,*np.PointD)
  radia.d = Radian(degrees)
  *np\x = *rc\x + ( Cos(radia) * (*p\x - *rc\x) - Sin(radia) * (*p\y - *rc\y) )
  *np\y = *rc\y + ( Sin(radia) * (*p\x - *rc\x) + Cos(radia) * (*p\y - *rc\y) )
EndProcedure




Procedure.b ComputeBoundingBoxAtAngle(pnts.i,Array pnt.PointD(1),deg.d,Array perimrect.PointD(1))
  
  ComputePolygonCentroid(pnts,pnt(),@cd.PointD)
  
  xmin.d = 99999999
  ymin.d = 99999999
  xmax.d = -99999999
  ymax.d = -99999999
  ; rotate all points...
  For p = 1 To pnts
    DegreeRotatePointAroundPoint(@pnt(p),@cd,-deg,@np.PointD)
    DefeatThis(xmin,np\x)
    DefeatThis(ymin,np\y)
    BeatThis(xmax,np\x)
    BeatThis(ymax,np\y)
  Next p
  
  ReDim perimrect(4)
  perimrect(1)\x=xmin : perimrect(1)\y=ymin
  perimrect(2)\x=xmax :	perimrect(2)\y=ymin
  perimrect(3)\x=xmax :	perimrect(3)\y=ymax
  perimrect(4)\x=xmin :	perimrect(4)\y=ymax
  For r = 1 To 4
    DegreeRotatePointAroundPoint(@perimrect(r),@cd,deg,@np.PointD)
    CopyPoint(np,perimrect(r))
  Next
  
  ProcedureReturn #True
  
EndProcedure




iw = 1600
ih = 800
win = OpenWindow(#PB_Any,0,0,iw,ih,"Angled Bounding Box",#PB_Window_ScreenCentered)
cnv = CanvasGadget(#PB_Any,0,0,iw,ih)
space=5
AddKeyboardShortcut(win,#PB_Shortcut_Space,space)
esc=6
AddKeyboardShortcut(win,#PB_Shortcut_Escape,esc)


Repeat
  pnts = Random(20,5)
  Dim pnt.PointD(pnts)
  For p = 1 To pnts
    pnt(p)\x = Random(iw*0.7,iw*0.3)
    pnt(p)\y = Random(ih*0.8,ih*0.2)
  Next p
  
  Dim rotpnt.PointD(4)
  deg.d = 45
  ComputeBoundingBoxAtAngle(pnts,pnt(),deg,rotpnt())
  rpnts=4
  
  
  StartDrawing(CanvasOutput(cnv))
  Box(0,0,OutputWidth(),OutputHeight(),#Black)
  
  For p = 1 To pnts
    Circle(pnt(p)\x,pnt(p)\y,5,#Red)
  Next p
  
  For p = 1 To rpnts
    p2=p+1 : If p=rpnts : p2=1 : EndIf
    LineXY(rotpnt(p)\x,rotpnt(p)\y,rotpnt(p2)\x,rotpnt(p2)\y,#Green)
  Next p
  
  StopDrawing()
  
  Repeat : Until WaitWindowEvent(5)=#PB_Event_Menu
  If EventMenu()=esc : Break : EndIf
ForEver

[Caronte3D]

Nice! Thanks!