[Sidefx-houdini-list] Space filling circles

Andy Nicholas andy at andynicholas.com
Wed Aug 5 12:05:13 EDT 2009


Hi Doug,
Are you asking this because you know of this being done somewhere else? I
only ask because I just Googled this (out of my own interest), and judging
on how many papers are written on this topic, I'd say that it's a
non-trivial problem to solve.

The only thing that springs to mind, would be to create an iterative
approach, using the SOP solver or the Feedback SOP (proto_install).

Note that I haven't tested this, or fully thought it through, but the
following... might... just...  work...

Start off with a triangular polygon with a random sized disc at each
vertex so that their circumferences touch. From that, take a pair of discs
and create another randomly sized one and place it (using simple
trigonometry) so that it touches the first two. Extend the triangle into a
four sided polygon with the new point at the center of the new disc.
Repeat the process, but ignoring any discs internal to the polygon.

I can see this approach breaking down if you ever have a non-convex
polygon, but there are probably some constraints that you could figure out
that will prevent this from happening.

Andy




> Hi
>
> Can anyone point me to a Houdini method (or other solution) for packing
> random sized circles so that they are tightly packed and each
> circumference
> just touches its neighbors?
>
> Thanks
>
> Doug
>
> --
> www.dougstruthers.com
> _______________________________________________
> Sidefx-houdini-list mailing list
> Sidefx-houdini-list at sidefx.com
> https://lists.sidefx.com:443/mailman/listinfo/sidefx-houdini-list
>





More information about the Sidefx-houdini-list mailing list