cu_algorithm.c 27.2 KB
Newer Older
1 2 3
/**********************************************************************
 *
 * PostGIS - Spatial Types for PostgreSQL
4
 * http://postgis.net
5 6 7 8
 * Copyright 2008 Paul Ramsey
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU General Public Licence. See the COPYING file.
Paul Ramsey's avatar
Paul Ramsey committed
9
 *
10
 **********************************************************************/
11

12 13 14 15
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CUnit/Basic.h"
16

17
#include "liblwgeom_internal.h"
18
#include "cu_tester.h"
19 20 21 22

/*
** Global variables used by tests below
*/
23

24 25 26 27 28
/* Two-point objects */
POINTARRAY *pa21 = NULL;
POINTARRAY *pa22 = NULL;
LWLINE *l21 = NULL;
LWLINE *l22 = NULL;
29 30
/* Parsing support */
LWGEOM_PARSER_RESULT parse_result;
31 32 33 34 35 36


/*
** The suite initialization function.
** Create any re-used objects.
*/
37
static int init_cg_suite(void)
38 39 40
{
	pa21 = ptarray_construct(0, 0, 2);
	pa22 = ptarray_construct(0, 0, 2);
41 42
	l21 = lwline_construct(SRID_UNKNOWN, NULL, pa21);
	l22 = lwline_construct(SRID_UNKNOWN, NULL, pa22);
43
	return 0;
44

45 46 47 48 49 50
}

/*
** The suite cleanup function.
** Frees any global objects.
*/
51
static int clean_cg_suite(void)
52
{
Paul Ramsey's avatar
Paul Ramsey committed
53 54
	if ( l21 ) lwline_free(l21);
	if ( l22 ) lwline_free(l22);
55 56 57 58 59 60
	return 0;
}

/*
** Test left/right side.
*/
61
static void test_lw_segment_side(void)
62
{
63
	int rv = 0;
64
	POINT2D p1, p2, q;
Paul Ramsey's avatar
Paul Ramsey committed
65

66
	/* Vertical line at x=0 */
67 68 69 70
	p1.x = 0.0;
	p1.y = 0.0;
	p2.x = 0.0;
	p2.y = 1.0;
Paul Ramsey's avatar
Paul Ramsey committed
71

72
	/* On the left */
73 74
	q.x = -2.0;
	q.y = 1.5;
Paul Ramsey's avatar
Paul Ramsey committed
75
	rv = lw_segment_side(&p1, &p2, &q);
76
	//printf("left %g\n",rv);
77
	CU_ASSERT(rv < 0);
Paul Ramsey's avatar
Paul Ramsey committed
78

79
	/* On the right */
80
	q.x = 2.0;
Paul Ramsey's avatar
Paul Ramsey committed
81
	rv = lw_segment_side(&p1, &p2, &q);
82
	//printf("right %g\n",rv);
83
	CU_ASSERT(rv > 0);
Paul Ramsey's avatar
Paul Ramsey committed
84

85
	/* On the line */
86
	q.x = 0.0;
Paul Ramsey's avatar
Paul Ramsey committed
87
	rv = lw_segment_side(&p1, &p2, &q);
88
	//printf("on line %g\n",rv);
89
	CU_ASSERT_EQUAL(rv, 0);
Paul Ramsey's avatar
Paul Ramsey committed
90

91 92 93 94 95
}

/*
** Test crossings side.
*/
96
static void test_lw_segment_intersects(void)
97
{
Paul Ramsey's avatar
Paul Ramsey committed
98

99 100 101
#define setpoint(p, x1, y1) {(p).x = (x1); (p).y = (y1);}

	POINT2D p1, p2, q1, q2;
Paul Ramsey's avatar
Paul Ramsey committed
102

103
	/* P: Vertical line at x=0 */
104 105 106 107 108
	setpoint(p1, 0.0, 0.0);
	p1.x = 0.0;
	p1.y = 0.0;
	p2.x = 0.0;
	p2.y = 1.0;
109 110

	/* Q: Horizontal line crossing left to right */
111 112 113 114
	q1.x = -0.5;
	q1.y = 0.5;
	q2.x = 0.5;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
115
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_RIGHT );
116 117

	/* Q: Horizontal line crossing right to left */
118 119 120 121
	q1.x = 0.5;
	q1.y = 0.5;
	q2.x = -0.5;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
122
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_LEFT );
123 124

	/* Q: Horizontal line not crossing right to left */
125 126 127 128
	q1.x = 0.5;
	q1.y = 1.5;
	q2.x = -0.5;
	q2.y = 1.5;
Paul Ramsey's avatar
Paul Ramsey committed
129
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
130

131 132 133 134 135
	/* Q: Horizontal line crossing at second vertex right to left */
	q1.x = 0.5;
	q1.y = 1.0;
	q2.x = -0.5;
	q2.y = 1.0;
Paul Ramsey's avatar
Paul Ramsey committed
136
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
137

138 139 140 141 142
	/* Q: Horizontal line crossing at first vertex right to left */
	q1.x = 0.5;
	q1.y = 0.0;
	q2.x = -0.5;
	q2.y = 0.0;
Paul Ramsey's avatar
Paul Ramsey committed
143
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_LEFT );
144

145 146 147 148 149
	/* Q: Diagonal line with large range crossing at first vertex right to left */
	q1.x = 0.5;
	q1.y = 10.0;
	q2.x = -0.5;
	q2.y = -10.0;
Paul Ramsey's avatar
Paul Ramsey committed
150
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_LEFT );
151

152 153 154 155 156
	/* Q: Diagonal line with large range crossing at second vertex right to left */
	q1.x = 0.5;
	q1.y = 11.0;
	q2.x = -0.5;
	q2.y = -9.0;
Paul Ramsey's avatar
Paul Ramsey committed
157
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
158 159 160 161 162 163

	/* Q: Horizontal touching from left at second vertex*/
	q1.x = -0.5;
	q1.y = 0.5;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
164
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
165 166 167 168 169 170

	/* Q: Horizontal touching from right at first vertex */
	q1.x = 0.0;
	q1.y = 0.5;
	q2.x = 0.5;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
171
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_RIGHT );
172 173 174 175 176 177

	/* Q: Horizontal touching from left and far below on second vertex */
	q1.x = -0.5;
	q1.y = -10.5;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
178
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
179 180 181 182 183 184

	/* Q: Horizontal touching from right and far above on second vertex */
	q1.x = 0.5;
	q1.y = 10.5;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
185
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
186 187

	/* Q: Co-linear from top */
188 189 190 191
	q1.x = 0.0;
	q1.y = 10.0;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
192
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_COLINEAR );
193 194

	/* Q: Co-linear from bottom */
195 196 197 198
	q1.x = 0.0;
	q1.y = -10.0;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
199
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_COLINEAR );
200 201

	/* Q: Co-linear contained */
202 203 204 205
	q1.x = 0.0;
	q1.y = 0.4;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
206
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_COLINEAR );
207 208

	/* Q: Horizontal touching at end point from left */
209 210 211 212
	q1.x = -0.5;
	q1.y = 1.0;
	q2.x = 0.0;
	q2.y = 1.0;
Paul Ramsey's avatar
Paul Ramsey committed
213
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_NO_INTERSECTION );
214 215

	/* Q: Horizontal touching at end point from right */
216 217 218 219
	q1.x = 0.0;
	q1.y = 1.0;
	q2.x = 0.0;
	q2.y = 0.5;
Paul Ramsey's avatar
Paul Ramsey committed
220
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_COLINEAR );
221 222

	/* Q: Horizontal touching at start point from left */
223 224 225 226
	q1.x = 0.0;
	q1.y = 0.0;
	q2.x = -0.5;
	q2.y = 0.0;
Paul Ramsey's avatar
Paul Ramsey committed
227
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_LEFT );
228 229

	/* Q: Horizontal touching at start point from right */
230 231 232 233
	q1.x = 0.0;
	q1.y = 0.0;
	q2.x = 0.5;
	q2.y = 0.0;
Paul Ramsey's avatar
Paul Ramsey committed
234
	CU_ASSERT( lw_segment_intersects(&p1, &p2, &q1, &q2) == SEG_CROSS_RIGHT );
235 236 237

}

238
static void test_lwline_crossing_short_lines(void)
239 240
{

241
	POINT4D p;
Paul Ramsey's avatar
Paul Ramsey committed
242

243
	/*
Paul Ramsey's avatar
Paul Ramsey committed
244
	** Simple test, two two-point lines
245 246 247
	*/

	/* Vertical line from 0,0 to 1,1 */
248 249
	p.x = 0.0;
	p.y = 0.0;
250
	ptarray_set_point4d(pa21, 0, &p);
251
	p.y = 1.0;
252
	ptarray_set_point4d(pa21, 1, &p);
Paul Ramsey's avatar
Paul Ramsey committed
253

254
	/* Horizontal, crossing mid-segment */
255 256
	p.x = -0.5;
	p.y = 0.5;
257
	ptarray_set_point4d(pa22, 0, &p);
258
	p.x = 0.5;
259
	ptarray_set_point4d(pa22, 1, &p);
260

261
	CU_ASSERT( lwline_crossing_direction(l21, l22) == LINE_CROSS_RIGHT );
262

263 264 265
	/* Horizontal, crossing at top end vertex (end crossings don't count) */
	p.x = -0.5;
	p.y = 1.0;
266
	ptarray_set_point4d(pa22, 0, &p);
267
	p.x = 0.5;
268
	ptarray_set_point4d(pa22, 1, &p);
269

270
	CU_ASSERT( lwline_crossing_direction(l21, l22) == LINE_NO_CROSS );
271 272

	/* Horizontal, crossing at bottom end vertex */
273 274
	p.x = -0.5;
	p.y = 0.0;
275
	ptarray_set_point4d(pa22, 0, &p);
276
	p.x = 0.5;
277
	ptarray_set_point4d(pa22, 1, &p);
278

279
	CU_ASSERT( lwline_crossing_direction(l21, l22) == LINE_CROSS_RIGHT );
280 281

	/* Horizontal, no crossing */
282 283
	p.x = -0.5;
	p.y = 2.0;
284
	ptarray_set_point4d(pa22, 0, &p);
285
	p.x = 0.5;
286
	ptarray_set_point4d(pa22, 1, &p);
287

288
	CU_ASSERT( lwline_crossing_direction(l21, l22) == LINE_NO_CROSS );
289 290

	/* Vertical, no crossing */
291 292
	p.x = -0.5;
	p.y = 0.0;
293
	ptarray_set_point4d(pa22, 0, &p);
294
	p.y = 1.0;
295
	ptarray_set_point4d(pa22, 1, &p);
296

297
	CU_ASSERT( lwline_crossing_direction(l21, l22) == LINE_NO_CROSS );
298 299

}
Paul Ramsey's avatar
Paul Ramsey committed
300

301
static void test_lwline_crossing_long_lines(void)
302
{
Paul Ramsey's avatar
Paul Ramsey committed
303 304 305
	LWLINE *l51;
	LWLINE *l52;
	/*
Paul Ramsey's avatar
Paul Ramsey committed
306
	** More complex test, longer lines and multiple crossings
307 308
	*/
	/* Vertical line with vertices at y integers */
309
	l51 = (LWLINE*)lwgeom_from_wkt("LINESTRING(0 0, 0 1, 0 2, 0 3, 0 4)", LW_PARSER_CHECK_NONE);
310 311

	/* Two crossings at segment midpoints */
312
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, -1 1.5, 1 3, 1 4, 1 5)", LW_PARSER_CHECK_NONE);
313
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_MULTICROSS_END_SAME_FIRST_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
314
	lwline_free(l52);
315 316

	/* One crossing at interior vertex */
317
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, 0 1, -1 1, -1 2, -1 3)", LW_PARSER_CHECK_NONE);
318
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_CROSS_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
319
	lwline_free(l52);
320 321

	/* Two crossings at interior vertices */
322
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, 0 1, -1 1, 0 3, 1 3)", LW_PARSER_CHECK_NONE);
323
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_MULTICROSS_END_SAME_FIRST_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
324
	lwline_free(l52);
325 326

	/* Two crossings, one at the first vertex on at interior vertex */
327
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 0, 0 0, -1 1, 0 3, 1 3)", LW_PARSER_CHECK_NONE);
328
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_MULTICROSS_END_SAME_FIRST_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
329
	lwline_free(l52);
330 331

	/* Two crossings, one at the first vertex on the next interior vertex */
332
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 0, 0 0, -1 1, 0 1, 1 2)", LW_PARSER_CHECK_NONE);
333
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_MULTICROSS_END_SAME_FIRST_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
334
	lwline_free(l52);
335 336

	/* Three crossings, two at midpoints, one at vertex */
337
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(0.5 1, -1 0.5, 1 2, -1 2, -1 3)", LW_PARSER_CHECK_NONE);
338
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_MULTICROSS_END_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
339
	lwline_free(l52);
340

341
	/* One mid-point co-linear crossing */
342
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, 0 1.5, 0 2.5, -1 3, -1 4)", LW_PARSER_CHECK_NONE);
343
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_CROSS_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
344
	lwline_free(l52);
345

Paul Ramsey's avatar
Paul Ramsey committed
346
	/* One on-vertices co-linear crossing */
347
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, 0 1, 0 2, -1 4, -1 4)", LW_PARSER_CHECK_NONE);
348
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_CROSS_LEFT );
Paul Ramsey's avatar
Paul Ramsey committed
349
	lwline_free(l52);
Paul Ramsey's avatar
Paul Ramsey committed
350 351

	/* No crossing, but end on a co-linearity. */
352
	l52 = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1, 1 2, 1 3, 0 3, 0 4)", LW_PARSER_CHECK_NONE);
353
	CU_ASSERT( lwline_crossing_direction(l51, l52) == LINE_NO_CROSS );
Paul Ramsey's avatar
Paul Ramsey committed
354
	lwline_free(l52);
Paul Ramsey's avatar
Paul Ramsey committed
355

356 357
	lwline_free(l51);

358 359
}

360

361
static void test_lwline_crossing_bugs(void)
362 363 364
{
	LWLINE *l1;
	LWLINE *l2;
Paul Ramsey's avatar
Paul Ramsey committed
365

366 367
	l1 = (LWLINE*)lwgeom_from_wkt("LINESTRING(2.99 90.16,71 74,20 140,171 154)", LW_PARSER_CHECK_NONE);
	l2 = (LWLINE*)lwgeom_from_wkt("LINESTRING(25 169,89 114,40 70,86 43)", LW_PARSER_CHECK_NONE);
368 369 370 371

	CU_ASSERT( lwline_crossing_direction(l1, l2) == LINE_MULTICROSS_END_RIGHT );
	lwline_free(l1);
	lwline_free(l2);
Paul Ramsey's avatar
Paul Ramsey committed
372

373 374
}

375
static void test_lwpoint_set_ordinate(void)
376
{
377 378 379 380 381 382
	POINT4D p;

	p.x = 0.0;
	p.y = 0.0;
	p.z = 0.0;
	p.m = 0.0;
Paul Ramsey's avatar
Paul Ramsey committed
383

384
	lwpoint_set_ordinate(&p, 'X', 1.5);
385
	CU_ASSERT_EQUAL( p.x, 1.5 );
Paul Ramsey's avatar
Paul Ramsey committed
386

387
	lwpoint_set_ordinate(&p, 'M', 2.5);
388
	CU_ASSERT_EQUAL( p.m, 2.5 );
Paul Ramsey's avatar
Paul Ramsey committed
389

390
	lwpoint_set_ordinate(&p, 'Z', 3.5);
391
	CU_ASSERT_EQUAL( p.z, 3.5 );
Paul Ramsey's avatar
Paul Ramsey committed
392

393 394
}

395
static void test_lwpoint_get_ordinate(void)
396
{
397
	POINT4D p;
398

399 400 401 402
	p.x = 10.0;
	p.y = 20.0;
	p.z = 30.0;
	p.m = 40.0;
Paul Ramsey's avatar
Paul Ramsey committed
403

404 405 406 407
	CU_ASSERT_EQUAL( lwpoint_get_ordinate(&p, 'X'), 10.0 );
	CU_ASSERT_EQUAL( lwpoint_get_ordinate(&p, 'Y'), 20.0 );
	CU_ASSERT_EQUAL( lwpoint_get_ordinate(&p, 'Z'), 30.0 );
	CU_ASSERT_EQUAL( lwpoint_get_ordinate(&p, 'M'), 40.0 );
408 409 410

}

411
static void test_point_interpolate(void)
412
{
413
	POINT4D p, q, r;
Paul Ramsey's avatar
Paul Ramsey committed
414 415
	int rv = 0;

416 417 418 419
	p.x = 10.0;
	p.y = 20.0;
	p.z = 30.0;
	p.m = 40.0;
Paul Ramsey's avatar
Paul Ramsey committed
420

421 422 423 424
	q.x = 20.0;
	q.y = 30.0;
	q.z = 40.0;
	q.m = 50.0;
Paul Ramsey's avatar
Paul Ramsey committed
425

426
	rv = point_interpolate(&p, &q, &r, 1, 1, 'Z', 35.0);
427
	CU_ASSERT_EQUAL( rv, LW_SUCCESS );
428
	CU_ASSERT_EQUAL( r.x, 15.0);
Paul Ramsey's avatar
Paul Ramsey committed
429

430
	rv = point_interpolate(&p, &q, &r, 1, 1, 'M', 41.0);
431
	CU_ASSERT_EQUAL( rv, LW_SUCCESS );
432
	CU_ASSERT_EQUAL( r.y, 21.0);
Paul Ramsey's avatar
Paul Ramsey committed
433

434
	rv = point_interpolate(&p, &q, &r, 1, 1, 'M', 50.0);
435
	CU_ASSERT_EQUAL( rv, LW_SUCCESS );
436
	CU_ASSERT_EQUAL( r.y, 30.0);
Paul Ramsey's avatar
Paul Ramsey committed
437

438
	rv = point_interpolate(&p, &q, &r, 1, 1, 'M', 40.0);
439
	CU_ASSERT_EQUAL( rv, LW_SUCCESS );
440
	CU_ASSERT_EQUAL( r.y, 20.0);
Paul Ramsey's avatar
Paul Ramsey committed
441

442
}
Paul Ramsey's avatar
Paul Ramsey committed
443

444
static void test_lwline_clip(void)
Paul Ramsey's avatar
Paul Ramsey committed
445 446
{
	LWCOLLECTION *c;
447
	LWLINE *line = NULL;
Paul Ramsey's avatar
Paul Ramsey committed
448
	LWLINE *l51 = NULL;
Paul Ramsey's avatar
Paul Ramsey committed
449
	char *ewkt;
Paul Ramsey's avatar
Paul Ramsey committed
450

451
	/* Vertical line with vertices at y integers */
452
	l51 = (LWLINE*)lwgeom_from_wkt("LINESTRING(0 0, 0 1, 0 2, 0 3, 0 4)", LW_PARSER_CHECK_NONE);
Paul Ramsey's avatar
Paul Ramsey committed
453

454
	/* Clip in the middle, mid-range. */
455
	c = lwline_clip_to_ordinate_range(l51, 'Y', 1.5, 2.5);
456
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
457
	//printf("c = %s\n", ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
458 459
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 1.5,0 2,0 2.5))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
460
	lwcollection_free(c);
Paul Ramsey's avatar
Paul Ramsey committed
461

462
	/* Clip off the top. */
463
	c = lwline_clip_to_ordinate_range(l51, 'Y', 3.5, 5.5);
464
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
465 466 467
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 3.5,0 4))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
468
	lwcollection_free(c);
469 470

	/* Clip off the bottom. */
471
	c = lwline_clip_to_ordinate_range(l51, 'Y', -1.5, 2.5);
472
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
473 474 475
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 0,0 1,0 2,0 2.5))" );
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
476
	lwcollection_free(c);
477 478

	/* Range holds entire object. */
479
	c = lwline_clip_to_ordinate_range(l51, 'Y', -1.5, 5.5);
480
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
481 482 483
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 0,0 1,0 2,0 3,0 4))" );
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
484
	lwcollection_free(c);
485 486

	/* Clip on vertices. */
487
	c = lwline_clip_to_ordinate_range(l51, 'Y', 1.0, 2.0);
488
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
489 490 491
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 1,0 2))" );
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
492
	lwcollection_free(c);
493 494

	/* Clip on vertices off the bottom. */
495
	c = lwline_clip_to_ordinate_range(l51, 'Y', -1.0, 2.0);
496
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
497 498 499
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 0,0 1,0 2))" );
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
500
	lwcollection_free(c);
501 502

	/* Clip on top. */
503
	c = lwline_clip_to_ordinate_range(l51, 'Y', -1.0, 0.0);
504
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
505 506 507
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "GEOMETRYCOLLECTION(POINT(0 0))" );
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
508
	lwcollection_free(c);
Paul Ramsey's avatar
Paul Ramsey committed
509

510
	/* ST_LocateBetweenElevations(ST_GeomFromEWKT('LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)'), 1, 2)) */
511
	line = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)", LW_PARSER_CHECK_NONE);
512
	c = lwline_clip_to_ordinate_range(line, 'Z', 1.0, 2.0);
513
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
514 515 516 517 518 519
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((2 2 2,1 1 1))" );
	lwfree(ewkt);
	lwcollection_free(c);
	lwline_free(line);

	/* ST_LocateBetweenElevations('LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)', 1, 2)) */
520
	line = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)", LW_PARSER_CHECK_NONE);
521
	c = lwline_clip_to_ordinate_range(line, 'Z', 1.0, 2.0);
522
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
523 524 525 526 527
	//printf("a = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((2 2 2,1 1 1))" );
	lwfree(ewkt);
	lwcollection_free(c);
	lwline_free(line);
Paul Ramsey's avatar
Paul Ramsey committed
528

529
	/* ST_LocateBetweenElevations('LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)', 1, 1)) */
530
	line = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 2 3, 4 5 6, 6 6 6, 1 1 1)", LW_PARSER_CHECK_NONE);
531
	c = lwline_clip_to_ordinate_range(line, 'Z', 1.0, 1.0);
532
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
533 534 535 536 537 538 539
	//printf("b = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "GEOMETRYCOLLECTION(POINT(1 1 1))" );
	lwfree(ewkt);
	lwcollection_free(c);
	lwline_free(line);

	/* ST_LocateBetweenElevations('LINESTRING(1 1 1, 1 2 2)', 1,1) */
540
	line = (LWLINE*)lwgeom_from_wkt("LINESTRING(1 1 1, 1 2 2)", LW_PARSER_CHECK_NONE);
541
	c = lwline_clip_to_ordinate_range(line, 'Z', 1.0, 1.0);
542
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
543 544 545 546 547 548
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "GEOMETRYCOLLECTION(POINT(1 1 1))" );
	lwfree(ewkt);
	lwcollection_free(c);
	lwline_free(line);

Paul Ramsey's avatar
Paul Ramsey committed
549
	lwline_free(l51);
550

Paul Ramsey's avatar
Paul Ramsey committed
551 552
}

553
static void test_lwmline_clip(void)
554 555 556 557
{
	LWCOLLECTION *c;
	char *ewkt;
	LWMLINE *mline = NULL;
558
	LWLINE *line = NULL;
559 560

	/*
Paul Ramsey's avatar
Paul Ramsey committed
561
	** Set up the input line. Trivial one-member case.
562
	*/
563
	mline = (LWMLINE*)lwgeom_from_wkt("MULTILINESTRING((0 0,0 1,0 2,0 3,0 4))", LW_PARSER_CHECK_NONE);
564 565

	/* Clip in the middle, mid-range. */
566
	c = lwmline_clip_to_ordinate_range(mline, 'Y', 1.5, 2.5);
567
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
568 569 570
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0 1.5,0 2,0 2.5))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
571
	lwcollection_free(c);
572

Paul Ramsey's avatar
Paul Ramsey committed
573
	lwmline_free(mline);
574

Paul Ramsey's avatar
Paul Ramsey committed
575
	/*
Paul Ramsey's avatar
Paul Ramsey committed
576
	** Set up the input line. Two-member case.
577
	*/
578
	mline = (LWMLINE*)lwgeom_from_wkt("MULTILINESTRING((1 0,1 1,1 2,1 3,1 4), (0 0,0 1,0 2,0 3,0 4))", LW_PARSER_CHECK_NONE);
579 580

	/* Clip off the top. */
581
	c = lwmline_clip_to_ordinate_range(mline, 'Y', 3.5, 5.5);
582
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
583 584 585
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((1 3.5,1 4),(0 3.5,0 4))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
586
	lwcollection_free(c);
587

Paul Ramsey's avatar
Paul Ramsey committed
588
	lwmline_free(mline);
589

Paul Ramsey's avatar
Paul Ramsey committed
590
	/*
Paul Ramsey's avatar
Paul Ramsey committed
591
	** Set up staggered input line to create multi-type output.
592
	*/
593
	mline = (LWMLINE*)lwgeom_from_wkt("MULTILINESTRING((1 0,1 -1,1 -2,1 -3,1 -4), (0 0,0 1,0 2,0 3,0 4))", LW_PARSER_CHECK_NONE);
594 595

	/* Clip from 0 upwards.. */
596
	c = lwmline_clip_to_ordinate_range(mline, 'Y', 0.0, 2.5);
597
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
598 599 600
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "GEOMETRYCOLLECTION(POINT(1 0),LINESTRING(0 0,0 1,0 2,0 2.5))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
601
	lwcollection_free(c);
602

Paul Ramsey's avatar
Paul Ramsey committed
603
	lwmline_free(mline);
604

Paul Ramsey's avatar
Paul Ramsey committed
605
	/*
606 607
	** Set up input line from MAC
	*/
608
	line = (LWLINE*)lwgeom_from_wkt("LINESTRING(0 0 0 0,1 1 1 1,2 2 2 2,3 3 3 3,4 4 4 4,3 3 3 5,2 2 2 6,1 1 1 7,0 0 0 8)", LW_PARSER_CHECK_NONE);
609 610

	/* Clip from 3 to 3.5 */
611
	c = lwline_clip_to_ordinate_range(line, 'Z', 3.0, 3.5);
612
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
613 614 615
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((3 3 3 3,3.5 3.5 3.5 3.5),(3.5 3.5 3.5 4.5,3 3 3 5))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
616
	lwcollection_free(c);
617 618

	/* Clip from 2 to 3.5 */
619
	c = lwline_clip_to_ordinate_range(line, 'Z', 2.0, 3.5);
620
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
621 622 623
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((2 2 2 2,3 3 3 3,3.5 3.5 3.5 3.5),(3.5 3.5 3.5 4.5,3 3 3 5,2 2 2 6))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
624
	lwcollection_free(c);
625 626

	/* Clip from 3 to 4 */
627
	c = lwline_clip_to_ordinate_range(line, 'Z', 3.0, 4.0);
628
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
629 630 631
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((3 3 3 3,4 4 4 4,3 3 3 5))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
632
	lwcollection_free(c);
633 634

	/* Clip from 2 to 3 */
635
	c = lwline_clip_to_ordinate_range(line, 'Z', 2.0, 3.0);
636
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
637 638 639
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((2 2 2 2,3 3 3 3),(3 3 3 5,2 2 2 6))");
	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
640
	lwcollection_free(c);
641 642


Paul Ramsey's avatar
Paul Ramsey committed
643
	lwline_free(line);
644

645 646 647 648
}



649
static void test_lwline_clip_big(void)
650 651
{
	POINTARRAY *pa = ptarray_construct(1, 0, 3);
652
	LWLINE *line = lwline_construct(SRID_UNKNOWN, NULL, pa);
653 654
	LWCOLLECTION *c;
	char *ewkt;
655 656 657 658 659
	POINT4D p;

	p.x = 0.0;
	p.y = 0.0;
	p.z = 0.0;
660
	ptarray_set_point4d(pa, 0, &p);
661 662 663 664

	p.x = 1.0;
	p.y = 1.0;
	p.z = 1.0;
665
	ptarray_set_point4d(pa, 1, &p);
666 667 668 669

	p.x = 2.0;
	p.y = 2.0;
	p.z = 2.0;
670
	ptarray_set_point4d(pa, 2, &p);
Paul Ramsey's avatar
Paul Ramsey committed
671

672
	c = lwline_clip_to_ordinate_range(line, 'Z', 0.5, 1.5);
673
	ewkt = lwgeom_to_ewkt((LWGEOM*)c);
674 675 676 677
	//printf("c = %s\n", ewkt);
	CU_ASSERT_STRING_EQUAL(ewkt, "MULTILINESTRING((0.5 0.5 0.5,1 1 1,1.5 1.5 1.5))" );

	lwfree(ewkt);
Paul Ramsey's avatar
Paul Ramsey committed
678 679
	lwcollection_free(c);
	lwline_free(line);
680 681
}

682
static void test_geohash_precision(void)
683
{
684 685
	GBOX bbox;
	GBOX bounds;
686
	int precision = 0;
687 688
	gbox_init(&bbox);
	gbox_init(&bounds);
689

690 691 692 693
	bbox.xmin = 23.0;
	bbox.xmax = 23.0;
	bbox.ymin = 25.2;
	bbox.ymax = 25.2;
Paul Ramsey's avatar
Paul Ramsey committed
694
	precision = lwgeom_geohash_precision(bbox, &bounds);
695
	//printf("\nprecision %d\n",precision);
696 697 698 699 700 701
	CU_ASSERT_EQUAL(precision, 20);

	bbox.xmin = 23.0;
	bbox.ymin = 23.0;
	bbox.xmax = 23.1;
	bbox.ymax = 23.1;
Paul Ramsey's avatar
Paul Ramsey committed
702
	precision = lwgeom_geohash_precision(bbox, &bounds);
703 704
	//printf("precision %d\n",precision);
	CU_ASSERT_EQUAL(precision, 3);
705 706 707 708 709

	bbox.xmin = 23.0;
	bbox.ymin = 23.0;
	bbox.xmax = 23.0001;
	bbox.ymax = 23.0001;
Paul Ramsey's avatar
Paul Ramsey committed
710
	precision = lwgeom_geohash_precision(bbox, &bounds);
711 712
	//printf("precision %d\n",precision);
	CU_ASSERT_EQUAL(precision, 7);
713 714 715

}

716
static void test_geohash_point(void)
Paul Ramsey's avatar
Paul Ramsey committed
717
{
718 719 720
	char *geohash;

	geohash = geohash_point(0, 0, 16);
Paul Ramsey's avatar
Paul Ramsey committed
721
	//printf("\ngeohash %s\n",geohash);
722
	CU_ASSERT_STRING_EQUAL(geohash, "s000000000000000");
Paul Ramsey's avatar
Paul Ramsey committed
723 724
	lwfree(geohash);

725
	geohash = geohash_point(90, 0, 16);
Paul Ramsey's avatar
Paul Ramsey committed
726
	//printf("\ngeohash %s\n",geohash);
727
	CU_ASSERT_STRING_EQUAL(geohash, "w000000000000000");
Paul Ramsey's avatar
Paul Ramsey committed
728 729
	lwfree(geohash);

730
	geohash = geohash_point(20.012345, -20.012345, 15);
Paul Ramsey's avatar
Paul Ramsey committed
731
	//printf("\ngeohash %s\n",geohash);
732
	CU_ASSERT_STRING_EQUAL(geohash, "kkqnpkue9ktbpe5");
Paul Ramsey's avatar
Paul Ramsey committed
733 734 735 736
	lwfree(geohash);

}

737
static void test_geohash(void)
738 739 740 741 742
{
	LWPOINT *lwpoint = NULL;
	LWLINE *lwline = NULL;
	LWMLINE *lwmline = NULL;
	char *geohash = NULL;
743

744
	lwpoint = (LWPOINT*)lwgeom_from_wkt("POINT(23.0 25.2)", LW_PARSER_CHECK_NONE);
745 746 747
	geohash = lwgeom_geohash((LWGEOM*)lwpoint,0);
	//printf("\ngeohash %s\n",geohash);
	CU_ASSERT_STRING_EQUAL(geohash, "ss2r77s0du7p2ewb8hmx");
748
	lwpoint_free(lwpoint);
749 750
	lwfree(geohash);

751
	lwpoint = (LWPOINT*)lwgeom_from_wkt("POINT(23.0 25.2 2.0)", LW_PARSER_CHECK_NONE);
752 753 754
	geohash = lwgeom_geohash((LWGEOM*)lwpoint,0);
	//printf("geohash %s\n",geohash);
	CU_ASSERT_STRING_EQUAL(geohash, "ss2r77s0du7p2ewb8hmx");
755
	lwpoint_free(lwpoint);
756 757
	lwfree(geohash);

758
	lwline = (LWLINE*)lwgeom_from_wkt("LINESTRING(23.0 23.0,23.1 23.1)", LW_PARSER_CHECK_NONE);
759 760 761
	geohash = lwgeom_geohash((LWGEOM*)lwline,0);
	//printf("geohash %s\n",geohash);
	CU_ASSERT_STRING_EQUAL(geohash, "ss0");
762
	lwline_free(lwline);
763 764
	lwfree(geohash);

765
	lwline = (LWLINE*)lwgeom_from_wkt("LINESTRING(23.0 23.0,23.001 23.001)", LW_PARSER_CHECK_NONE);
766 767 768
	geohash = lwgeom_geohash((LWGEOM*)lwline,0);
	//printf("geohash %s\n",geohash);
	CU_ASSERT_STRING_EQUAL(geohash, "ss06g7");
769
	lwline_free(lwline);
770 771
	lwfree(geohash);

772
	lwmline = (LWMLINE*)lwgeom_from_wkt("MULTILINESTRING((23.0 23.0,23.1 23.1),(23.0 23.0,23.1 23.1))", LW_PARSER_CHECK_NONE);
773 774 775
	geohash = lwgeom_geohash((LWGEOM*)lwmline,0);
	//printf("geohash %s\n",geohash);
	CU_ASSERT_STRING_EQUAL(geohash, "ss0");
776
	lwmline_free(lwmline);
777 778 779
	lwfree(geohash);
}