# Closest disc packing in Python

My spare time project. Find the closest disc packing in Python.

Why does one come to complex math problems in his spare time?

It started quite simple. I thought about usefull christmas presents for my people and my 3D-Printer to provide them.

The first thing that came to my attention was a Pen-Holder for their desk.

The Idea a stole somewhere. And reimplemented it with SolidPython.

The uniform hexagonal pattern is quite nice but a bit sterile (not individual). So I started to playing around with random holes.

But these did not have the organic (Jungendstil) look I tried to achieve.

Then I found a paper on closed disc packaging with images of holes exactly what I was looking for.

But to achieve this I would have to go a lot of steps and have to write a lot of Python code.

The solution for this closest disc problem utilizes Voronoi diagrams (or their inverse formulation as Delauny trinagulations).

At first I hunted numpy/scipy for Voronoi diagram.

ScyPi has a Voronoi function but the code behind it comes from a completely different aim: Game programming.

In game programming you need often the convex hull of a 3D-Object e.g. for collision detection.

So ScyPi uses in fact gaming code from the qhull project. This seems funny but we were already using gaming code for science in an other project.

For the EU Volcanic Ash monitoring site https://e-profile.eu we utilize the JS PIXI 2D gaming engine to realize heatmaps with high performance.

Most JS graphic systems utilize SVG which cannot deliver heatmaps in realtime.

The Qhull code is ok, but I do not like wrappers in my code base. If I later try to optimize any wrapper sucks.

So I extended my search to pure python implementations for voronoi diagrams.

There were three candidates:

https://github.com/jansonh/Voronoi

https://github.com/Yatoom/voronoi

https://pypi.org/project/SweeplineVT/

I chose  https://github.com/Yatoom/voronoi  since Yatoom had already implemented a polygonal bounding box.

I decided to extent Yatoom's code with circular bounding box.

Read on in From Bounding Polygone to Circle