# How to calculate how many polygons I can put inside a polygon?

I usually use QGIS. I explain my problem with an example: there is a forest (irregular geometry1) and one tree (geometry2). I want to know the maximum number of trees that the forest can contain. Furthermore, I want a shapefile output of the best disposition of these trees inside the forest.

• Nice problem....
– WKT
May 13 '16 at 11:57
• I don't know how I would even start. Sounds like a Maters degree problem/algorithm. May 13 '16 at 12:13
• If you can gain access to a free trial of ArcGIS (or download R which is free), the Geospatial Modelling Environment software has a `gencirclesinpolys (Generate Circles In Polygons)` tool which could be useful. May 13 '16 at 12:42
• You're looking for a tool to solve Packing problems but I'm not aware of any for QGIS May 14 '16 at 21:22
• @Joseph I used the tool Geospatial Modelling Environment, it works. Unfortunately the tool generates a regular arrangement of circles (or hexagon) within the bounds of polygons, this implies that the output shape doesn't show (necessarily) the best disposition of the features, I mean the maximum number possible of it. May 18 '16 at 19:53

Interesting problem!

I've done a similar thing with irregular polygons (in this case, buildings were packed so as not to overlap)

Used postgresql and postgis, and python. Rough algorithm was

• Find random point in polygon's bounding box (ST_Envelope)
• If point outside polygon, go back one step
• Make a geometry for the tree centred this random point
• If that overlaps any existing placed tree (ST_Overlaps), go back to start
• Add tree at point
• Go back to start

I can't guarantee this will give the global optimum, you'd need a 'circle packing' algorithm for that (as others have mentioned).

It will carry on forever, so you'll need to put some code in to decide when to quit, e.g.

• when combined area of placed trees is a certain percentage of area of polygon
• when it takes more than N iterations to find a non-overlapping tree.

According to Circle Packing on Wikipedia, the best packing density is achieved with a hexagonal grid. It might be possible to create such a grid using MMQGIS, whose spacing is based on the size of your trees, which I assume are identical. Then placing a tree on each vertex. But then, you have the problem of knowing where to place the grid to maximize the number of trees.

Try this app online svgnest.com/

steps: 1. svg creates a file (as in Figure 1); 2. Go to the link and upload svg; 3. Select with the mouse the container polygon; 4. start

after a number of iterations, you can lock and download the svg file (see Figure 2)

NB: polygon and circles must be in the same file svg