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.
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
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.