circle-packing


Information

Created with NetLogo version NetLogo 4.0.4
Running with NetLogoLite.jar version 404.


WHAT IS IT?


-------
This model attempts to create dense-packings of equal-sized circles in a circle.

HOW IT WORKS


--------
The desired number of circles are created at random locations, inside the containing circle, at a small size, with no overlaps.
The circles are increased in size by a small amount.
If no circles overlap, the size is increased again.
If any circles overlap, some simple physical dynamics are applied.
The program is designed to use hexagon-pack numbers--becuase it is easy to compare the density of a hexagon arangement of circles in a circle to the tweaked desnse-packed arrangement.

HEGXAGONAL NUMBERS


--------------
| K | R | 3 * K * (K + 1) + 1 |
| 0 | 1 | 1 |
| 1 | 6 | 7 |
| 2 | 12 | 19 |
| 3 | 18 | 37 |
| 4 | 24 | 61 |
| 5 | 30 | 91 |

HOW TO USE IT


---------
This section could explain how to use the model, including a description of each of the items in the interface tab.

THINGS TO NOTICE


------------
This section could give some ideas of things for the user to notice while running the model.

THINGS TO TRY


---------
This section could give some ideas of things for the user to try to do (move sliders, switches, etc.) with the model.

EXTENDING THE MODEL


---------------
This section could give some ideas of things to add or change in the procedures tab to make the model more complicated, detailed, accurate, etc.

NETLOGO FEATURES


------------
This section could point out any especially interesting or unusual features of NetLogo that the model makes use of, particularly in the Procedures tab. It might also point out places where workarounds were needed because of missing features.

RELATED MODELS


----------
This section could give the names of models in the NetLogo Models Library or elsewhere which are of related interest.

HEXAGONAL NUMBERS


-------------

k 1 2 3 4 5


per ring 1 (1 + 6 * 1) (1 + 6 * 2) (1 + 6 * 3) (1 + 6 * 4) (1 + 6 * 5)


total 1 (2 + 6 * 1) (3 + 6 * 3) (4 + 6 * 6) (5 + 6 * 10) (6 + 6 * 15)

CREDITS AND REFERENCES


------------------
Lubachevsky, D.B.; Graham, R.L. : "Dense Packings of 3k(k+1)+1 Equal Disks in a circle for k = 1, 2, 3, 4, and 5", February 24, 1995, AT&T Bell Laboratories.

Procedures

NetLogo Version: NetLogo 4.0.4

globals
[ container-diameter
  container-radius
  container-area
  escape-radius
  new-size
  new-radius
  overlap-radius
  overlap-count
  countdown
  ; circle-count
  pause?
  time-since-zero
  master-rad-inc
  master-jiggle
  rad-inc ;; radius increment
  jiggle ;; movement caused by collisions
  jiggle-timeout-inc
  jiggle-timeout ;; max ticks for jiggling before reducing jiggle/rad-inc
  last-zero
  this-zero
  next-zero
  hex-pack-area
  hex-pack-radius
  hex-pack-density
  collision-buffer
  collision-radius
  last-good-size
  ordered-circles
  history
  hist-len
  circ-color
]

breed [ circles circle ]
circles-own
[  moved?
   ;; circles that overlap this circle
   d
   overlaps
   vx vy
   xx yy
   overcount
   last-good-position
]
undirected-link-breed [ collisions collision ]
collisions-own
[ age ]

;;=========================================================================================
;;=========================================================================================
;; the breed for the mouse pointer
;; defined last so pointer is on top of all other shapes
breed [ pointers pointer ]
pointers-own
[ dragged 
  hovered 
  hover-radius^2
  click-time
  outside?
  in-click?
  mx my
]
;;=========================================================================================
;;=========================================================================================


to setup
   
   ca
   
   ;; create the circle that defines the arena
   set container-diameter min (list world-width world-height) * .8
   set container-radius  container-diameter / 2
   set container-area pi * container-radius ^ 2 
      create-turtles 1
   [ home
     set shape "circle-edge"
     set size container-diameter
     set color white
     stamp
     die
   ]
   
   reset-history
   set-default-shape circles "circle-edge"
   set circle-count 3 * k * (k + 1) + 1
   set master-rad-inc .01
   set rad-inc master-rad-inc
   set master-jiggle 1.55
   set jiggle master-jiggle
   set jiggle-timeout-inc circle-count * 2
   set jiggle-timeout jiggle-timeout-inc
   set collision-buffer 1e-5

   set last-zero 0
   set next-zero 1000
   
   ;; now create the circles
  
   setup-circles
   set ordered-circles sort circles
end
   
to setup-circles
   let hex-pack-size container-radius * 2 / (k * 2 + 1)
   set circ-color blue
   foreach (n-values (k + 1) [ ? ])
   [ let r ?
     create-ordered-circles (max (list (r * 6) 1))
     [ set size hex-pack-size
       ; set label hex who
       set color circ-color
       jump r * hex-pack-size
     ]
   ] 
   while [ any? circles with [ any? collision-set size ]]
   [ set hex-pack-size hex-pack-size * .999
     ask circles [ set size hex-pack-size ]
   ]
   ask min-one-of circles [ who ] [ set shape "circle" ]
   ask max-one-of circles [ who ] [ set shape "circle" ]
   set new-size hex-pack-size
   save-arrangement
   update-size 0
end

to go
   mouse:go
   ifelse pause? != true
   [
   set overlap-count 0
   
   ;; detect collisions, accumulate total collision "push"
   set collision-radius new-size ; + collision-buffer * 2
   let collision-fade-delay 1
   let ticks+collision-fade-delay ticks + collision-fade-delay

   ask circles
   [ set xx 0
     set yy 0
     if any? other circles with [ nearly-same self myself ]
     [ rt random-float 360 jump new-size * .5 
     ]
      ifelse who = max [ who ] of circles
      [ set overlaps no-turtles
        set overcount 0
      ]
      [ 
     
     
     set overlaps collision-set new-size
     
     
     set overcount 0
     ;; find collisions with other circles

     ifelse any? overlaps
     [
       set overcount count overlaps
       set xx xx + bounce * sum [ (xcor + (collision-radius) * sin (safe-towards myself) - [ xcor ] of myself)  ] of overlaps 
       set yy yy + bounce * sum [ (ycor + (collision-radius) * cos (safe-towards myself) - [ ycor ] of myself)  ] of overlaps 
       set color circ-color - 2
     ]
     [ set color circ-color
     ]
    ]
;  ]
   
   ;; collisions affect circles
 ; ask circles
  ;[  ;calculate new x, y coords after "push"
     let new-x xcor + xx
     let new-y ycor + yy
     
     ;; prevent escape from edge
     if sqrt (new-x * new-x + new-y * new-y) > escape-radius
     [ let head atan new-x new-y
       set new-x ( escape-radius - collision-buffer ) * sin head
       set new-y ( escape-radius - collision-buffer ) * cos head
       set xx new-x - xcor
       set yy new-y - ycor
     ]
     if who > 1 [ setxy new-x new-y  ]
     let move-dist sqrt (xx * xx + yy * yy)
     ifelse move-dist > 0
     [ set overlap-count overlap-count + 1
       set moved? true
     ]
     [ set moved? false
     ] 
     ;; create collision vis.
     if show-collisions?
     [ if show-collisions?
       [ create-collisions-with overlaps
         [ set thickness 0
           set color white
           set thickness .25
           ;set color scale-color red severe 0 .001
         ]
         ;; refresh age of all current collisions
         ask (link-set [collision-with myself ] of overlaps)
         [ set age ticks+collision-fade-delay
         ] 
       ]
     ]
   ]
;; kill any old collisions
   ifelse show-collisions?
   [
     ask collisions with [ age != ticks+collision-fade-delay ]
     [ ifelse age < ticks
       [ die ]
       [ ; set color scale-color gray  (age - ticks) 0 collision-fade-delay
       ]
     ]  
   ]
   
   [ if any? collisions
     [ ask collisions [ die ]
     ]
   ]
   set history lput overlap-count but-first history
   set-current-plot-pen "default"
   plot overlap-count
   set-current-plot-pen "mean"
   plot mean history
   
   ifelse overlap-count = 0
   [ 
       save-arrangement
       update-size rad-inc
       if clear-plot-at-zero? [  clear-plot ]
   ]
   [ set time-since-zero time-since-zero + 1
     ;if time-since-zero > jiggle-timeout-inc 
     ;[ set jiggle-timeout-inc jiggle-timeout-inc * 1.01
     ;  set jiggle jiggle * .75
     ;  let old-inc rad-inc
     ;  set rad-inc rad-inc * .75
     ;  update-size (- old-inc)
     ;  set time-since-zero 0
     ;  if rad-inc < .001
     ;  [ ask collisions [ die ]
     ;    ask circles [ set label "" ]
     ;    ask pointers [ die ]
     ;    display
     ;    stop stop
     ;  ]
     ;]

     
   ]
   tick
   ]
   [ display
   ]
   set pause? false
   if ticks > next-zero
   [ restore-arrangement
     ask circles [ set label "" ]
     ask pointers [ die ]
     update-size 0
     ;; SHOW HEX PACK RADIUS
     create-turtles 1
     [ home
       set shape "circle-edge"
       set size hex-pack-radius * 2
       set color YELLOW
       stamp
       die
     ]
     display
     stop stop
   ]
end

to-report collision-set [ coll-rad ]
   report other circles in-radius coll-rad
end    

to reset-history
   set hist-len 100
   set history n-values hist-len [ circle-count ]
end

to-report safe-towards [ agent ]
   ifelse [ xcor] of agent = xcor or [ ycor ] of agent = ycor
   [ report 0 ]
   [ report (1 - random-float 2 + towards agent )]
end
   
to save-arrangement
   ask circles
   [ set last-good-position (list xcor ycor)
   ]
   set last-good-size new-size
end

to restore-arrangement
   set new-size last-good-size
   ask circles
   [ setxy (first last-good-position)(last last-good-position)
     set size new-size
   ]
   ask collisions [ die ]
end
   

to update-size [ #new-size ]
   set new-size new-size + #new-size
   ask circles
   [ ;; inflate the turtle
     set size new-size
     set moved? false
   ]

   set this-zero ticks
   set next-zero (max (list 2000 (this-zero + 10 * (this-zero - last-zero)))) 
   set last-zero this-zero
   reset-history
   set new-radius new-size * .5
   set escape-radius container-radius - new-radius
   ; set overlap-radius new-size 
   
   set circ-color wrap-color circ-color + 10
   
   let circle-area circle-count * pi * (new-size * .5) ^ 2
   let density circle-area / container-area
   let d/d circle-count / density
   

   set hex-pack-radius (k * 2 + 1) * new-size * .5
   set hex-pack-area pi * hex-pack-radius * hex-pack-radius 
   set hex-pack-density circle-area / hex-pack-area
   ask patch ( max-pxcor ) ( max-pycor - 1 ) [ set plabel ( word "r: " precision new-size 5 "  " ) ]
   ask patch ( max-pxcor ) ( max-pycor - 3 ) [ set plabel ( word "n0: " precision next-zero 0 "  " ) ]
   
   ask patch ( max-pxcor ) ( min-pxcor + 5 ) [ set plabel ( word "d: " precision density 5 ) ]
   ask patch ( max-pxcor ) ( min-pxcor + 3 ) [ set plabel ( word "hd: " precision hex-pack-density 5 ) ]
   ask patch ( max-pxcor ) ( min-pxcor + 1 ) [ set plabel ( word "D/d: " precision d/d 5 ) ]
   set time-since-zero 0
end


;;=========================================================================================
;;=========================================================================================
;;=========================================================================================
;;=========================================================================================
;; MOUSE DRIVER
;;=========================================================================================
;;=========================================================================================
;;=========================================================================================
;;=========================================================================================

to mouse:go
   if not any? pointers [ mouse:setup-pointer ]
   ask pointers
   [ ifelse mouse-inside?
     [ ;; mouse is inside
       set mx mouse-xcor
       set my mouse-ycor
       setxy mx my
       ;; did it just come inside?
       if outside?
       [ set outside? false
         mouse:do-go-inside
       ]
       ifelse mouse-down?
       [ if not in-click? [ set in-click? true mouse:do-click-start ]  mouse:do-down ]
       
       [ ;; mouse is up
         
         ;; did it just come up?
         if in-click?
         [ set in-click? false
           mouse:do-click-end
         ]
         mouse:do-hover
       ]
     ]
     [ ;; mouse is outside
       ;; did it just come outside
       if not outside?
       [ set outside? true
         mouse:do-go-outside
       ]
       mouse:do-outside 
     ]
   ]
end     

to mouse:do-go-inside debug-print "go-inside"
   show-turtle
end

to-report nearly-same [ a b ]
   report ( abs( [ xcor ] of a - [xcor] of b ) < collision-buffer and
   abs( [ ycor ] of a - [ycor] of b ) < collision-buffer
   )
end   
to mouse:do-click-start debug-print "click-start"
   
   if is-circle? hovered [ mouse:hover-drop ]
   if not is-circle? dragged 
   [ if any? circles
     [ set dragged min-one-of circles with [ mouse:quick-distance myself < [hover-radius^2] of myself ] [ mouse:quick-distance myself ]
     ]
   ]
end

to mouse:do-down
   if is-circle? dragged
   [ ask dragged [ setxy [ mx ] of myself [ my ] of myself ]
   ]
end

to mouse:do-click-end debug-print "click-end"
       set dragged nobody
end

to mouse:do-go-outside debug-print "go-outside"
   set dragged nobody
   if is-circle? hovered [ mouse:hover-drop ]
   hide-turtle
end

to mouse:do-outside
end

to mouse:do-hover 
   ifelse is-turtle? hovered 
   [ ifelse mouse:quick-distance hovered > hover-radius^2
     [ mouse:hover-drop
     ]
     [
     ]
   ]
   [  mouse:hover-pickup ]
end

to mouse:hover-pickup
   debug-print "get-hovered"
   let hoverable circles with [ mouse:quick-distance myself < size * size * .5 * .5 ] 
   if any? hoverable
   [ set hovered max-one-of hoverable [ who ]
     ask hovered [ begin-hover ]
     set hover-radius^2  .5 * .5 * size * size
     debug-print (word "(" hovered ")" )
   ]
end

to mouse:hover-drop
       debug-print "drop-hovered"
       ask hovered [ reset-hover ]
       set hovered nobody
end

to begin-hover
   set shape "circle"
end
   

to reset-hover
   set shape "circle-edge"
end   
to-report mouse:quick-distance [ agent ]
   ;; reports the square of the distance
   ;; avoids the slow square root function
   ;; useful when simply looking for nearest
   ;; or comparing distance
   ;; or comparing to a known squared distance
   let x2x [ xcor ] of agent - xcor
   let y2y [ ycor ] of agent - ycor
   report (x2x * x2x + y2y * y2y)
end

to mouse:setup-pointer
   create-pointers 1
   [ set shape "pointer"
     set color white
     set size 7
     set heading 0
     set dragged nobody
     set in-click? false
     set outside? true
     set hovered nobody
     hide-turtle
   ]
end
          
to debug-print [ message ]
   ;output-print message
end   

to-report hex [ number ]
   let hdigits "0123456789ABCDEF"
   let hx ""
   while [ number > 0 ]
   [ let ddigit number mod 16
     let hdigit item ddigit hdigits
     set hx (word hdigit hx)
     set number floor (number / 16)
   ]
   report hx
end

                    


Download Link

View or download the complete model file (to download: right-click, save-link-as):
-- Download circle-packing --