PostGIS  2.5.7dev-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 382 of file lwgeom_geos_cluster.c.

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

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().

Here is the call graph for this function:
Here is the caller graph for this function: