PostGIS  2.3.8dev-r@@SVN_REVISION@@
lwgeom_geos_cluster.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright 2015-2016 Daniel Baston <dbaston@gmail.com>
22  *
23  **********************************************************************/
24 
25 #include <string.h>
26 #include "liblwgeom.h"
27 #include "liblwgeom_internal.h"
28 #include "lwgeom_log.h"
29 #include "lwgeom_geos.h"
30 #include "lwunionfind.h"
31 
32 static const int STRTREE_NODE_CAPACITY = 10;
33 
34 /* Utility struct used to accumulate items in GEOSSTRtree_query callback */
36 {
37  void** items_found;
38  uint32_t items_found_size;
39  uint32_t num_items_found;
40 };
41 
42 /* Utility struct to keep GEOSSTRtree and associated structures to be freed after use */
43 struct STRTree
44 {
45  GEOSSTRtree* tree;
46  GEOSGeometry** envelopes;
47  uint32_t* geom_ids;
48  uint32_t num_geoms;
49 };
50 
51 static struct STRTree make_strtree(void** geoms, uint32_t num_geoms, char is_lwgeom);
52 static void destroy_strtree(struct STRTree * tree);
53 static int union_intersecting_pairs(GEOSGeometry** geoms, uint32_t num_geoms, UNIONFIND* uf);
54 static int combine_geometries(UNIONFIND* uf, void** geoms, uint32_t num_geoms, void*** clustersGeoms, uint32_t* num_clusters, char is_lwgeom);
55 
56 /* Make a minimal GEOSGeometry* whose Envelope covers the same 2D extent as
57  * the supplied GBOX. This is faster and uses less memory than building a
58  * five-point polygon with GBOX2GEOS.
59  */
60 static GEOSGeometry*
62 {
63  if (lwgeom_is_empty(g))
64  return GEOSGeom_createEmptyPolygon();
65 
66  if (lwgeom_get_type(g) == POINTTYPE) {
67  const POINT2D* pt = getPoint2d_cp(lwgeom_as_lwpoint(g)->point, 0);
68  return make_geos_point(pt->x, pt->y);
69  } else {
70  const GBOX* box = lwgeom_get_bbox(g);
71  if (!box)
72  return NULL;
73 
74  return make_geos_segment(box->xmin, box->ymin, box->xmax, box->ymax);
75  }
76 }
77 
80 static struct STRTree
81 make_strtree(void** geoms, uint32_t num_geoms, char is_lwgeom)
82 {
83  struct STRTree tree;
84  tree.tree = GEOSSTRtree_create(STRTREE_NODE_CAPACITY);
85  if (tree.tree == NULL)
86  {
87  return tree;
88  }
89  tree.geom_ids = lwalloc(num_geoms * sizeof(uint32_t));
90  tree.num_geoms = num_geoms;
91 
92  if (is_lwgeom)
93  {
94  uint32_t i;
95  tree.envelopes = lwalloc(num_geoms * sizeof(GEOSGeometry*));
96  for (i = 0; i < num_geoms; i++)
97  {
98  tree.geom_ids[i] = i;
99  tree.envelopes[i] = geos_envelope_surrogate(geoms[i]);
100  GEOSSTRtree_insert(tree.tree, tree.envelopes[i], &(tree.geom_ids[i]));
101  }
102  }
103  else
104  {
105  uint32_t i;
106  tree.envelopes = NULL;
107  for (i = 0; i < num_geoms; i++)
108  {
109  tree.geom_ids[i] = i;
110  GEOSSTRtree_insert(tree.tree, geoms[i], &(tree.geom_ids[i]));
111  }
112  }
113 
114  return tree;
115 }
116 
118 static void
120 {
121  size_t i;
122  GEOSSTRtree_destroy(tree->tree);
123 
124  if (tree->envelopes)
125  {
126  for (i = 0; i < tree->num_geoms; i++)
127  {
128  GEOSGeom_destroy(tree->envelopes[i]);
129  }
130  lwfree(tree->envelopes);
131  }
132  lwfree(tree->geom_ids);
133 }
134 
135 static void
136 query_accumulate(void* item, void* userdata)
137 {
138  struct QueryContext *cxt = userdata;
139  if (!cxt->items_found)
140  {
141  cxt->items_found_size = 8;
142  cxt->items_found = lwalloc(cxt->items_found_size * sizeof(void*));
143  }
144 
145  if (cxt->num_items_found >= cxt->items_found_size)
146  {
147  cxt->items_found_size = 2 * cxt->items_found_size;
148  cxt->items_found = lwrealloc(cxt->items_found, cxt->items_found_size * sizeof(void*));
149  }
150  cxt->items_found[cxt->num_items_found++] = item;
151 }
152 
153 /* Identify intersecting geometries and mark them as being in the same set */
154 static int
155 union_intersecting_pairs(GEOSGeometry** geoms, uint32_t num_geoms, UNIONFIND* uf)
156 {
157  uint32_t p, i;
158  struct STRTree tree;
159  struct QueryContext cxt =
160  {
161  .items_found = NULL,
162  .num_items_found = 0,
163  .items_found_size = 0
164  };
165  int success = LW_SUCCESS;
166 
167  if (num_geoms <= 1)
168  return LW_SUCCESS;
169 
170  tree = make_strtree((void**) geoms, num_geoms, LW_FALSE);
171  if (tree.tree == NULL)
172  {
173  destroy_strtree(&tree);
174  return LW_FAILURE;
175  }
176 
177  for (p = 0; p < num_geoms; p++)
178  {
179  const GEOSPreparedGeometry* prep = NULL;
180 
181  if (GEOSisEmpty(geoms[p]))
182  continue;
183 
184  cxt.num_items_found = 0;
185  GEOSSTRtree_query(tree.tree, geoms[p], &query_accumulate, &cxt);
186 
187  for (i = 0; i < cxt.num_items_found; i++)
188  {
189  uint32_t q = *((uint32_t*) cxt.items_found[i]);
190 
191  if (p != q && UF_find(uf, p) != UF_find(uf, q))
192  {
193  int geos_type = GEOSGeomTypeId(geoms[p]);
194  int geos_result;
195 
196  /* Don't build prepared a geometry around a Point or MultiPoint -
197  * there are some problems in the implementation, and it's not clear
198  * there would be a performance benefit in any case. (See #3433)
199  */
200  if (geos_type != GEOS_POINT && geos_type != GEOS_MULTIPOINT)
201  {
202  /* Lazy initialize prepared geometry */
203  if (prep == NULL)
204  {
205  prep = GEOSPrepare(geoms[p]);
206  }
207  geos_result = GEOSPreparedIntersects(prep, geoms[q]);
208  }
209  else
210  {
211  geos_result = GEOSIntersects(geoms[p], geoms[q]);
212  }
213  if (geos_result > 1)
214  {
215  success = LW_FAILURE;
216  break;
217  }
218  else if (geos_result)
219  {
220  UF_union(uf, p, q);
221  }
222  }
223  }
224 
225  if (prep)
226  GEOSPreparedGeom_destroy(prep);
227 
228  if (!success)
229  break;
230  }
231 
232  if (cxt.items_found)
233  lwfree(cxt.items_found);
234 
235  destroy_strtree(&tree);
236  return success;
237 }
238 
242 int
243 cluster_intersecting(GEOSGeometry** geoms, uint32_t num_geoms, GEOSGeometry*** clusterGeoms, uint32_t* num_clusters)
244 {
245  int cluster_success;
246  UNIONFIND* uf = UF_create(num_geoms);
247 
248  if (union_intersecting_pairs(geoms, num_geoms, uf) == LW_FAILURE)
249  {
250  UF_destroy(uf);
251  return LW_FAILURE;
252  }
253 
254  cluster_success = combine_geometries(uf, (void**) geoms, num_geoms, (void***) clusterGeoms, num_clusters, 0);
255  UF_destroy(uf);
256  return cluster_success;
257 }
258 
259 static int
260 dbscan_update_context(GEOSSTRtree* tree, struct QueryContext* cxt, LWGEOM** geoms, uint32_t p, double eps)
261 {
262  cxt->num_items_found = 0;
263 
264  GEOSGeometry* query_envelope;
265  if (geoms[p]->type == POINTTYPE)
266  {
267  const POINT2D* pt = getPoint2d_cp(lwgeom_as_lwpoint(geoms[p])->point, 0);
268  query_envelope = make_geos_segment( pt->x - eps, pt->y - eps, pt->x + eps, pt->y + eps );
269  } else {
270  const GBOX* box = lwgeom_get_bbox(geoms[p]);
271  query_envelope = make_geos_segment( box->xmin - eps, box->ymin - eps, box->xmax + eps, box->ymax + eps );
272  }
273 
274  if (!query_envelope)
275  return LW_FAILURE;
276 
277  GEOSSTRtree_query(tree, query_envelope, &query_accumulate, cxt);
278 
279  GEOSGeom_destroy(query_envelope);
280 
281  return LW_SUCCESS;
282 }
283 
284 /* Union p's cluster with q's cluster, if q is not a border point of another cluster.
285  * Applicable to DBSCAN with minpoints > 1.
286  */
287 static void
288 union_if_available(UNIONFIND* uf, uint32_t p, uint32_t q, char* is_in_core, char* in_a_cluster)
289 {
290  if (in_a_cluster[q])
291  {
292  /* Can we merge p's cluster with q's cluster? We can do this only
293  * if both p and q are considered _core_ points of their respective
294  * clusters.
295  */
296  if (is_in_core[q])
297  {
298  UF_union(uf, p, q);
299  }
300  }
301  else
302  {
303  UF_union(uf, p, q);
304  in_a_cluster[q] = LW_TRUE;
305  }
306 }
307 
308 /* An optimized DBSCAN union for the case where min_points == 1.
309  * If min_points == 1, then we don't care how many neighbors we find; we can union clusters
310  * on the fly, as as we go through the distance calculations. This potentially allows us
311  * to avoid some distance computations altogether.
312  */
313 static int
314 union_dbscan_minpoints_1(LWGEOM** geoms, uint32_t num_geoms, UNIONFIND* uf, double eps, char** in_a_cluster_ret)
315 {
316  uint32_t p, i;
317  struct STRTree tree;
318  struct QueryContext cxt =
319  {
320  .items_found = NULL,
321  .num_items_found = 0,
322  .items_found_size = 0
323  };
324  int success = LW_SUCCESS;
325 
326  if (in_a_cluster_ret)
327  {
328  char* in_a_cluster = lwalloc(num_geoms * sizeof(char));
329  for (i = 0; i < num_geoms; i++)
330  in_a_cluster[i] = LW_TRUE;
331  *in_a_cluster_ret = in_a_cluster;
332  }
333 
334  if (num_geoms <= 1)
335  return LW_SUCCESS;
336 
337  tree = make_strtree((void**) geoms, num_geoms, LW_TRUE);
338  if (tree.tree == NULL)
339  {
340  destroy_strtree(&tree);
341  return LW_FAILURE;
342  }
343 
344  for (p = 0; p < num_geoms; p++)
345  {
346  if (lwgeom_is_empty(geoms[p]))
347  continue;
348 
349  dbscan_update_context(tree.tree, &cxt, geoms, p, eps);
350  for (i = 0; i < cxt.num_items_found; i++)
351  {
352  uint32_t q = *((uint32_t*) cxt.items_found[i]);
353 
354  if (UF_find(uf, p) != UF_find(uf, q))
355  {
356  double mindist = lwgeom_mindistance2d_tolerance(geoms[p], geoms[q], eps);
357  if (mindist == FLT_MAX)
358  {
359  success = LW_FAILURE;
360  break;
361  }
362 
363  if (mindist <= eps)
364  UF_union(uf, p, q);
365  }
366  }
367  }
368 
369  if (cxt.items_found)
370  lwfree(cxt.items_found);
371 
372  destroy_strtree(&tree);
373 
374  return success;
375 }
376 
377 static int
378 union_dbscan_general(LWGEOM** geoms, uint32_t num_geoms, UNIONFIND* uf, double eps, uint32_t min_points, char** in_a_cluster_ret)
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 }
509 
510 int union_dbscan(LWGEOM** geoms, uint32_t num_geoms, UNIONFIND* uf, double eps, uint32_t min_points, char** in_a_cluster_ret)
511 {
512  if (min_points <= 1)
513  return union_dbscan_minpoints_1(geoms, num_geoms, uf, eps, in_a_cluster_ret);
514  else
515  return union_dbscan_general(geoms, num_geoms, uf, eps, min_points, in_a_cluster_ret);
516 }
517 
521 int
522 cluster_within_distance(LWGEOM** geoms, uint32_t num_geoms, double tolerance, LWGEOM*** clusterGeoms, uint32_t* num_clusters)
523 {
524  int cluster_success;
525  UNIONFIND* uf = UF_create(num_geoms);
526 
527  if (union_dbscan(geoms, num_geoms, uf, tolerance, 1, NULL) == LW_FAILURE)
528  {
529  UF_destroy(uf);
530  return LW_FAILURE;
531  }
532 
533  cluster_success = combine_geometries(uf, (void**) geoms, num_geoms, (void***) clusterGeoms, num_clusters, 1);
534  UF_destroy(uf);
535  return cluster_success;
536 }
537 
541 static int
542 combine_geometries(UNIONFIND* uf, void** geoms, uint32_t num_geoms, void*** clusterGeoms, uint32_t* num_clusters, char is_lwgeom)
543 {
544  size_t i, j, k;
545 
546  /* Combine components of each cluster into their own GeometryCollection */
547  *num_clusters = uf->num_clusters;
548  *clusterGeoms = lwalloc(*num_clusters * sizeof(void*));
549 
550  void** geoms_in_cluster = lwalloc(num_geoms * sizeof(void*));
551  uint32_t* ordered_components = UF_ordered_by_cluster(uf);
552  for (i = 0, j = 0, k = 0; i < num_geoms; i++)
553  {
554  geoms_in_cluster[j++] = geoms[ordered_components[i]];
555 
556  /* Is this the last geometry in the component? */
557  if ((i == num_geoms - 1) ||
558  (UF_find(uf, ordered_components[i]) != UF_find(uf, ordered_components[i+1])))
559  {
560  if (k >= uf->num_clusters) {
561  /* Should not get here - it means that we have more clusters than uf->num_clusters thinks we should. */
562  return LW_FAILURE;
563  }
564 
565  if (is_lwgeom)
566  {
567  LWGEOM** components = lwalloc(j * sizeof(LWGEOM*));
568  memcpy(components, geoms_in_cluster, j * sizeof(LWGEOM*));
569  (*clusterGeoms)[k++] = lwcollection_construct(COLLECTIONTYPE, components[0]->srid, NULL, j, (LWGEOM**) components);
570  }
571  else
572  {
573  int srid = GEOSGetSRID(((GEOSGeometry**) geoms_in_cluster)[0]);
574  GEOSGeometry* combined = GEOSGeom_createCollection(GEOS_GEOMETRYCOLLECTION, (GEOSGeometry**) geoms_in_cluster, j);
575  GEOSSetSRID(combined, srid);
576  (*clusterGeoms)[k++] = combined;
577  }
578  j = 0;
579  }
580  }
581 
582  lwfree(geoms_in_cluster);
583  lwfree(ordered_components);
584 
585  return LW_SUCCESS;
586 }
uint32_t num_items_found
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:53
GEOSGeometry * make_geos_segment(double x1, double y1, double x2, double y2)
static void query_accumulate(void *item, void *userdata)
GEOSGeometry ** envelopes
LWCOLLECTION * lwcollection_construct(uint8_t type, int srid, GBOX *bbox, uint32_t ngeoms, LWGEOM **geoms)
Definition: lwcollection.c:43
void lwfree(void *mem)
Definition: lwutil.c:242
double lwgeom_mindistance2d_tolerance(const LWGEOM *lw1, const LWGEOM *lw2, double tolerance)
Function handling min distance calculations and dwithin calculations.
Definition: measures.c:213
uint32_t lwgeom_get_type(const LWGEOM *geom)
Return LWTYPE number.
Definition: lwgeom.c:842
double xmax
Definition: liblwgeom.h:292
#define LW_SUCCESS
Definition: liblwgeom.h:79
uint32_t items_found_size
static int union_dbscan_general(LWGEOM **geoms, uint32_t num_geoms, UNIONFIND *uf, double eps, uint32_t min_points, char **in_a_cluster_ret)
GEOSSTRtree * tree
int cluster_intersecting(GEOSGeometry **geoms, uint32_t num_geoms, GEOSGeometry ***clusterGeoms, uint32_t *num_clusters)
Takes an array of GEOSGeometry* and constructs an array of GEOSGeometry*, where each element in the c...
LWPOINT * lwgeom_as_lwpoint(const LWGEOM *lwgeom)
Definition: lwgeom.c:93
GEOSGeometry * make_geos_point(double x, double y)
#define LW_FAILURE
Definition: liblwgeom.h:78
static const int STRTREE_NODE_CAPACITY
double x
Definition: liblwgeom.h:327
static int union_dbscan_minpoints_1(LWGEOM **geoms, uint32_t num_geoms, UNIONFIND *uf, double eps, char **in_a_cluster_ret)
double ymin
Definition: liblwgeom.h:293
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:61
double xmin
Definition: liblwgeom.h:291
#define LW_FALSE
Definition: liblwgeom.h:76
const POINT2D * getPoint2d_cp(const POINTARRAY *pa, int n)
Returns a POINT2D pointer into the POINTARRAY serialized_ptlist, suitable for reading from...
Definition: lwgeom_api.c:485
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...
int cluster_within_distance(LWGEOM **geoms, uint32_t num_geoms, double tolerance, LWGEOM ***clusterGeoms, uint32_t *num_clusters)
Takes an array of LWGEOM* and constructs an array of LWGEOM*, where each element in the constructed a...
uint32_t * UF_ordered_by_cluster(UNIONFIND *uf)
Definition: lwunionfind.c:112
#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)
const GBOX * lwgeom_get_bbox(const LWGEOM *lwgeom)
Get a non-empty geometry bounding box, computing and caching it if not already there.
Definition: lwgeom.c:653
uint32_t * geom_ids
double ymax
Definition: liblwgeom.h:294
static void destroy_strtree(struct STRTree *tree)
Clean up STRTree after use.
double y
Definition: liblwgeom.h:327
uint32_t num_clusters
Definition: lwunionfind.h:35
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:34
void * lwrealloc(void *mem, size_t size)
Definition: lwutil.c:235
#define POINTTYPE
LWTYPE numbers, used internally by PostGIS.
Definition: liblwgeom.h:84
static int dbscan_update_context(GEOSSTRtree *tree, struct QueryContext *cxt, LWGEOM **geoms, uint32_t p, double eps)
type
Definition: ovdump.py:41
void UF_union(UNIONFIND *uf, uint32_t i, uint32_t j)
Definition: lwunionfind.c:84
void * lwalloc(size_t size)
Definition: lwutil.c:227
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:1310
uint32_t num_geoms
static int combine_geometries(UNIONFIND *uf, void **geoms, uint32_t num_geoms, void ***clustersGeoms, uint32_t *num_clusters, char is_lwgeom)
Uses a UNIONFIND to identify the set with which each input geometry is associated, and groups the geometries into GeometryCollections.
static int union_intersecting_pairs(GEOSGeometry **geoms, uint32_t num_geoms, UNIONFIND *uf)
static GEOSGeometry * geos_envelope_surrogate(const LWGEOM *g)
#define COLLECTIONTYPE
Definition: liblwgeom.h:90
This library is the generic geometry handling section of PostGIS.
int union_dbscan(LWGEOM **geoms, uint32_t num_geoms, UNIONFIND *uf, double eps, uint32_t min_points, char **in_a_cluster_ret)