# Are there any algorithms for solid polygon clustering?

I'm looking for something like K-Means for dividing solid polygons into regions. K-Means clusters discrete points. But I want to cluster (that is, partition) the points of solid polygons.

I don't see any problems with implementing K-Means extension for this case but I want be sure before reinventing the wheel.

So questions:

1. Are there any algorithms for solid polygon clustering?
2. Are there any implementations (preferably in javascript)?

I looked at GIS clustering but everything I found is about polygon clustering for zooming. And a polygon is a convex hull of geo markers and deeply inside it is about clustering discrete points.

• Did you mean clustering using Voronoi cells? Because those look like Voronoi cells to me. You can do that using Scipy Oct 11 '19 at 0:25
• @HS-nebula yes, there are Voronoi cells on picture and I cluster using them. I looked for reference description of such approach. Oct 11 '19 at 0:48
• I edited the English because the original question seemed very unclear and about some other problem. Oct 11 '19 at 6:55

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

1. Building Voronoi diagram for k centers with Fortune's algorithm: O(k log(k)). Expected that you have centers and cells as result.

2. Intersect each Voronoi cell with clustered polygon. I use algorithm from polygon-clipping package.

From description:

"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).

1. 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).

1. 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.

1. K-Means result will be less accurate.

2. If n >> m log(m) then K-Means will be slower than solid clustering.

Interesting points

1. 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.

2. 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.

1. I think this bottleneck problem may be significantly reduced with center jumps - jump center of the smallest cluster to the biggest one.
• Very nice. Never thought about this simple continuous version of K-means. It has a scientific name: en.wikipedia.org/wiki/Centroidal_Voronoi_tessellation. If you have time, please add one of the illustrations, e.g., about the points migrating through a bottleneck here. Oct 11 '19 at 6:54
• @Valentas do you mean add illustration to the question or to the wiki? I don't understand. Oct 11 '19 at 11:05
• I mean adding it to the answer. Oct 11 '19 at 11:08