PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ kmeans()

kmeans_result kmeans ( kmeans_config config)

Definition at line 249 of file kmeans.c.

References kmeans_config::centers, kmeans_config::centroid_method, kmeans_config::clusters, kmeans_config::distance_method, kmeans_config::k, KMEANS_ERROR, KMEANS_EXCEEDED_MAX_ITERATIONS, kmeans_free, kmeans_malloc, KMEANS_MAX_ITERATIONS, KMEANS_OK, LW_ON_INTERRUPT, kmeans_config::max_iterations, kmeans_config::num_objs, kmeans_config::objs, kmeans_config::total_iterations, update_means(), and update_r().

Referenced by lwgeom_cluster_2d_kmeans().

250 {
251  int iterations = 0;
252  int *clusters_last;
253  size_t clusters_sz = sizeof(int)*config->num_objs;
254 
255  assert(config);
256  assert(config->objs);
257  assert(config->num_objs);
258  assert(config->distance_method);
259  assert(config->centroid_method);
260  assert(config->centers);
261  assert(config->k);
262  assert(config->clusters);
263  assert(config->k <= config->num_objs);
264 
265  /* Zero out cluster numbers, just in case user forgets */
266  memset(config->clusters, 0, clusters_sz);
267 
268  /* Set default max iterations if necessary */
269  if (!config->max_iterations)
271 
272  /*
273  * Previous cluster state array. At this time, r doesn't mean anything
274  * but it's ok
275  */
276  clusters_last = kmeans_malloc(clusters_sz);
277 
278  while (1)
279  {
280  LW_ON_INTERRUPT(kmeans_free(clusters_last); return KMEANS_ERROR);
281 
282  /* Store the previous state of the clustering */
283  memcpy(clusters_last, config->clusters, clusters_sz);
284 
285 #ifdef KMEANS_THREADED
286  update_r_threaded(config);
287  update_means_threaded(config);
288 #else
289  update_r(config);
290  update_means(config);
291 #endif
292  /*
293  * if all the cluster numbers are unchanged since last time,
294  * we are at a stable solution, so we can stop here
295  */
296  if (memcmp(clusters_last, config->clusters, clusters_sz) == 0)
297  {
298  kmeans_free(clusters_last);
299  config->total_iterations = iterations;
300  return KMEANS_OK;
301  }
302 
303  if (iterations++ > config->max_iterations)
304  {
305  kmeans_free(clusters_last);
306  config->total_iterations = iterations;
308  }
309 
310  }
311 
312  kmeans_free(clusters_last);
313  config->total_iterations = iterations;
314  return KMEANS_ERROR;
315 }
int * clusters
Definition: kmeans.h:120
static void update_r(kmeans_config *config)
Definition: kmeans.c:24
#define LW_ON_INTERRUPT(x)
#define kmeans_free(ptr)
Definition: kmeans.h:57
#define kmeans_malloc(size)
Definition: kmeans.h:56
Pointer * centers
Definition: kmeans.h:107
unsigned int total_iterations
Definition: kmeans.h:117
unsigned int max_iterations
Definition: kmeans.h:114
size_t num_objs
Definition: kmeans.h:100
static void update_means(kmeans_config *config)
Definition: kmeans.c:72
unsigned int k
Definition: kmeans.h:110
Pointer * objs
Definition: kmeans.h:97
kmeans_distance_method distance_method
Definition: kmeans.h:85
kmeans_centroid_method centroid_method
Definition: kmeans.h:88
#define KMEANS_MAX_ITERATIONS
Definition: kmeans.h:43
Here is the call graph for this function:
Here is the caller graph for this function: