kmeans_init()

static void kmeans_init ( POINT2D **  objs, uint32_t  n, POINT2D **  centers, POINT2D *  centers_raw, uint32_t  k  )

static

Definition at line 129 of file lwkmeans.c.

{
        double* distances;
        uint32_t p1 = 0, p2 = 0;
        uint32_t i, j;
        uint32_t duplicate_count = 1; /* a point is a duplicate of itself */
        double max_dst = -1, current_distance;
        double dst_p1, dst_p2;
 
        /* k=0, k=1: "clustering" is just input validation */
        assert(k > 1);
 
        /* k >= 2: find two distant points greedily */
        for (i = 1; i < n; i++)
        {
                /* skip null */
                if (!objs[i]) continue;
 
                /* reinit if first element happened to be null */
                if (!objs[p1] && !objs[p2])
                {
                        p1 = i;
                        p2 = i;
                        continue;
                }
 
                /* if we found a larger distance, replace our choice */
                dst_p1 = distance2d_sqr_pt_pt(objs[i], objs[p1]);
                dst_p2 = distance2d_sqr_pt_pt(objs[i], objs[p2]);
                if ((dst_p1 > max_dst) || (dst_p2 > max_dst))
                {
                        if (dst_p1 > dst_p2)
                        {
                                max_dst = dst_p1;
                                p2 = i;
                        }
                        else
                        {
                                max_dst = dst_p2;
                                p1 = i;
                        }
                }
                if ((dst_p1 == 0) || (dst_p2 == 0)) duplicate_count++;
        }
        if (duplicate_count > 1)
                lwnotice(
                    "%s: there are at least %u duplicate inputs, number of output clusters may be less than you requested",
                    __func__,
                    duplicate_count);
 
        /* by now two points should be found and non-same */
        assert(p1 != p2 && objs[p1] && objs[p2] && max_dst >= 0);
 
        /* accept these two points */
        centers_raw[0] = *((POINT2D *)objs[p1]);
        centers[0] = &(centers_raw[0]);
        centers_raw[1] = *((POINT2D *)objs[p2]);
        centers[1] = &(centers_raw[1]);
 
        if (k > 2)
        {
                /* array of minimum distance to a point from accepted cluster centers */
                distances = lwalloc(sizeof(double) * n);
 
                /* initialize array with distance to first object */
                for (j = 0; j < n; j++)
                {
                        if (objs[j])
                                distances[j] = distance2d_sqr_pt_pt(objs[j], centers[0]);
                        else
                                distances[j] = -1;
                }
                distances[p1] = -1;
                distances[p2] = -1;
 
                /* loop i on clusters, skip 0 and 1 as found already */
                for (i = 2; i < k; i++)
                {
                        uint32_t candidate_center = 0;
                        double max_distance = -DBL_MAX;
 
                        /* loop j on objs */
                        for (j = 0; j < n; j++)
                        {
                                /* empty objs and accepted clusters are already marked with distance = -1 */
                                if (distances[j] < 0) continue;
 
                                /* update minimal distance with previosuly accepted cluster */
                                current_distance = distance2d_sqr_pt_pt(objs[j], centers[i - 1]);
                                if (current_distance < distances[j])
                                        distances[j] = current_distance;
 
                                /* greedily take a point that's farthest from any of accepted clusters */
                                if (distances[j] > max_distance)
                                {
                                        candidate_center = j;
                                        max_distance = distances[j];
                                }
                        }
 
                        /* Checked earlier by counting entries on input, just in case */
                        assert(max_distance >= 0);
 
                        /* accept candidate to centers */
                        distances[candidate_center] = -1;
                        /* Copy the point coordinates into the initial centers array
                         * Centers array is an array of pointers to points, not an array of points */
                        centers_raw[i] = *((POINT2D *)objs[candidate_center]);
                        centers[i] = &(centers_raw[i]);
                }
                lwfree(distances);
        }
}

References distance2d_sqr_pt_pt(), lwalloc(), lwfree(), and lwnotice().

Referenced by lwgeom_cluster_2d_kmeans().

Here is the call graph for this function:

Here is the caller graph for this function: