# 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

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

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