PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ union_dbscan_general()

static int union_dbscan_general ( LWGEOM **  geoms,
uint32_t  num_geoms,
UNIONFIND uf,
double  eps,
uint32_t  min_points,
char **  in_a_cluster_ret 
)
static

Definition at line 378 of file lwgeom_geos_cluster.c.

References dbscan_update_context(), destroy_strtree(), QueryContext::items_found, LW_FAILURE, LW_SUCCESS, LW_TRUE, lwalloc(), lwfree(), lwgeom_is_empty(), lwgeom_mindistance2d_tolerance(), make_strtree(), QueryContext::num_items_found, STRTree::tree, UF_find(), and union_if_available().

Referenced by union_dbscan().

379 {
380  uint32_t p, i;
381  struct STRTree tree;
382  struct QueryContext cxt =
383  {
384  .items_found = NULL,
385  .num_items_found = 0,
386  .items_found_size = 0
387  };
388  int success = LW_SUCCESS;
389  uint32_t* neighbors;
390  char* in_a_cluster;
391  char* is_in_core;
392 
393  in_a_cluster = lwalloc(num_geoms * sizeof(char));
394  memset(in_a_cluster, 0, num_geoms * sizeof(char));
395 
396  if (in_a_cluster_ret)
397  *in_a_cluster_ret = in_a_cluster;
398 
399  /* Bail if we don't even have enough inputs to make a cluster. */
400  if (num_geoms <= min_points)
401  {
402  if (!in_a_cluster_ret)
403  lwfree(in_a_cluster);
404  return LW_SUCCESS;
405  }
406 
407  tree = make_strtree((void**) geoms, num_geoms, LW_TRUE);
408  if (tree.tree == NULL)
409  {
410  destroy_strtree(&tree);
411  return LW_FAILURE;
412  }
413 
414  is_in_core = lwalloc(num_geoms * sizeof(char));
415  memset(is_in_core, 0, num_geoms * sizeof(char));
416  neighbors = lwalloc(min_points * sizeof(uint32_t));
417 
418  for (p = 0; p < num_geoms; p++)
419  {
420  uint32_t num_neighbors = 0;
421 
422  if (lwgeom_is_empty(geoms[p]))
423  continue;
424 
425  dbscan_update_context(tree.tree, &cxt, geoms, p, eps);
426 
427  /* We didn't find enough points to do anything, even if they are all within eps. */
428  if (cxt.num_items_found < min_points)
429  continue;
430 
431  for (i = 0; i < cxt.num_items_found; i++)
432  {
433  uint32_t q = *((uint32_t*) cxt.items_found[i]);
434 
435  if (num_neighbors >= min_points)
436  {
437  /* If we've already identified p as a core point, and it's already
438  * in the same cluster in q, then there's nothing to learn by
439  * computing the distance.
440  */
441  if (UF_find(uf, p) == UF_find(uf, q))
442  continue;
443 
444  /* Similarly, if q is already identifed as a border point of another
445  * cluster, there's no point figuring out what the distance is.
446  */
447  if (in_a_cluster[q] && !is_in_core[q])
448  continue;
449  }
450 
451  double mindist = lwgeom_mindistance2d_tolerance(geoms[p], geoms[q], eps);
452  if (mindist == FLT_MAX)
453  {
454  success = LW_FAILURE;
455  break;
456  }
457 
458  if (mindist <= eps)
459  {
460  /* If we haven't hit min_points yet, we don't know if we can union p and q.
461  * Just set q aside for now.
462  */
463  if (num_neighbors < min_points)
464  {
465  neighbors[num_neighbors++] = q;
466 
467  /* If we just hit min_points, we can now union all of the neighbor geometries
468  * we've been saving.
469  */
470  if (num_neighbors == min_points)
471  {
472  uint32_t j;
473  is_in_core[p] = LW_TRUE;
474  in_a_cluster[p] = LW_TRUE;
475  for (j = 0; j < num_neighbors; j++)
476  {
477  union_if_available(uf, p, neighbors[j], is_in_core, in_a_cluster);
478  }
479  }
480  }
481  else
482  {
483  /* If we're above min_points, no need to store our neighbors, just go ahead
484  * and union them now. This may allow us to cut out some distance
485  * computations.
486  */
487  union_if_available(uf, p, q, is_in_core, in_a_cluster);
488  }
489  }
490  }
491 
492  if (!success)
493  break;
494  }
495 
496  lwfree(neighbors);
497  lwfree(is_in_core);
498 
499  /* Free in_a_cluster if we're not giving it to our caller */
500  if (!in_a_cluster_ret)
501  lwfree(in_a_cluster);
502 
503  if (cxt.items_found)
504  lwfree(cxt.items_found);
505 
506  destroy_strtree(&tree);
507  return success;
508 }
uint32_t num_items_found
void lwfree(void *mem)
Definition: lwutil.c:244
double lwgeom_mindistance2d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance)
Function handling min distance calculations and dwithin calculations.
Definition: measures.c:213
#define LW_SUCCESS
Definition: liblwgeom.h:79
GEOSSTRtree * tree
#define LW_FAILURE
Definition: liblwgeom.h:78
unsigned int uint32_t
Definition: uthash.h:78
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:61
static struct STRTree make_strtree(void **geoms, uint32_t num_geoms, char is_lwgeom)
Make a GEOSSTRtree that stores a pointer to a variable containing the array index of the input geoms...
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
static void union_if_available(UNIONFIND *uf, uint32_t p, uint32_t q, char *is_in_core, char *in_a_cluster)
static void destroy_strtree(struct STRTree *tree)
Clean up STRTree after use.
static int dbscan_update_context(GEOSSTRtree *tree, struct QueryContext *cxt, LWGEOM **geoms, uint32_t p, double eps)
void * lwalloc(size_t size)
Definition: lwutil.c:229
int lwgeom_is_empty(const LWGEOM *geom)
Return true or false depending on whether a geometry is an "empty" geometry (no vertices members) ...
Definition: lwgeom.c:1393
Here is the call graph for this function:
Here is the caller graph for this function: