circle packing algorithm

[MCLKEL003]

Hi, 

I am looking to create a geometry consisting of hexagonally packed spheres along the interior walls of a closed cylinder (ie. along end walls and azimuthal walls). It does not have to be optimal, so where the end walls meet the azimuthal wall there is some leniency, but there can be no overlap of the spheres. I am a relatively new AutoCAD user, so I am wondering if

a) there is code already generated which will hexagonally pack circles/spheres within a surface, or 

b) if AutoCAD is the best program to use for something so mathematically technical. If not, does anyone have a suggestion as to which program will be able to accomplish this project?

I really appreciate any advice...

Thank you,

Kelly

[martti.halminen]

---

@MCLKEL003 wrote:

I am looking to create a geometry consisting of hexagonally packed spheres along the interior walls of a closed cylinder (ie. along end walls and azimuthal walls). It does not have to be optimal, so where the end walls meet the azimuthal wall there is some leniency, but there can be no overlap of the spheres. I am a relatively new AutoCAD user, so I am wondering if

a) there is code already generated which will hexagonally pack circles/spheres within a surface, or 

b) if AutoCAD is the best program to use for something so mathematically technical. If not, does anyone have a suggestion as to which program will be able to accomplish this project?

---

One idea: start with the 2-D case: circles inside a larger circle. Generate a sufficiently large set of circles hexaconally placed (either programmatically or playing with the ARRAY command), placing one of them exactly touching the edge, and then destroy any that are outside or intersect the edge.

- calculate the 3-D offset for the next layer and repeat.

--

[Kent1Cooper]

---

@MCLKEL003 wrote:

.... 

I am looking to create a geometry consisting of hexagonally packed spheres along the interior walls of a closed cylinder (ie. along end walls and azimuthal walls). ....

---

Assuming a cylinder whose ends are perpendicular to its azimuthal walls, and with an end sitting on the WCS and the cylinder projecting upward, here's a way to line the base of the azimuthal walls with a first layer of touching spheres.  To fill in the floor inboard of them is another issue, and to get the next layer of them right seems a challenge (rotationally is easy -- the vertical part could be tricky).  But maybe it's a start, and demonstrates that AutoCAD is capable of this sort of thing.

If you have an existing cylinder, maybe you can extract its inside surface radius somehow, though I'm not sure how if it's a 3D solid.  If it's sitting on its end as assumed, the level and center of the base can be calculated from its bounding box.

[When fully developed, the routine would turn off running object snap, but you can do that for now.  And it should also check that the sphere radius is less than half the cylinder radius.]

(setq
  ctr (getpoint "\nCenter of base of Cylinder: ")
  rc (getdist "\nRadius of inside Cylinder wall: ")
  rs (getdist "\nRadius of Spheres: ")
  ang (* 2 (atan (/ rs (sqrt (- (expt (- rc rs) 2) (expt rs 2))))))
); setq
(command
  "_.circle" ctr rc ; [for visual confirmation here -- not needed with existing cylinder]
  "_.sphere" (mapcar '+ ctr (list (- rc rs) 0 rs)) rs
  "_.array" "_last" "" "_circular" ctr (angtos ang) (fix (/ (* pi 2) ang)) ""
); command

[MCLKEL003]

Hi guys, thanks for your suggestions. Kent, I will try your method for generating spheres along the bottom layer. Maybe I didn't make it clear, but all I need is one layer of spherical particles lining each interior wall of the cylinder...so if this works..problem solved 🙂 🙂 

Thank you!

[Kent1Cooper]

---

@MCLKEL003 wrote:

... I will try your method for generating spheres along the bottom layer. Maybe I didn't make it clear, but all I need is one layer of spherical particles lining each interior wall of the cylinder...so if this works..problem solved 🙂 🙂 

...

---

I think I understood correctly, but an image or sample drawing would be helpful.

What I suggested puts spheres touching the inside of the cylinder and each other around the edge of the flat end, as many as fit, which almost always means there's a gap between the last and first spheres.  Those could be copied/rotated to additional layers that would be in "true" hexagonal packing lining the curved cylinder wall, with each one touching six others around it.  However, if the idea is to get the most in, it would be better to spread out those on each level equally, so there are small gaps between all of them, they don't touch their companions on the same level, and each touches only four others on the levels above and below [except those on the top and bottom levels].  That wouldn't be a regular-hexagonal pattern relative to the curved surface, but would shorten the vertical distance between levels, and therefore get more spheres in, and would be the same all the way around instead of having a gap.  Does that sound like the way to go?

[I've already got something close to filling in the "floor" worked out -- not quite there yet, but hang on....]

[REID7800]

I hope you don't mind me revising your lisp, kentlcooper

(defun c:test ( / cad ad as *error* addcircle ctr rc rs ang s ) (vl-load-com)

  (defun cad nil
    (setq *acad*
      (cond ( *acad* )
        ( (vlax-get-acad-object) )
      ) 
    )
  )

  (defun ad nil
    (setq *acdoc*
      (cond  ( *acdoc* )
        ( (vlax-get (cad) 'ActiveDocument) ) 
      )
    )
  )


  (defun as nil (ad)
    (cond
      ( (eq AcModelSpace (vlax-get *acdoc* 'ActiveSpace))
        (vlax-get *acdoc* 'ModelSpace)
      )
      ( (vlax-get *acdoc* 'PaperSpace) )
    )
  )
 (defun *error* ( m )
    (or (wcmatch (strcase m) "*BREAK,*CANCEL*,*EXIT*")
        (princ (strcat "\n** Error: " m " **")))
    (princ)
  )

  (defun addcircle ( radius insertionpoint layer flag / e )
    (setq e
      (entmakex
        (list
          (cons 0 "circle")
          (cons 8 layer)
          (cons 10 insertionpoint)
          (cons 40 radius)
        )
      )
    )
    (if (and e flag)
      (vlax-ename->vla-object e) e
    )
  )

  (if
    (and
      (setq ctr (getpoint "\nSpecify center of circle: "))
      (setq rc (getdist "\nSpecify radius of circle: "))
      (setq rs (getdist "\nSpecify radius of spheres: "))
      (setq ang (* 2 (atan (/ rs (sqrt (- (expt (- rc rs) 2) (expt rs 2)))))))
    )
    (progn
      (addcircle rc ctr (getvar 'clayer) t)
      (setq s
        (vlax-invoke (as) 'AddSphere
          (mapcar (function +) 
            ctr (list (- rc rs) 0 rs)
          ) rs
        )
      )
      (vlax-invoke s 'arraypolar (fix (/ (* pi 2) ang)) (* pi 2) ctr)
    )
  ) (princ)
)

[martti.halminen]

Here is my implementation of this. Still has bugs in the vertical direction, but I don't have any more time to play with this.

(defun shrapnel (rshell rball h / i n startpt offset1 offset2 ent)
  ;; Draws spheres (radius = rball) inside a cylinder (radius = rshell, height = h)
  ;; base center at (rshell 0 0), h in the Z direction
  ;; -- better take OSNAP off before this...
  (setq n (1+ (fix (/ rshell rball))))
  (setq rshell (float rshell)
        rball (float rball))
  (setq startpt (list (- rball) 0 rball)
        offset1 (times rball (list 1.0 (/ 1 (sqrt 3)) (/ (sqrt 2)(sqrt 3))))
        offset2 (times rball (list 0.0 0.0 (* 2 (/ (sqrt 2)(sqrt 3)))))
        ent (entlast))
  (repeat (fix (/ h (* rball (+ 1 (* 2 (/ (sqrt 2)(sqrt 3)))))))
    (layer-of-balls rball startpt n)
    (layer-of-balls rball (plus startpt offset1) n)
    (setq startpt (plus startpt offset2)))
  (while (setq ent (entnext ent))
    (if (outside-cyl-p ent (- rshell rball) (list rshell 0 0))
        (entdel ent)))
  (vl-cmdf "_CIRCLE" (list rshell 0.0 0.0) rshell))


(defun layer-of-balls (R startpt n / i P2)
  (setq P2 startpt)
  (line-of-balls R startpt n)
  (setq i 1)
  (repeat (1+ (/ n 2))
    (line-of-balls R
                   (setq startpt
                         (polar startpt
                                (if (oddp i)
                                    (/ pi 3)
                                    (* 2 (/ pi 3)))
                                (* 2 R)))
                   n)
    (line-of-balls R
                   (setq P2
                         (polar P2
                                (if (oddp i)
                                    (/ pi -3)
                                    (* 2 (/ pi -3)))
                                (* 2 R)))
                   n)
    (setq i (1+ i))))


(defun line-of-balls (r startpt n / i)
  ;; draws a line of n balls in the X direction from a given startpoint (center of the first ball)
  (setq i 0)
  (repeat n
    (vl-cmdf "_SPHERE"
             (plus startpt (times i (list (* 2 r) 0 0)))
             r)
    (setq i (1+ i))))

(defun outside-cyl-p (ent radius pt)
  ;; is the centerpoint of entity outside of a vertical cylinder centered at pt
  (> (+ (sqr (- (x pt) (getpropertyvalue ent "SolidPosition/X")))
        (sqr (- (y pt) (getpropertyvalue ent "SolidPosition/Y"))))
     (sqr radius)))

(defun x (pt) (car pt))

(defun y (pt) (cadr pt))

(defun sqr (x) (* x x))

(defun plus (p1 p2)
  ;; sum of two points/vectors
  (mapcar (function +)
	  p1 p2))

(defun times (a b)
  ;; Generic multiplication (unfinished, only scalar*list so far...)
  (cond
    ((and (numberp a) (listp b))
     (mapcar (function (lambda (item)
               (* a item)))
             b))
    ((and (listp a) (numberp b))
     (times b a))
    (T (alert (strcat "unhandled case in TIMES: " (vl-princ-to-string a) "  "
                      (vl-princ-to-string b))))))

(defun oddp (num)
  (not (zerop (rem num 2))))

 --

[Kent1Cooper · Accepted solution]

---

@Kent1Cooper wrote:

.... if the idea is to get the most in, it would be better to spread out those on each level equally, so there are small gaps between all of them....  Does that sound like the way to go?

[I've already got something close to filling in the "floor" worked out -- not quite there yet, but hang on....]

---

Give this a whirl....  I assumed the equally-spaced option in the attached CylinderSphereLine.lsp with its CSL command, though it has some instructions for having the spheres in each ring always touching each other instead.

I'm sure the "floor" surface fill could be optimized.  This puts either the center of a sphere or the tangency point between two spheres at the center, but there are situations in which putting the "center of gravity" point between three touching spheres at the center would get more in.  I haven't figured out yet how to determine which is best in a particular situation, but I'll think about it.

Also, it sits the rings of spheres on the bottom end and builds up from there, so in many situations there's empty space above the top ring, and the "ceiling" spheres aren't at the same level as the top ring.  It could be adjusted to space the rings equally so the top ring is against the ceiling, if that would be preferred.

[MCLKEL003]

Hi all, thank you for all of your solutions....it was extremely helpful, and gave me the information I needed.

@Kent: Having equally spaced gaps between each sphere around the circumference was the best solution for what I needed. In the vertical direction, it does not matter so much, as I can adjust the height of the cylinder. In terms of optimizing the bottom, well, as the radius of my cylinder is large in comparison to the sphere radius, the position of the central spheres in relation to the cylinder's center is insignificant enough to ignore. If it's OK with you, I would like to alter your code such that the two ends of the cylinder are hexagonally packed right to the edges of the cylinder, and have the ring of spheres begin in the next layer up. As my end goal is to have a corrugated inner liner for the cylinder, I think this will give me the configuration with the fewest gaps. 

Thanks

Kelly

[Kent1Cooper]

---

@MCLKEL003 wrote:

.... I would like to alter your code such that the two ends of the cylinder are hexagonally packed right to the edges of the cylinder, and have the ring of spheres begin in the next layer up. ....

---

This modification seems to do that [limited testing].

[martti.halminen]

If you are interested in the mathematical side of this, there is a Wikipedia page:

http://en.wikipedia.org/wiki/Close-packing_of_equal_spheres

--

[Kent1Cooper]

---

@martti.halminen wrote:

If you are interested in the mathematical side of this, there is a Wikipedia page:

.... 

---

I guess one could have assumed someone would have worked out the mathematics of this kind of thing. 

That's about filling a volume, rather than lining a surface.  What I'm interested in [even though the OP says it's not essential] is optimizing the number of Circles you can get on the flat end surfaces of the Cylinder.  There's this site, and this other one, but both start with a quantity of Circles to pack in and calculate the smallest Circle they'll fit in, rather than starting with a known larger Circle size and figuring how to fit the most in.  Maybe it could be worked backwards somehow.  I'd be content to limit it to purely hexagonal arrays, with the variant being what's at the center, but it looks from those sites as though that's often not the optimum.  I'd have to look more deeply into it all.

[martti.halminen]

Yes, seems I misread the original post. I've been thinking about filling the whole cylinder, not just lining  the walls.

--