PostGIS  2.5.7dev-r@@SVN_REVISION@@
cu_geos_cluster.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * Copyright 2015 Daniel Baston
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU General Public Licence. See the COPYING file.
10  *
11  **********************************************************************/
12 
13 #include "CUnit/Basic.h"
14 
15 #include "../lwgeom_log.h"
16 #include "../lwgeom_geos.h"
17 #include "cu_tester.h"
18 
19 static void assert_all_results_found(LWGEOM** results, size_t num_outputs, LWGEOM** expected, size_t num_expected_outputs)
20 {
21  size_t i, j;
22 
23  char found_equal = 0;
24  for (i = 0; i < num_outputs; i++)
25  {
26  for (j = 0; j < num_expected_outputs; j++)
27  {
28  if (lwgeom_same(results[i], expected[j]))
29  {
30  found_equal = 1;
31  break;
32  }
33  }
34 
35  CU_ASSERT_TRUE(found_equal);
36  }
37 }
38 
39 static GEOSGeometry** LWGEOMARRAY2GEOS(LWGEOM** lw_array, size_t num_geoms)
40 {
41  size_t i;
42  GEOSGeometry** geos_geoms = lwalloc(num_geoms * sizeof(GEOSGeometry*));
43 
44  for (i = 0; i < num_geoms; i++)
45  {
46  geos_geoms[i] = LWGEOM2GEOS(lw_array[i], 0);
47  }
48 
49  return geos_geoms;
50 }
51 
52 static LWGEOM** GEOSARRAY2LWGEOM(GEOSGeometry** geos_array, size_t num_geoms)
53 {
54  size_t i;
55  LWGEOM** lw_geoms = lwalloc(num_geoms * sizeof(LWGEOM*));
56 
57  for (i = 0; i < num_geoms; i++)
58  {
59  lw_geoms[i] = GEOS2LWGEOM(geos_array[i], 0);
60  }
61 
62  return lw_geoms;
63 }
64 
65 static LWGEOM** WKTARRAY2LWGEOM(char** wkt_array, size_t num_geoms)
66 {
67  size_t i;
68 
69  LWGEOM** lw_geoms = lwalloc(num_geoms * sizeof(LWGEOM*));
70 
71  for (i = 0; i < num_geoms; i++)
72  {
73  lw_geoms[i] = lwgeom_from_wkt(wkt_array[i], LW_PARSER_CHECK_NONE);
74  }
75 
76  return lw_geoms;
77 }
78 
79 static void perform_cluster_intersecting_test(char** wkt_inputs, uint32_t num_inputs, char** wkt_outputs, uint32_t num_outputs)
80 {
81  GEOSGeometry** geos_results;
82  LWGEOM** lw_results;
83  uint32_t num_clusters;
84 
85  LWGEOM** expected_outputs = WKTARRAY2LWGEOM(wkt_outputs, num_outputs);
86  LWGEOM** lw_inputs = WKTARRAY2LWGEOM(wkt_inputs, num_inputs);
87  GEOSGeometry** geos_inputs = LWGEOMARRAY2GEOS(lw_inputs, num_inputs);
88 
89  cluster_intersecting(geos_inputs, num_inputs, &geos_results, &num_clusters);
90  CU_ASSERT_EQUAL(num_outputs, num_clusters);
91 
92  lw_results = GEOSARRAY2LWGEOM(geos_results, num_clusters);
93 
94  assert_all_results_found(lw_results, num_clusters, expected_outputs, num_outputs);
95 
96  /* Cleanup */
97  uint32_t i;
98  for(i = 0; i < num_clusters; i++)
99  {
100  GEOSGeom_destroy(geos_results[i]);
101  }
102  lwfree(geos_inputs);
103  lwfree(geos_results);
104 
105  for(i = 0; i < num_outputs; i++)
106  {
107  lwgeom_free(expected_outputs[i]);
108  lwgeom_free(lw_results[i]);
109  }
110  lwfree(expected_outputs);
111  lwfree(lw_results);
112 
113  for(i = 0; i < num_inputs; i++)
114  {
115  lwgeom_free(lw_inputs[i]);
116  }
117  lwfree(lw_inputs);
118 }
119 
120 static void perform_cluster_within_distance_test(double tolerance, char** wkt_inputs, uint32_t num_inputs, char** wkt_outputs, uint32_t num_outputs)
121 {
122  LWGEOM** lw_results;
123  uint32_t num_clusters;
124 
125  LWGEOM** expected_outputs = WKTARRAY2LWGEOM(wkt_outputs, num_outputs);
126  LWGEOM** lw_inputs = WKTARRAY2LWGEOM(wkt_inputs, num_inputs);
127 
128  cluster_within_distance(lw_inputs, num_inputs, tolerance, &lw_results, &num_clusters);
129 
130  CU_ASSERT_EQUAL(num_outputs, num_clusters);
131 
132  assert_all_results_found(lw_results, num_clusters, expected_outputs, num_outputs);
133 
134  /* Cleanup */
135  uint32_t i;
136  for(i = 0; i < num_outputs; i++)
137  {
138  lwgeom_free(expected_outputs[i]);
139  lwgeom_free(lw_results[i]);
140  }
141  lwfree(lw_results);
142  lwfree(expected_outputs);
143  lwfree(lw_inputs);
144 }
145 
146 static int init_geos_cluster_suite(void)
147 {
148  initGEOS(lwnotice, lwgeom_geos_error);
149  return 0;
150 }
151 
152 static int clean_geos_cluster_suite(void)
153 {
154  finishGEOS();
155  return 0;
156 }
157 
158 static void basic_test(void)
159 {
160  char* a = "LINESTRING (0 0, 1 1)";
161  char* b = "LINESTRING (1 1, 2 2)";
162  char* c = "LINESTRING (5 5, 6 6)";
163 
164  char* wkt_inputs_a[] = {a, b, c};
165  char* wkt_inputs_b[] = {b, c, a};
166  char* wkt_inputs_c[] = {c, a, b};
167 
168  char* expected_outputs_a[] = { "GEOMETRYCOLLECTION(LINESTRING (0 0, 1 1), LINESTRING (1 1, 2 2))",
169  "GEOMETRYCOLLECTION(LINESTRING (5 5, 6 6))"
170  };
171 
172  char* expected_outputs_b[] = { "GEOMETRYCOLLECTION(LINESTRING (1 1, 2 2), LINESTRING (0 0, 1 1))",
173  "GEOMETRYCOLLECTION(LINESTRING (5 5, 6 6))"
174  };
175 
176  char* expected_outputs_c[] = { "GEOMETRYCOLLECTION(LINESTRING (0 0, 1 1), LINESTRING (1 1, 2 2))",
177  "GEOMETRYCOLLECTION(LINESTRING (5 5, 6 6))"
178  };
179 
180  perform_cluster_intersecting_test(wkt_inputs_a, 3, expected_outputs_a, 2);
181  perform_cluster_intersecting_test(wkt_inputs_b, 3, expected_outputs_b, 2);
182  perform_cluster_intersecting_test(wkt_inputs_c, 3, expected_outputs_c, 2);
183 
184  perform_cluster_within_distance_test(0, wkt_inputs_a, 3, expected_outputs_a, 2);
185  perform_cluster_within_distance_test(0, wkt_inputs_b, 3, expected_outputs_b, 2);
186  perform_cluster_within_distance_test(0, wkt_inputs_c, 3, expected_outputs_c, 2);
187 }
188 
189 static void basic_distance_test(void)
190 {
191  char* a = "LINESTRING (0 0, 1 1)";
192  char* b = "LINESTRING (1 1, 2 2)";
193  char* c = "LINESTRING (5 5, 6 6)";
194 
195  char* wkt_inputs[] = {a, b, c};
196 
197  char* expected_outputs_all[] = {"GEOMETRYCOLLECTION(LINESTRING(0 0, 1 1), LINESTRING(1 1, 2 2), LINESTRING(5 5, 6 6))"};
198  char* expected_outputs_partial[] = {"GEOMETRYCOLLECTION(LINESTRING(0 0, 1 1), LINESTRING(1 1, 2 2))",
199  "GEOMETRYCOLLECTION(LINESTRING(5 5, 6 6))"
200  };
201 
202  perform_cluster_within_distance_test(0, wkt_inputs, 3, expected_outputs_partial, 2);
203  perform_cluster_within_distance_test(sqrt(18) - 0.0000001, wkt_inputs, 3, expected_outputs_partial, 2);
204  perform_cluster_within_distance_test(sqrt(18) + 0.0000001, wkt_inputs, 3, expected_outputs_all, 1);
205 }
206 
207 static void nonsequential_test(void)
208 {
209  char* wkt_inputs[] = { "LINESTRING (0 0, 1 1)",
210  "LINESTRING (1 1, 2 2)",
211  "LINESTRING (5 5, 6 6)",
212  "LINESTRING (5 5, 4 4)",
213  "LINESTRING (3 3, 2 2)",
214  "LINESTRING (3 3, 4 4)"
215  };
216 
217  char* expected_outputs[] = { "GEOMETRYCOLLECTION (LINESTRING (0 0, 1 1), LINESTRING (1 1, 2 2), LINESTRING (5 5, 6 6), LINESTRING (5 5, 4 4), LINESTRING (3 3, 2 2), LINESTRING (3 3, 4 4))" };
218 
219  perform_cluster_intersecting_test(wkt_inputs, 6, expected_outputs, 1);
220  perform_cluster_within_distance_test(0, wkt_inputs, 6, expected_outputs, 1);
221 }
222 
223 static void single_input_test(void)
224 {
225  char* wkt_inputs[] = { "POINT (0 0)" };
226  char* expected_outputs[] = { "GEOMETRYCOLLECTION (POINT (0 0))" };
227 
228  perform_cluster_intersecting_test(wkt_inputs, 1, expected_outputs, 1);
229  perform_cluster_within_distance_test(1, wkt_inputs, 1, expected_outputs, 1);
230 }
231 
232 static void empty_inputs_test(void)
233 {
234  char* wkt_inputs[] = { "POLYGON EMPTY", "LINESTRING EMPTY"};
235  char* expected_outputs[] = { "GEOMETRYCOLLECTION( LINESTRING EMPTY )", "GEOMETRYCOLLECTION( POLYGON EMPTY )" };
236 
237  perform_cluster_intersecting_test(wkt_inputs, 2, expected_outputs, 2);
238  perform_cluster_within_distance_test(1, wkt_inputs, 2, expected_outputs, 2);
239 }
240 
241 static void multipoint_test(void)
242 {
243  /* See #3433 */
244  char* wkt_inputs_mp[] = { "MULTIPOINT ((0 0), (0 1))", "POINT (0 0)"};
245  char* expected_outputs_mp[] = { "GEOMETRYCOLLECTION(MULTIPOINT ((0 0), (0 1)), POINT (0 0))"};
246 
247  char* wkt_inputs_gc[] = { "GEOMETRYCOLLECTION (POINT (0 0), POINT (0 1))", "POINT (0 0)"};
248  char* expected_outputs_gc[] = { "GEOMETRYCOLLECTION(GEOMETRYCOLLECTION (POINT (0 0), POINT (0 1)), POINT (0 0))"};
249 
250  char* wkt_inputs_pt[] = { "POINT (3 3)", "POINT (3 3)"};
251  char* expected_outputs_pt[] = { "GEOMETRYCOLLECTION(POINT (3 3), POINT (3 3))"};
252 
253  perform_cluster_intersecting_test(wkt_inputs_mp, 2, expected_outputs_mp, 1);
254  perform_cluster_intersecting_test(wkt_inputs_gc, 2, expected_outputs_gc, 1);
255  perform_cluster_intersecting_test(wkt_inputs_pt, 2, expected_outputs_pt, 1);
256 }
257 
259  double eps;
262  char** wkt_inputs;
265 };
266 
267 static void do_dbscan_test(struct dbscan_test_info test)
268 {
269  LWGEOM** geoms = WKTARRAY2LWGEOM(test.wkt_inputs, test.num_geoms);
270  UNIONFIND* uf = UF_create(test.num_geoms);
271  uint32_t* ids;
272  char* in_a_cluster;
273  uint32_t i;
274 
275  union_dbscan(geoms, test.num_geoms, uf, test.eps, test.min_points, &in_a_cluster);
276  ids = UF_get_collapsed_cluster_ids(uf, in_a_cluster);
277 
278  for (i = 0; i < test.num_geoms; i++)
279  {
280  ASSERT_INT_EQUAL(in_a_cluster[i], test.expected_in_cluster[i]);
281  if (in_a_cluster[i])
282  ASSERT_INT_EQUAL(ids[i], test.expected_ids[i]);
283  }
284 
285  UF_destroy(uf);
286  for (i = 0; i < test.num_geoms; i++)
287  {
288  lwgeom_free(geoms[i]);
289  }
290  lwfree(geoms);
291  lwfree(in_a_cluster);
292  lwfree(ids);
293 }
294 
295 static void dbscan_test(void)
296 {
297  struct dbscan_test_info test;
298  char* wkt_inputs[] = { "POINT (0 0)", "POINT (-1 0)", "POINT (-1 -0.1)", "POINT (-1 0.1)",
299  "POINT (1 0)",
300  "POINT (2 0)", "POINT (3 0)", "POINT ( 3 -0.1)", "POINT ( 3 0.1)" };
301  /* Although POINT (1 0) and POINT (2 0) are within eps distance of each other,
302  * they do not connect the two clusters because POINT (1 0) is not a core point.
303  * See #3572
304  */
305  test.eps = 1.01;
306  test.min_points = 5;
307  uint32_t expected_ids[] = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 };
308  int expected_in_cluster[] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
309  test.num_geoms = sizeof(wkt_inputs) / sizeof(char*);
310 
311  test.expected_ids = expected_ids;
312  test.wkt_inputs = wkt_inputs;
314  do_dbscan_test(test);
315 }
316 
317 static void dbscan_test_3612a(void)
318 {
319  struct dbscan_test_info test;
320  char* wkt_inputs[] = { "POINT (1 1)" };
321 
322  test.eps = 0.0;
323  test.min_points = 5;
324  uint32_t expected_ids[] = { rand() };
325  int expected_in_cluster[] = { 0 };
326  test.num_geoms = sizeof(wkt_inputs) / sizeof(char*);
327 
328  test.expected_ids = expected_ids;
330  test.wkt_inputs = wkt_inputs;
331  do_dbscan_test(test);
332 }
333 
334 static void dbscan_test_3612b(void)
335 {
336  struct dbscan_test_info test;
337  char* wkt_inputs[] = { "POINT (1 1)" };
338 
339  test.eps = 0.0;
340  test.min_points = 1;
341  uint32_t expected_ids[] = { 0 };
342  int expected_in_cluster[] = { 1 };
343  test.num_geoms = sizeof(wkt_inputs) / sizeof(char*);
344 
345  test.expected_ids = expected_ids;
347  test.wkt_inputs = wkt_inputs;
348  do_dbscan_test(test);
349 }
350 
351 static void dbscan_test_3612c(void)
352 {
353  struct dbscan_test_info test;
354  char* wkt_inputs[] = { "POLYGONM((-71.1319 42.2503 1,-71.132 42.2502 3,-71.1323 42.2504 -2,-71.1322 42.2505 1,-71.1319 42.2503 0))",
355  "POLYGONM((-71.1319 42.2512 0,-71.1318 42.2511 20,-71.1317 42.2511 -20,-71.1317 42.251 5,-71.1317 42.2509 4,-71.132 42.2511 6,-71.1319 42.2512 30))" };
356  test.eps = 20.1;
357  test.min_points = 5;
358  uint32_t expected_ids[] = { rand(), rand() };
359  int expected_in_cluster[] = { 0, 0 };
360  test.num_geoms = sizeof(wkt_inputs) / sizeof(char*);
361 
362  test.expected_ids = expected_ids;
364  test.wkt_inputs = wkt_inputs;
365  do_dbscan_test(test);
366 }
367 
368 void geos_cluster_suite_setup(void);
370 {
371  CU_pSuite suite = CU_add_suite("clustering", init_geos_cluster_suite, clean_geos_cluster_suite);
372  PG_ADD_TEST(suite, basic_test);
378  PG_ADD_TEST(suite, dbscan_test);
382 }
static void basic_distance_test(void)
static GEOSGeometry ** LWGEOMARRAY2GEOS(LWGEOM **lw_array, size_t num_geoms)
static void multipoint_test(void)
void geos_cluster_suite_setup(void)
static void dbscan_test_3612c(void)
static void perform_cluster_within_distance_test(double tolerance, char **wkt_inputs, uint32_t num_inputs, char **wkt_outputs, uint32_t num_outputs)
static void single_input_test(void)
static void empty_inputs_test(void)
static int clean_geos_cluster_suite(void)
static void dbscan_test_3612b(void)
static void nonsequential_test(void)
static int init_geos_cluster_suite(void)
static void dbscan_test(void)
static void assert_all_results_found(LWGEOM **results, size_t num_outputs, LWGEOM **expected, size_t num_expected_outputs)
static void do_dbscan_test(struct dbscan_test_info test)
static LWGEOM ** GEOSARRAY2LWGEOM(GEOSGeometry **geos_array, size_t num_geoms)
static LWGEOM ** WKTARRAY2LWGEOM(char **wkt_array, size_t num_geoms)
static void dbscan_test_3612a(void)
static void perform_cluster_intersecting_test(char **wkt_inputs, uint32_t num_inputs, char **wkt_outputs, uint32_t num_outputs)
static void basic_test(void)
#define ASSERT_INT_EQUAL(o, e)
#define PG_ADD_TEST(suite, testfunc)
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, uint8_t autofix)
LWGEOM * GEOS2LWGEOM(const GEOSGeometry *geom, uint8_t want3d)
void lwgeom_geos_error(const char *fmt,...)
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...
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...
int union_dbscan(LWGEOM **geoms, uint32_t num_geoms, UNIONFIND *uf, double eps, uint32_t min_points, char **is_in_cluster_ret)
char lwgeom_same(const LWGEOM *lwgeom1, const LWGEOM *lwgeom2)
geom1 same as geom2 iff
Definition: lwgeom.c:582
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1144
#define LW_PARSER_CHECK_NONE
Definition: liblwgeom.h:2005
void lwfree(void *mem)
Definition: lwutil.c:244
LWGEOM * lwgeom_from_wkt(const char *wkt, const char check)
Definition: lwin_wkt.c:904
void * lwalloc(size_t size)
Definition: lwutil.c:229
void lwnotice(const char *fmt,...)
Write a notice out to the notice handler.
Definition: lwutil.c:177
uint32_t * UF_get_collapsed_cluster_ids(UNIONFIND *uf, const char *is_in_cluster)
Definition: lwunionfind.c:145
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:53
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:34
uint32_t * expected_ids
unsigned int uint32_t
Definition: uthash.h:78