Finally I just implemented solution as I planned and described it in Medium post.
This is "K-Means for solid polygons". I made a playground on my github.io.
A bit more details of solid clustering approach.
K-Means complexity is O(nkdi) or O(nk) per iteration without d,
- n is the number of d-dimensional vectors (to be clustered)
- k the number of clusters
- i the number of iterations needed until convergence.
Complexity estimation of solid clustering
Suppose that clustered polygon has no self-intersections.
- k - number of clusters
- m - number of points in clustered polygon (to not mix with K-Means n).
Step complexity estimations
Building Voronoi diagram for k centers with Fortune's algorithm: O(k log(k)). Expected that you have centers and cells as result.
Intersect each Voronoi cell with clustered polygon.
I use algorithm from polygon-clipping package.
"The Martinez-Rueda-Feito polygon clipping algorithm is used to
compute the result in O((n+k) log(n)) time, where n is the total
number of edges in all polygons involved and k is the number of
intersections between edges."
Total number of edges for us is m and edges in Voronoi cell Tmp. In complex polygon case m >> Tmp. I don't know how to estimate number of intersections but I think with big m it can be ignored.
So full estimation of this step O(m log(m) k).
- Complexities of polygon area and center of weight are O(m).
What is the number of polygon points estimation?
In worst case one Voronoi cell polygon has (k-1) edges.
Clustered polygon has m edges.
As I can imagine in the worst case intersection of the worst Voronoi cell and the worst polygon will produce 3n/2 edges polygon.
As a result the upper boundary of this step is O(nk).
- Centers of weight are new centers - move to step 1.
Final complexity estimation is O(k log(k) + m log(m) k + m k) => O(m log(m) k) per iteration.
What does it mean?
If we want to solve the same problem of solid polygon clustering with K-Means then we need to discretize original polygon to K-Means points.
K-Means result will be less accurate.
If n >> m log(m) then K-Means will be slower than solid
K-Means includes density as part of clustering process. Some points may be heavier than other.
Solid clustering ignores density so weights of all clustered points are equal.
We can see bottleneck effect in solid clustering. Clustering tries to spread cluster centers to have equal density. But cluster center can't jump out of its polygon so it slowly moves from dense area to spatial. In certain conditions we can see the same effect in K-Means.
- I think this bottleneck problem may be significantly reduced with center jumps - jump center of the smallest cluster to the biggest one.