2
$\begingroup$

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.expected polygon clustering

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.

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

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.

enter image description here

  1. I think this bottleneck problem may be significantly reduced with center jumps - jump center of the smallest cluster to the biggest one.
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Valentas Oct 11 at 6:54
  • $\begingroup$ @Valentas do you mean add illustration to the question or to the wiki? I don't understand. $\endgroup$ – NtsDK Oct 11 at 11:05
  • $\begingroup$ I mean adding it to the answer. $\endgroup$ – Valentas Oct 11 at 11:08
  • 1
    $\begingroup$ I added more information about complexity and interesting points (including bottleneck situation) $\endgroup$ – NtsDK Oct 13 at 21:55
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As is K-Means is not applicable to my problem (as it already mentioned in question). I don't ensure convergence with math. I want to try naive way and it works. Question in NOT about discrete points clustering. So I have no distance matrix and clustering with it. $\endgroup$ – NtsDK Oct 11 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.