I have a layer of points and I would like to create clusters where a predefined square area of 5km by 5km is the boundary for the cluster.

Is there a way to iteratively draw square polygons around the points so that the polygons are not overlapping and contain at least 1 point and not more than a 100 points? The polygons can be rotated to get the best fit.

It would be better not to start with one cluster containing the maximum number of points as a starting point but rather to try evenly distribute the points in the clusters especially with dens areas with lots of points. The cluster size of 1 should be only created if there is no possibility to combine at least two points.

I am imagining the following rules.
start with:
- find the biggest cluster of points where area is bigger than 5km by 5km, draw the boundaries around it so it can be in next step divided into even 5km by 5km squares(big one can be rotated to get the best fit so minimizing the empty space)
- find the next cluster by size and repeat the procedure
- find any number of points which can fit the 5km by 5km
- in the last instance find the single points and draw 5km by 5km squares

It would be like drawing a customized grid.

I had to create this task very quickly so I used square buffers and join by location algorithms but had to adjust dens locations by hand. I will have more points (around 20k) in the future and would like to automate the procedure.

I used QGIS but I was thinking this could be probably done also with R.

How could this be achieved and what tools could be used to do it?

Clusters bounded by rectangule Dens area

  • I'm not certain this is a well-posed question yet. A 5km x 5km regular grid, with the empty cells removed, would satisfy most of your conditions, unless one cell had > 100 points in, but there could be dense point patterns where its impossible to put 5km cells without having a cell with 100 points in. Are you wanting to minimise the number of 5km cells? I suspect finding the true optimum is a computationally hard problem, finding a good solution might involve genetic algorithms or other stochastic algorithms. – Spacedman Sep 6 '18 at 13:19
  • I did try the grid but the outcome was too random. I would try to control the square position with a sort of rules mention above. Rather minimizing I would say optimizing. I can imagine the rules but how and in which tools could be done. I will try to find some help in R exchanges. – Primož Dolžan Sep 7 '18 at 11:27
  • If you can "imagine the rules" can you edit your question to include them written down? Have you considered a simpler problem, such as using circles instead of squares, to get a handle on the complexity? – Spacedman Sep 7 '18 at 13:45
  • I did add them but I don't know if they are optimal in terms of hierarchy. Unfortunately, they have to be squared. – Primož Dolžan Sep 7 '18 at 16:01
  • You could use the "circles" idea that @Spacedman recommended and then create a square polygon around each circle using the extent of each circle. This however, does not deal with the variable orientation that you seem to be after. I think that this equates to an optimization problem and is more complex than you seem to think but, we do not have enough information on specifics to really make specific recommendations. – Jeffrey Evans Sep 7 '18 at 16:41

Your Answer

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

Browse other questions tagged or ask your own question.