lwgeom_cluster_2d_kmeans()

int* lwgeom_cluster_2d_kmeans	(	const LWGEOM **	geoms,
		uint32_t	ngeoms,
		uint32_t	k
	)

Take a list of LWGEOMs and a number of clusters and return an integer array indicating which cluster each geometry is in.

Parameters

geoms	the input array of LWGEOM pointers
ngeoms	the number of elements in the array
k	the number of clusters to calculate

Definition at line 240 of file lwkmeans.c.

{
        uint32_t i;
        uint32_t num_centroids = 0;
        uint32_t num_non_empty = 0;
        LWGEOM** centroids;
        POINT2D* centers_raw;
        const POINT2D* cp;
        int result = LW_FALSE;
 
        /* An array of objects to be analyzed.
         * All NULL values will be returned in the KMEANS_NULL_CLUSTER. */
        POINT2D** objs;
 
        /* An array of centers for the algorithm. */
        POINT2D** centers;
 
        /* Array to fill in with cluster numbers. */
        int* clusters;
 
        assert(k > 0);
        assert(n > 0);
        assert(geoms);
 
        if (n < k)
        {
                lwerror("%s: number of geometries is less than the number of clusters requested, not all clusters will get data", __func__);
                k = n;
        }
 
        /* We'll hold the temporary centroid objects here */
        centroids = lwalloc(sizeof(LWGEOM*) * n);
        memset(centroids, 0, sizeof(LWGEOM*) * n);
 
        /* The vector of cluster means. We have to allocate a chunk of memory for these because we'll be mutating them
         * in the kmeans algorithm */
        centers_raw = lwalloc(sizeof(POINT2D) * k);
        memset(centers_raw, 0, sizeof(POINT2D) * k);
 
        /* K-means configuration setup */
        objs = lwalloc(sizeof(POINT2D*) * n);
        clusters = lwalloc(sizeof(int) * n);
        centers = lwalloc(sizeof(POINT2D*) * k);
 
        /* Clean the memory */
        memset(objs, 0, sizeof(POINT2D*) * n);
        memset(clusters, 0, sizeof(int) * n);
        memset(centers, 0, sizeof(POINT2D*) * k);
 
        /* Prepare the list of object pointers for K-means */
        for (i = 0; i < n; i++)
        {
                const LWGEOM* geom = geoms[i];
                LWPOINT* lwpoint;
 
                /* Null/empty geometries get a NULL pointer, set earlier with memset */
                if ((!geom) || lwgeom_is_empty(geom)) continue;
 
                /* If the input is a point, use its coordinates */
                /* If its not a point, convert it to one via centroid */
                if (lwgeom_get_type(geom) != POINTTYPE)
                {
                        LWGEOM* centroid = lwgeom_centroid(geom);
                        if ((!centroid)) continue;
                        if (lwgeom_is_empty(centroid))
                        {
                                lwgeom_free(centroid);
                                continue;
                        }
                        centroids[num_centroids++] = centroid;
                        lwpoint = lwgeom_as_lwpoint(centroid);
                }
                else
                        lwpoint = lwgeom_as_lwpoint(geom);
 
                /* Store a pointer to the POINT2D we are interested in */
                cp = getPoint2d_cp(lwpoint->point, 0);
                objs[i] = (POINT2D*)cp;
                num_non_empty++;
        }
 
        if (num_non_empty < k)
        {
                lwnotice("%s: number of non-empty geometries is less than the number of clusters requested, not all clusters will get data", __func__);
                k = num_non_empty;
        }
 
        if (k > 1)
        {
                kmeans_init(objs, clusters, n, centers, centers_raw, k);
                result = kmeans(objs, clusters, n, centers, k);
        }
        else
        {
                /* k=0: everythong is unclusterable
                 * k=1: mark up NULL and non-NULL */
                for (i = 0; i < n; i++)
                {
                        if (k == 0 || !objs[i])
                                clusters[i] = KMEANS_NULL_CLUSTER;
                        else
                                clusters[i] = 0;
                }
                result = LW_TRUE;
        }
 
        /* Before error handling, might as well clean up all the inputs */
        lwfree(objs);
        lwfree(centers);
        lwfree(centers_raw);
        lwfree(centroids);
 
        /* Good result */
        if (result) return clusters;
 
        /* Bad result, not going to need the answer */
        lwfree(clusters);
        return NULL;
}

References centroid(), getPoint2d_cp(), kmeans(), kmeans_init(), KMEANS_NULL_CLUSTER, LW_FALSE, LW_TRUE, lwalloc(), lwerror(), lwfree(), lwgeom_as_lwpoint(), lwgeom_centroid(), lwgeom_free(), lwgeom_get_type(), lwgeom_is_empty(), lwnotice(), LWPOINT::point, and POINTTYPE.

Referenced by ST_ClusterKMeans(), and test_kmeans().

Here is the call graph for this function:

Here is the caller graph for this function: