Generative Circle Packing

This experiment is based on matsys pseudo-code, which is not completely self explained. Nevertheless I found the way to fill the gaps crating a mixture between the 2 algorithms. Circle Packing has different applications, The pseudo code and algorithm showed below is focused in Unequal circles (random radius).

According to Wikipedia:

There are also a range of problems which permit the sizes of the circles to be non-uniform. One such extension is to find the maximum possible density of a system with two specific sizes of circle (a binary system). Only nine particular radius ratios permit compact packing, which is when every pair of circles in contact is in mutual contact with two other circles (when line segments are drawn from contacting circle-center to circle-center, they triangulate the surface). For seven of these radius ratios a compact packing is known that achieves the maximum possible packing fraction (above that of uniformly-sized discs) for mixtures of discs with that radius ratio. All nine have ratio-specific packings denser than the uniform triangular packing, as do some radius ratios without compact packings.

It is also known that if the radius ratio is above 0.742, a binary mixture cannot pack better than uniformly-sized discs.[9] Upper bounds for the density that can be obtained in such binary packings at smaller ratios have also been obtained.



CIRCLE PACKING ALGORITHM
Pseudo code
  1. Input: Maximum radius, boundary, iterations (not necessary the number of circles).
  2. Add in a random position, a circle with the maximum radius. Which is the maximum space that the circle can fill up.
  3. Add a Random Point.
  4. Test if the random Point is inside of the circle created. Else, delete the point and add another random point until the point is outside.
  5. Add line from the point to the center of the circle. If the distance is greater than the maximum radius add a circle at that point with the maximum radius. If the distance is less than the maximum radius, add a circle with the measured distance.
  6. Add another point and test if this point is within the other circles.
  7. Add a line to every center circle to find the closest circle.
  8. Repeat from step 5 until the number of iterations is reached.


Code
Option Explicit
'Script written by Carlos de la Barrera
'Script copyrighted by Carlos de la Barrera

Call Main()
Sub Main()
    Dim Pt, R
    Pt = Array(rnd * 100, rnd * 100, 0)
    R = FuncCir(Pt, 10)

Call Pack(R)
End Sub

Function Pack(R)

    Dim Pt, i, count
    count = Rhino.GetInteger(" number of circles ", 50, 2, 1000)
    If IsNull (count) Then Exit Function
    Dim ArrData()

    For i = 0 To count
        ReDim Preserve ArrData(i)
        ArrData(i) = R
        Pt = Array(Rnd * 100, rnd * 100, 0)
        Dim j
        Dim t: t = 0

        For j = 0 To UBound(ArrData)
            If Rhino.IsPointOnSurface(ArrData(j)(1)(0), Pt)Then
                Call Rhino.print ("point in surface")
                t = t + 1
            End If
        Next

        If (t = 0) Then
            ReDim ArrLine(UBound(ArrData))
            Dim k, line

            For K = 0 To UBound(ArrData)
                line = Rhino.AddLine(Pt, Rhino.CircleCenterPoint(ArrData(k)(0)))
                ArrLine(k) = Line
            Next

            Dim d, d2, l
            d = funcDist(Pt, ArrData(0)(0), ArrLine(0))

            For l = 0 To UBound(ArrLine)
                d2 = funcDist(Pt, ArrData(l)(0), ArrLine(l))
                If d < d2 Then
                    'Call Rhino.Print ("nothing")
                Else
                    d = d2
                End If
            Next

            R = FuncCir(Pt, d)
            Call Rhino.DeleteObjects (ArrLine)
        End If
    Next

End Function

Function FuncCir(p, D)
    If D >= 10 Then
        D = 10
    End If
    Dim plane
    Dim R(1)
    plane = Rhino.PlaneFromFrame(p, Array(1.0,0.0,0.0), Array(0.0,1.0,0.0))
    R(0)   = Rhino.AddCircle(plane, D)
    R(1) = Rhino.AddPlanarSrf(Array(R(0)))
    FuncCir = R
End Function

Function funcDist(Pt, circleP, Line)
    Dim Ap, j, d
    Ap = Rhino.CurveCurveIntersection (circleP, Line)
    For j = 0 To UBound(Ap)
        d = Rhino.Distance(Pt, Ap(j, 1))
    Next
    funcDist = d
End Function



RESULTS

First test


Color implementation


Test with bigger radius, 10,000 iterations and the max radius is 500


The number of iterations is 4,000, which is approximate the number of circles included in the packing. Max radius is 100


It's not difficult to implement spheres instead circles in the algorithm


The process runs very similar way


Close up to the sphere packing


9 Comments:

Add a comment

Comments

Written on Fri, 27 Jan 2017 9:30:00 by
Joakim

Hi, Think I have browsed the whole internet for theorems, paper and blogs about circle packing. I am working on a pseudo-random (non-iterative - ordo(n) ) circle packing generator and have found how hard it is. So far I'm not very much closer than above, but I'm working on it. My goal is to create a procedural texture that creates a circle packing pattern in an OSL-shader. You can see my results so far here: https://blenderartists.org/forum/showthread.php?414289-Math-help-needed-packing-algorithm Any ideas or where to look for someone done this, please let me know!

Written on Sun, 24 Jan 2016 9:30:00 by
designemergente

Hi Mark, no I haven’t work again in random circle parking. why you ask?

Written on Sat, 23 Jan 2016 00:04:52 by
Mark

Are you still trying to work on the random circle packing problem?

Written on Mon, 4 May 2015 14:21:17 by
designemergente

The number of circles defined in the code is approximate amount, since the algorithm might discard some of them because there is chance the point is inside another circle.

Written on Thu, 1 Dec 2011 19:50:06 by
designemergente

Hello Rara, Right now I’m so far from my home, I do not have access to my code. sorry for the delay. It will be the first thing that I do when I come back. best C,

Written on Tue, 22 Nov 2011 21:32:40 by
Rara

That is, if it is a script… Thanks!

Written on Tue, 22 Nov 2011 21:32:40 by
Rara

Hi, is this script downloadable somewhere?

Written on Fri, 14 Nov 2008 17:02:14 by
designemergente

hello Tobias, thanks for the post, I’ve been looking your blog and it’s very interesting. I never work in grasshopper before. I use GC When I need Generative scripting. the other day show me the new GC, and has a new association windows very similar to GH and you can invert the relations of the components, I don’t know if you can do this by GH. the people for bentley told me that the new Gc will appear the next year, after the new Microstation version. well thanks a lot, keep in touch best C.

Written on Thu, 13 Nov 2008 21:26:16 by
Tobias

Hello, I seem to be interested in simliar things. I did a couple of exercises on cricle packing and sphere packing in Rhino and processing. Recently I translated some of my packing rhinoscripts into vb.net components in Grasshopper. Have a look at http://tobesch.wordpress.com/category/research/. Regards, Tobias