# Maximisation of circles that don't intersect other geometries within a given layer using QGIS

My context is an orchard in which certain trees already exist. I want to plant new trees that have to be at 10m from any other trees and from the border of the orchard. The grey points in the image are the already existing trees, the circles around them are buffer zones of 10m diameter, the red polygon is the orchard.

I'm trying to find a way to automatically draw the maximum number of circles of a given diameter (10m) within the polygon (the orchard).

I've buffered the already existing trees; I've created a layer "difference" which is contained within the orchard and excludes the buffers.

From there I only have to draw the circles but I can't find a tool doing this.

• Commented Oct 4, 2022 at 12:03

Disclaimer: I can't proof that this solution actually creates the maximum number of points/centroids and highly suspect that it doesn't - though `nearest neighbour analysis` returns a mean centroid distance of 10.74 m. Still, to the untrained eye the result looks "better" than the one suggest by Comrade Che.

But let's start at the beginning:

1. Buffer your area of interest (where you already subtracted the existing trees) with -5 m, providing you with the area the centroids of your to-be-planted trees need to be situated within.
2. Run `random points in polygons`. Your first input is your negatively buffered area of interest. Enter an adequately high number of points. In my example I tried to create 5000 points in an area of 100 by 200 m. This would be no issue, but I also forced a distance of at least 10 m between points, resulting in the pink-ish points you can see in the screenshot.
3. Buffer your not so random points by 5 m to create the "trees".

I suppose you could enforce a more optimal placement (and increase computation time) by allowing more iterations per points than the 10 I used.

/edit: I ran the same area with the same settings but allowed 1000 iterations per point and the number of created points increased from 124 to 129.

• could you give an estimation of the computation time for 10 and 1000 iteration ?
– J.R
Commented Oct 5, 2022 at 12:15
• About 1 second to half a minute @J.R
– Erik
Commented Oct 5, 2022 at 12:19

This solution looks much better than mine.

I don't think that's the optimal solution but you may try to:

1. Use this tool to generate points aroud and inside your polygon.
2. Buffer them with the right radius.
3. Delete circles that lay outside of the polygon.

• Thanks for your help, that's one way to get there but i don't think it maximises the number of circles :)
– jo.H
Commented Oct 4, 2022 at 12:36

Your task is an example of a mathematically interesting problem, called a packing problem, or more specifically, a circle packing problem maximizing the number of equal-sized circles within one or several irregularly shaped polygons.

In general, if the buffer around the new trees is circular and the free space for new trees is many trees in width in height (for a sufficient value of many), a hexagonal pattern will be optimal in large parts. This is because a hexagonal pattern is the most efficient packing pattern for circles only limited by themself.

However, for a small orchard, a plain hexagonal pattern is not the most efficient. I can't find any QGIS plugin for packaging problems; you probably have to research and implement some circle packing algorithm.

A similar question was also asked in 2016: How to calculate how many polygons I can put inside a polygon? In this, a link was posted to an online tool SVGnest that may help.