Repository navigation
Use single covering cell instead of initial tiling to simplify setup #81
Description
The current algorithm computes the bounding box of the polygon, selects the shortest side as the initial cell size, and then tiles the polygon with 1×1, 1×N or N×1 of these initial cells. Following that, it seeds the current best interior distance with the better of the bounds center or the polygon centroid.
Since the remainder of the algorithm has all the machinery to test and subdivide cells, we can rely on this and simplify the initial setup.
Instead of choosing the smallest side of the bounding box, choose the largest side, to compute the square cell that fully and tightly contains the polygon. Initialize the priority queue with this single cell, eliminating the tiling code from the original algorithm. Further, because this cell contains the bounds center (which is identical to the rectangular bounds center), you do not need to compute and choose between two initial best values — just use the polygon centroid distance.
Tested in my implementation, and works great.
Activity
mourner commentedon Feb 2, 2021
Thanks for bringing this up — I think it's worth trying out. As far as I remember, the reason I went for "cover with cells" is that theoretically it should be faster, because in cases where one axis is significantly bigger than the other, the current covering is likely to get good initial cells inside the polygon, thus converging faster, while with a single big cell that's inevitably split into 4 cells, centers of those 4 will likely be outside the polygon and converge to a good solution slower, with more cells to search. But that's just theoretical, and we need to measure with benchmarks say for sure.
mourner commentedon Jun 25, 2026
After #127 Polylabel is fast enough for this to not really matter much.