Are there any algorithms for solid polygon clustering?

Question

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.

Answer 1

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

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

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

3. I think this bottleneck problem may be significantly reduced with center jumps - jump center of the smallest cluster to the biggest one.

UPD March 2022: Sources of the playground.

Answer 2

K-means will not work well, because how do you compute and use the "mean"? How do you ensure convergence? Furthermore, distance computations will be expensive and cannot be reused.

Instead, use any algorithm that can be used with a distance matrix. For example: hierarchical clustering, PAM (k-medoids, similar to k-means but using an arbitrary distance matrix) and DBSCAN.

Compute the distance matrix only once, as this will be fairly expensive. Then try out different algorithms and parameters.