Instead of the grid for the whole area I would create a grid from the bounding box of each feature. Based on this estimate the maximum number of circles that can be inside, and also estimate a most likely number of circles. Then som iterations would be necessary perhaps with some Artificial Intelligence algorithm.
Interesting question, would be fun to see the result if you have implemented some solution in FME. I don't think you're going to find an optimal answer, but a reasonable estimate should be possible. If you are going for a repeated grid center solution, keep in mind that the most efficient way of packing circles is in a hexagonal layout.
The simplest approach would be to create a filled space of hexagonally distributed circles, covering the bounding box as Sig suggested, and counting the circles that are completely covered by the parcel. You could add some form of local search in the form of Hillclimbing, Simulated annealing or Random search, but in my opinion a small number of iterations which move the grid in predetermined directions will give you a good estimate.
A different approach would make the assumption that the best packing has circles touching the edge of the parcel. If you do a negative Buffer with -circleradius on the parcels, you can start by fitting as many circles as possible (perhaps trying different starting positions) on the buffered boundary. You can count these circles, clip the parcelpolygon with them, and repeat the abovementioned steps.
If you have time, try a few methods and make it a competition, I'm curious to see how the different methods would perform.
Hello,
Thanks for the reactions.
This is the solution of something I just implemented:
Because I'm affraid of using iterations (would be nefast for performancy, my area is a lot bigger than just this sample), I used a 'simpler' approach which works well enough.
If someone is interested in what I did; here are the steps:
1. Create unique ID for each parcel
2. Create Bounding Box for each Parcel
3. Create grid (2.5 by 2.5 meters) of points in bounding box in each parcel and keep attributes _column and _row (they will be important later on)
4. Throw away the points falling outside the parcel (for performancy I first do this step before I do an overlay with the circles, step 6)
5. Buffer the points with radius 2.5 m (remark: they overlap eachother)
6. Throw away the circles which are not completely within the parcel
Now there is a group of circles falling completely within the parcel. But there is still overlap.
7. For each parcel, look for the most south-western circle which is kept and log its _column en _row attribute.
8. if the column-attribute is even, throw away all circles with odd colum-attribute, if the column attribute is odd, throw away all circles with even column attribute.
9. repeat the same for row-attribute. (so only keep even or odd rows)
(step 8 and 9) will nicely removed all the even of odd lines/rows, depending on the lower left circle.
Now I have the red circles of the drawing. (with a specific pattern as you see, without overlap, based on the eveness/oddness of the most lower left circle.)
10. One extra iteration is add. Check if there is still som parcel area which can be covered by circles which were removed in step (8) or (9).
If yes, repair them and uses the same method as in step 8 and 9 to prevent overlap.
So, it is not the best theoretical solution (you can't do that without iterations and dependencies), but this solution is sufficient for the purpose I'm using it.
