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.enter image description here

  • 3
    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
  • 2
    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.
    – Joseph
    May 13 '16 at 12:42
  • 3
    You're looking for a tool to solve Packing problems but I'm not aware of any for QGIS
    – underdark
    May 14 '16 at 21:22
  • 1
    @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.
    – ksatzu
    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)

enter image description here

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

figure 1

figure 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.