Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * geo_ops.c
4 : * 2D geometric operations
5 : *
6 : * This module implements the geometric functions and operators. The
7 : * geometric types are (from simple to more complicated):
8 : *
9 : * - point
10 : * - line
11 : * - line segment
12 : * - box
13 : * - circle
14 : * - polygon
15 : *
16 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
17 : * Portions Copyright (c) 1994, Regents of the University of California
18 : *
19 : *
20 : * IDENTIFICATION
21 : * src/backend/utils/adt/geo_ops.c
22 : *
23 : *-------------------------------------------------------------------------
24 : */
25 : #include "postgres.h"
26 :
27 : #include <math.h>
28 : #include <limits.h>
29 : #include <float.h>
30 : #include <ctype.h>
31 :
32 : #include "libpq/pqformat.h"
33 : #include "miscadmin.h"
34 : #include "nodes/miscnodes.h"
35 : #include "utils/float.h"
36 : #include "utils/fmgrprotos.h"
37 : #include "utils/geo_decls.h"
38 : #include "varatt.h"
39 :
40 : /*
41 : * * Type constructors have this form:
42 : * void type_construct(Type *result, ...);
43 : *
44 : * * Operators commonly have signatures such as
45 : * void type1_operator_type2(Type *result, Type1 *obj1, Type2 *obj2);
46 : *
47 : * Common operators are:
48 : * * Intersection point:
49 : * bool type1_interpt_type2(Point *result, Type1 *obj1, Type2 *obj2);
50 : * Return whether the two objects intersect. If *result is not NULL,
51 : * it is set to the intersection point.
52 : *
53 : * * Containment:
54 : * bool type1_contain_type2(Type1 *obj1, Type2 *obj2);
55 : * Return whether obj1 contains obj2.
56 : * bool type1_contain_type2(Type1 *contains_obj, Type1 *contained_obj);
57 : * Return whether obj1 contains obj2 (used when types are the same)
58 : *
59 : * * Distance of closest point in or on obj1 to obj2:
60 : * float8 type1_closept_type2(Point *result, Type1 *obj1, Type2 *obj2);
61 : * Returns the shortest distance between two objects. If *result is not
62 : * NULL, it is set to the closest point in or on obj1 to obj2.
63 : *
64 : * These functions may be used to implement multiple SQL-level operators. For
65 : * example, determining whether two lines are parallel is done by checking
66 : * whether they don't intersect.
67 : */
68 :
69 : /*
70 : * Internal routines
71 : */
72 :
73 : enum path_delim
74 : {
75 : PATH_NONE, PATH_OPEN, PATH_CLOSED
76 : };
77 :
78 : /* Routines for points */
79 : static inline void point_construct(Point *result, float8 x, float8 y);
80 : static inline void point_add_point(Point *result, Point *pt1, Point *pt2);
81 : static inline void point_sub_point(Point *result, Point *pt1, Point *pt2);
82 : static inline void point_mul_point(Point *result, Point *pt1, Point *pt2);
83 : static inline void point_div_point(Point *result, Point *pt1, Point *pt2);
84 : static inline bool point_eq_point(Point *pt1, Point *pt2);
85 : static inline float8 point_dt(Point *pt1, Point *pt2);
86 : static inline float8 point_sl(Point *pt1, Point *pt2);
87 : static int point_inside(Point *p, int npts, Point *plist);
88 :
89 : /* Routines for lines */
90 : static inline void line_construct(LINE *result, Point *pt, float8 m);
91 : static inline float8 line_sl(LINE *line);
92 : static inline float8 line_invsl(LINE *line);
93 : static bool line_interpt_line(Point *result, LINE *l1, LINE *l2);
94 : static bool line_contain_point(LINE *line, Point *point);
95 : static float8 line_closept_point(Point *result, LINE *line, Point *point);
96 :
97 : /* Routines for line segments */
98 : static inline void statlseg_construct(LSEG *lseg, Point *pt1, Point *pt2);
99 : static inline float8 lseg_sl(LSEG *lseg);
100 : static inline float8 lseg_invsl(LSEG *lseg);
101 : static bool lseg_interpt_line(Point *result, LSEG *lseg, LINE *line);
102 : static bool lseg_interpt_lseg(Point *result, LSEG *l1, LSEG *l2);
103 : static int lseg_crossing(float8 x, float8 y, float8 prev_x, float8 prev_y);
104 : static bool lseg_contain_point(LSEG *lseg, Point *pt);
105 : static float8 lseg_closept_point(Point *result, LSEG *lseg, Point *pt);
106 : static float8 lseg_closept_line(Point *result, LSEG *lseg, LINE *line);
107 : static float8 lseg_closept_lseg(Point *result, LSEG *on_lseg, LSEG *to_lseg);
108 :
109 : /* Routines for boxes */
110 : static inline void box_construct(BOX *result, Point *pt1, Point *pt2);
111 : static void box_cn(Point *center, BOX *box);
112 : static bool box_ov(BOX *box1, BOX *box2);
113 : static float8 box_ar(BOX *box);
114 : static float8 box_ht(BOX *box);
115 : static float8 box_wd(BOX *box);
116 : static bool box_contain_point(BOX *box, Point *point);
117 : static bool box_contain_box(BOX *contains_box, BOX *contained_box);
118 : static bool box_contain_lseg(BOX *box, LSEG *lseg);
119 : static bool box_interpt_lseg(Point *result, BOX *box, LSEG *lseg);
120 : static float8 box_closept_point(Point *result, BOX *box, Point *pt);
121 : static float8 box_closept_lseg(Point *result, BOX *box, LSEG *lseg);
122 :
123 : /* Routines for circles */
124 : static float8 circle_ar(CIRCLE *circle);
125 :
126 : /* Routines for polygons */
127 : static void make_bound_box(POLYGON *poly);
128 : static void poly_to_circle(CIRCLE *result, POLYGON *poly);
129 : static bool lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start);
130 : static bool poly_contain_poly(POLYGON *contains_poly, POLYGON *contained_poly);
131 : static bool plist_same(int npts, Point *p1, Point *p2);
132 : static float8 dist_ppoly_internal(Point *pt, POLYGON *poly);
133 :
134 : /* Routines for encoding and decoding */
135 : static bool single_decode(char *num, float8 *x, char **endptr_p,
136 : const char *type_name, const char *orig_string,
137 : Node *escontext);
138 : static void single_encode(float8 x, StringInfo str);
139 : static bool pair_decode(char *str, float8 *x, float8 *y, char **endptr_p,
140 : const char *type_name, const char *orig_string,
141 : Node *escontext);
142 : static void pair_encode(float8 x, float8 y, StringInfo str);
143 : static int pair_count(char *s, char delim);
144 : static bool path_decode(char *str, bool opentype, int npts, Point *p,
145 : bool *isopen, char **endptr_p,
146 : const char *type_name, const char *orig_string,
147 : Node *escontext);
148 : static char *path_encode(enum path_delim path_delim, int npts, Point *pt);
149 :
150 :
151 : /*
152 : * Delimiters for input and output strings.
153 : * LDELIM, RDELIM, and DELIM are left, right, and separator delimiters, respectively.
154 : * LDELIM_EP, RDELIM_EP are left and right delimiters for paths with endpoints.
155 : */
156 :
157 : #define LDELIM '('
158 : #define RDELIM ')'
159 : #define DELIM ','
160 : #define LDELIM_EP '['
161 : #define RDELIM_EP ']'
162 : #define LDELIM_C '<'
163 : #define RDELIM_C '>'
164 : #define LDELIM_L '{'
165 : #define RDELIM_L '}'
166 :
167 :
168 : /*
169 : * Geometric data types are composed of points.
170 : * This code tries to support a common format throughout the data types,
171 : * to allow for more predictable usage and data type conversion.
172 : * The fundamental unit is the point. Other units are line segments,
173 : * open paths, boxes, closed paths, and polygons (which should be considered
174 : * non-intersecting closed paths).
175 : *
176 : * Data representation is as follows:
177 : * point: (x,y)
178 : * line segment: [(x1,y1),(x2,y2)]
179 : * box: (x1,y1),(x2,y2)
180 : * open path: [(x1,y1),...,(xn,yn)]
181 : * closed path: ((x1,y1),...,(xn,yn))
182 : * polygon: ((x1,y1),...,(xn,yn))
183 : *
184 : * For boxes, the points are opposite corners with the first point at the top right.
185 : * For closed paths and polygons, the points should be reordered to allow
186 : * fast and correct equality comparisons.
187 : *
188 : * XXX perhaps points in complex shapes should be reordered internally
189 : * to allow faster internal operations, but should keep track of input order
190 : * and restore that order for text output - tgl 97/01/16
191 : */
192 :
193 : static bool
116 tgl 194 GNC 112368 : single_decode(char *num, float8 *x, char **endptr_p,
195 : const char *type_name, const char *orig_string,
196 : Node *escontext)
197 : {
198 112368 : *x = float8in_internal(num, endptr_p, type_name, orig_string, escontext);
199 112341 : return (!SOFT_ERROR_OCCURRED(escontext));
200 : } /* single_decode() */
9385 lockhart 201 ECB :
202 : static void
2566 tgl 203 GIC 4588 : single_encode(float8 x, StringInfo str)
204 : {
2566 tgl 205 CBC 4588 : char *xstr = float8out_internal(x);
7457 tgl 206 ECB :
2566 tgl 207 GIC 4588 : appendStringInfoString(str, xstr);
208 4588 : pfree(xstr);
2118 209 4588 : } /* single_encode() */
9483 scrappy 210 ECB :
211 : static bool
1697 tomas.vondra 212 CBC 56019 : pair_decode(char *str, float8 *x, float8 *y, char **endptr_p,
213 : const char *type_name, const char *orig_string,
214 : Node *escontext)
9345 bruce 215 ECB : {
2566 tgl 216 : bool has_delim;
9345 bruce 217 :
8162 tgl 218 GIC 56061 : while (isspace((unsigned char) *str))
9345 bruce 219 42 : str++;
9345 bruce 220 CBC 56019 : if ((has_delim = (*str == LDELIM)))
9345 bruce 221 GIC 36571 : str++;
222 :
116 tgl 223 GNC 56019 : if (!single_decode(str, x, &str, type_name, orig_string, escontext))
116 tgl 224 UNC 0 : return false;
225 :
2566 tgl 226 GIC 56001 : if (*str++ != DELIM)
116 tgl 227 GNC 27 : goto fail;
228 :
229 55974 : if (!single_decode(str, y, &str, type_name, orig_string, escontext))
230 27 : return false;
2566 tgl 231 EUB :
9345 bruce 232 GIC 55941 : if (has_delim)
9345 bruce 233 ECB : {
2566 tgl 234 CBC 36532 : if (*str++ != RDELIM)
116 tgl 235 GNC 9 : goto fail;
8162 tgl 236 CBC 36556 : while (isspace((unsigned char) *str))
9345 bruce 237 GIC 33 : str++;
9345 bruce 238 ECB : }
9483 scrappy 239 :
2566 tgl 240 : /* report stopping point if wanted, else complain if not end of string */
2566 tgl 241 CBC 55932 : if (endptr_p)
2566 tgl 242 GIC 55087 : *endptr_p = str;
243 845 : else if (*str != '\0')
116 tgl 244 GNC 3 : goto fail;
245 55929 : return true;
246 :
247 39 : fail:
248 39 : ereturn(escontext, false,
249 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
250 : errmsg("invalid input syntax for type %s: \"%s\"",
251 : type_name, orig_string)));
9483 scrappy 252 ECB : }
253 :
254 : static void
2566 tgl 255 CBC 891796 : pair_encode(float8 x, float8 y, StringInfo str)
9483 scrappy 256 ECB : {
2566 tgl 257 GIC 891796 : char *xstr = float8out_internal(x);
258 891796 : char *ystr = float8out_internal(y);
259 :
260 891796 : appendStringInfo(str, "%s,%s", xstr, ystr);
261 891796 : pfree(xstr);
262 891796 : pfree(ystr);
9483 scrappy 263 CBC 891796 : }
264 :
265 : static bool
2566 tgl 266 25648 : path_decode(char *str, bool opentype, int npts, Point *p,
267 : bool *isopen, char **endptr_p,
268 : const char *type_name, const char *orig_string,
269 : Node *escontext)
9345 bruce 270 ECB : {
9344 bruce 271 CBC 25648 : int depth = 0;
2566 tgl 272 ECB : char *cp;
273 : int i;
274 :
2566 tgl 275 CBC 25651 : while (isspace((unsigned char) *str))
2566 tgl 276 GIC 3 : str++;
277 25648 : if ((*isopen = (*str == LDELIM_EP)))
278 : {
279 : /* no open delimiter allowed? */
9345 bruce 280 CBC 15205 : if (!opentype)
116 tgl 281 GNC 3 : goto fail;
9345 bruce 282 CBC 15202 : depth++;
2566 tgl 283 15202 : str++;
284 : }
2566 tgl 285 GIC 10443 : else if (*str == LDELIM)
9345 bruce 286 ECB : {
2566 tgl 287 CBC 10365 : cp = (str + 1);
8162 288 10374 : while (isspace((unsigned char) *cp))
9345 bruce 289 9 : cp++;
9345 bruce 290 GIC 10365 : if (*cp == LDELIM)
9345 bruce 291 ECB : {
9345 bruce 292 GIC 616 : depth++;
2566 tgl 293 CBC 616 : str = cp;
9345 bruce 294 ECB : }
2566 tgl 295 CBC 9749 : else if (strrchr(str, LDELIM) == str)
9345 bruce 296 ECB : {
9345 bruce 297 GIC 9529 : depth++;
2566 tgl 298 CBC 9529 : str = cp;
9345 bruce 299 ECB : }
300 : }
9483 scrappy 301 :
9345 bruce 302 GIC 80543 : for (i = 0; i < npts; i++)
9345 bruce 303 ECB : {
116 tgl 304 GNC 54955 : if (!pair_decode(str, &(p->x), &(p->y), &str, type_name, orig_string,
305 : escontext))
306 36 : return false;
2566 tgl 307 GIC 54898 : if (*str == DELIM)
308 29292 : str++;
9345 bruce 309 54898 : p++;
9347 bruce 310 ECB : }
311 :
9345 bruce 312 CBC 50872 : while (depth > 0)
313 : {
1715 tomas.vondra 314 25305 : if (*str == RDELIM || (*str == RDELIM_EP && *isopen && depth == 1))
9345 bruce 315 ECB : {
9345 bruce 316 CBC 25284 : depth--;
2566 tgl 317 25284 : str++;
2566 tgl 318 GIC 25293 : while (isspace((unsigned char) *str))
319 9 : str++;
9345 bruce 320 ECB : }
321 : else
116 tgl 322 GNC 21 : goto fail;
9345 bruce 323 ECB : }
324 :
325 : /* report stopping point if wanted, else complain if not end of string */
2566 tgl 326 GIC 25567 : if (endptr_p)
2566 tgl 327 CBC 15440 : *endptr_p = str;
2566 tgl 328 GIC 10127 : else if (*str != '\0')
116 tgl 329 GNC 3 : goto fail;
330 25564 : return true;
331 :
332 27 : fail:
333 27 : ereturn(escontext, false,
334 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
335 : errmsg("invalid input syntax for type %s: \"%s\"",
336 : type_name, orig_string)));
2118 tgl 337 ECB : } /* path_decode() */
9345 bruce 338 :
9344 339 : static char *
3562 peter_e 340 GIC 298899 : path_encode(enum path_delim path_delim, int npts, Point *pt)
9345 bruce 341 ECB : {
2566 tgl 342 : StringInfoData str;
343 : int i;
344 :
2566 tgl 345 GIC 298899 : initStringInfo(&str);
346 :
3562 peter_e 347 298899 : switch (path_delim)
348 : {
3562 peter_e 349 CBC 50323 : case PATH_CLOSED:
2566 tgl 350 GIC 50323 : appendStringInfoChar(&str, LDELIM);
9344 bruce 351 50323 : break;
3562 peter_e 352 30200 : case PATH_OPEN:
2566 tgl 353 30200 : appendStringInfoChar(&str, LDELIM_EP);
9344 bruce 354 CBC 30200 : break;
3562 peter_e 355 GIC 218376 : case PATH_NONE:
9344 bruce 356 CBC 218376 : break;
357 : }
9483 scrappy 358 ECB :
9345 bruce 359 CBC 1186107 : for (i = 0; i < npts; i++)
9345 bruce 360 ECB : {
2566 tgl 361 CBC 887208 : if (i > 0)
362 588309 : appendStringInfoChar(&str, DELIM);
363 887208 : appendStringInfoChar(&str, LDELIM);
364 887208 : pair_encode(pt->x, pt->y, &str);
365 887208 : appendStringInfoChar(&str, RDELIM);
9345 bruce 366 GIC 887208 : pt++;
367 : }
2566 tgl 368 ECB :
3562 peter_e 369 GIC 298899 : switch (path_delim)
9345 bruce 370 ECB : {
3562 peter_e 371 CBC 50323 : case PATH_CLOSED:
2566 tgl 372 50323 : appendStringInfoChar(&str, RDELIM);
9344 bruce 373 50323 : break;
3562 peter_e 374 30200 : case PATH_OPEN:
2566 tgl 375 30200 : appendStringInfoChar(&str, RDELIM_EP);
9344 bruce 376 GIC 30200 : break;
3562 peter_e 377 218376 : case PATH_NONE:
9344 bruce 378 CBC 218376 : break;
379 : }
9483 scrappy 380 ECB :
2566 tgl 381 CBC 298899 : return str.data;
2118 tgl 382 ECB : } /* path_encode() */
9483 scrappy 383 :
384 : /*-------------------------------------------------------------
385 : * pair_count - count the number of points
386 : * allow the following notation:
387 : * '((1,2),(3,4))'
388 : * '(1,3,2,4)'
389 : * require an odd number of delim characters in the string
390 : *-------------------------------------------------------------*/
391 : static int
9345 bruce 392 GIC 15664 : pair_count(char *s, char delim)
393 : {
9344 394 15664 : int ndelim = 0;
395 :
9345 396 70007 : while ((s = strchr(s, delim)) != NULL)
397 : {
398 54343 : ndelim++;
399 54343 : s++;
400 : }
8986 bruce 401 CBC 15664 : return (ndelim % 2) ? ((ndelim + 1) / 2) : -1;
402 : }
9770 scrappy 403 ECB :
404 :
405 : /***********************************************************************
406 : **
9345 bruce 407 : ** Routines for two-dimensional boxes.
9770 scrappy 408 : **
409 : ***********************************************************************/
410 :
411 : /*----------------------------------------------------------
412 : * Formatting and conversion routines.
413 : *---------------------------------------------------------*/
414 :
415 : /* box_in - convert a string to internal form.
416 : *
417 : * External format: (two corners of box)
418 : * "(f8, f8), (f8, f8)"
419 : * also supports the older style "(f8, f8, f8, f8)"
420 : */
421 : Datum
8288 tgl 422 GIC 9922 : box_in(PG_FUNCTION_ARGS)
423 : {
424 9922 : char *str = PG_GETARG_CSTRING(0);
116 tgl 425 GNC 9922 : Node *escontext = fcinfo->context;
8288 tgl 426 GIC 9922 : BOX *box = (BOX *) palloc(sizeof(BOX));
427 : bool isopen;
428 : float8 x,
429 : y;
430 :
116 tgl 431 GNC 9922 : if (!path_decode(str, false, 2, &(box->high), &isopen, NULL, "box", str,
432 : escontext))
433 12 : PG_RETURN_NULL();
9483 scrappy 434 ECB :
435 : /* reorder corners if necessary... */
1697 tomas.vondra 436 CBC 9895 : if (float8_lt(box->high.x, box->low.x))
9345 bruce 437 ECB : {
9345 bruce 438 CBC 448 : x = box->high.x;
9345 bruce 439 GIC 448 : box->high.x = box->low.x;
440 448 : box->low.x = x;
441 : }
1697 tomas.vondra 442 9895 : if (float8_lt(box->high.y, box->low.y))
9345 bruce 443 ECB : {
9345 bruce 444 GIC 454 : y = box->high.y;
9345 bruce 445 CBC 454 : box->high.y = box->low.y;
9345 bruce 446 GIC 454 : box->low.y = y;
447 : }
9483 scrappy 448 ECB :
8288 tgl 449 GIC 9895 : PG_RETURN_BOX_P(box);
8288 tgl 450 ECB : }
9770 scrappy 451 :
9345 bruce 452 : /* box_out - convert a box to external form.
453 : */
8288 tgl 454 : Datum
8288 tgl 455 GIC 88442 : box_out(PG_FUNCTION_ARGS)
9770 scrappy 456 ECB : {
8288 tgl 457 CBC 88442 : BOX *box = PG_GETARG_BOX_P(0);
9483 scrappy 458 ECB :
3562 peter_e 459 GIC 88442 : PG_RETURN_CSTRING(path_encode(PATH_NONE, 2, &(box->high)));
460 : }
9770 scrappy 461 ECB :
462 : /*
463 : * box_recv - converts external binary format to box
464 : */
465 : Datum
7271 tgl 466 UIC 0 : box_recv(PG_FUNCTION_ARGS)
7271 tgl 467 ECB : {
7271 tgl 468 UIC 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
7271 tgl 469 ECB : BOX *box;
470 : float8 x,
471 : y;
472 :
7271 tgl 473 UIC 0 : box = (BOX *) palloc(sizeof(BOX));
474 :
475 0 : box->high.x = pq_getmsgfloat8(buf);
476 0 : box->high.y = pq_getmsgfloat8(buf);
477 0 : box->low.x = pq_getmsgfloat8(buf);
7271 tgl 478 UBC 0 : box->low.y = pq_getmsgfloat8(buf);
479 :
7271 tgl 480 EUB : /* reorder corners if necessary... */
1697 tomas.vondra 481 UIC 0 : if (float8_lt(box->high.x, box->low.x))
482 : {
7271 tgl 483 0 : x = box->high.x;
484 0 : box->high.x = box->low.x;
7271 tgl 485 UBC 0 : box->low.x = x;
486 : }
1697 tomas.vondra 487 0 : if (float8_lt(box->high.y, box->low.y))
7271 tgl 488 EUB : {
7271 tgl 489 UBC 0 : y = box->high.y;
490 0 : box->high.y = box->low.y;
7271 tgl 491 UIC 0 : box->low.y = y;
492 : }
7271 tgl 493 EUB :
7271 tgl 494 UIC 0 : PG_RETURN_BOX_P(box);
7271 tgl 495 EUB : }
496 :
497 : /*
498 : * box_send - converts box to binary format
499 : */
500 : Datum
7271 tgl 501 UBC 0 : box_send(PG_FUNCTION_ARGS)
7271 tgl 502 EUB : {
7271 tgl 503 UBC 0 : BOX *box = PG_GETARG_BOX_P(0);
504 : StringInfoData buf;
505 :
506 0 : pq_begintypsend(&buf);
7271 tgl 507 UIC 0 : pq_sendfloat8(&buf, box->high.x);
508 0 : pq_sendfloat8(&buf, box->high.y);
509 0 : pq_sendfloat8(&buf, box->low.x);
510 0 : pq_sendfloat8(&buf, box->low.y);
511 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
512 : }
7271 tgl 513 EUB :
514 :
9345 bruce 515 : /* box_construct - fill in a new box.
516 : */
517 : static inline void
1715 tomas.vondra 518 GBC 130272 : box_construct(BOX *result, Point *pt1, Point *pt2)
9770 scrappy 519 EUB : {
1697 tomas.vondra 520 GBC 130272 : if (float8_gt(pt1->x, pt2->x))
9345 bruce 521 EUB : {
1715 tomas.vondra 522 GBC 9279 : result->high.x = pt1->x;
523 9279 : result->low.x = pt2->x;
524 : }
525 : else
526 : {
1715 tomas.vondra 527 GIC 120993 : result->high.x = pt2->x;
528 120993 : result->low.x = pt1->x;
529 : }
1697 tomas.vondra 530 CBC 130272 : if (float8_gt(pt1->y, pt2->y))
531 : {
1715 532 9297 : result->high.y = pt1->y;
1715 tomas.vondra 533 GIC 9297 : result->low.y = pt2->y;
9345 bruce 534 ECB : }
535 : else
536 : {
1715 tomas.vondra 537 GIC 120975 : result->high.y = pt2->y;
538 120975 : result->low.y = pt1->y;
9345 bruce 539 ECB : }
9770 scrappy 540 CBC 130272 : }
541 :
9770 scrappy 542 ECB :
543 : /*----------------------------------------------------------
9345 bruce 544 : * Relational operators for BOXes.
545 : * <, >, <=, >=, and == are based on box area.
546 : *---------------------------------------------------------*/
547 :
548 : /* box_same - are two boxes identical?
9770 scrappy 549 : */
8288 tgl 550 : Datum
8288 tgl 551 GIC 6880 : box_same(PG_FUNCTION_ARGS)
9770 scrappy 552 ECB : {
8288 tgl 553 GIC 6880 : BOX *box1 = PG_GETARG_BOX_P(0);
554 6880 : BOX *box2 = PG_GETARG_BOX_P(1);
555 :
1715 tomas.vondra 556 6880 : PG_RETURN_BOOL(point_eq_point(&box1->high, &box2->high) &&
557 : point_eq_point(&box1->low, &box2->low));
558 : }
559 :
560 : /* box_overlap - does box1 overlap box2?
561 : */
562 : Datum
8288 tgl 563 CBC 32367 : box_overlap(PG_FUNCTION_ARGS)
564 : {
565 32367 : BOX *box1 = PG_GETARG_BOX_P(0);
566 32367 : BOX *box2 = PG_GETARG_BOX_P(1);
567 :
568 32367 : PG_RETURN_BOOL(box_ov(box1, box2));
569 : }
570 :
571 : static bool
8288 tgl 572 GIC 738090 : box_ov(BOX *box1, BOX *box2)
573 : {
3712 574 1115022 : return (FPle(box1->low.x, box2->high.x) &&
3712 tgl 575 CBC 438393 : FPle(box2->low.x, box1->high.x) &&
3712 tgl 576 GIC 1176483 : FPle(box1->low.y, box2->high.y) &&
3712 tgl 577 CBC 49236 : FPle(box2->low.y, box1->high.y));
9770 scrappy 578 ECB : }
579 :
6498 tgl 580 : /* box_left - is box1 strictly left of box2?
581 : */
582 : Datum
6498 tgl 583 GIC 25011 : box_left(PG_FUNCTION_ARGS)
9770 scrappy 584 ECB : {
8288 tgl 585 GIC 25011 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 586 CBC 25011 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 587 ECB :
6498 tgl 588 CBC 25011 : PG_RETURN_BOOL(FPlt(box1->high.x, box2->low.x));
9770 scrappy 589 ECB : }
590 :
591 : /* box_overleft - is the right edge of box1 at or left of
592 : * the right edge of box2?
593 : *
594 : * This is "less than or equal" for the end of a time range,
6498 tgl 595 : * when time ranges are stored as rectangles.
596 : */
8288 597 : Datum
6498 tgl 598 CBC 49854 : box_overleft(PG_FUNCTION_ARGS)
599 : {
8288 600 49854 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 601 GIC 49854 : BOX *box2 = PG_GETARG_BOX_P(1);
602 :
6498 603 49854 : PG_RETURN_BOOL(FPle(box1->high.x, box2->high.x));
604 : }
605 :
606 : /* box_right - is box1 strictly right of box2?
607 : */
608 : Datum
8288 609 65871 : box_right(PG_FUNCTION_ARGS)
9770 scrappy 610 ECB : {
8288 tgl 611 GIC 65871 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 612 CBC 65871 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 613 ECB :
8288 tgl 614 GIC 65871 : PG_RETURN_BOOL(FPgt(box1->low.x, box2->high.x));
9770 scrappy 615 ECB : }
616 :
617 : /* box_overright - is the left edge of box1 at or right of
618 : * the left edge of box2?
619 : *
620 : * This is "greater than or equal" for time ranges, when time ranges
9345 bruce 621 : * are stored as rectangles.
622 : */
8288 tgl 623 : Datum
8288 tgl 624 CBC 56199 : box_overright(PG_FUNCTION_ARGS)
625 : {
626 56199 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 627 GIC 56199 : BOX *box2 = PG_GETARG_BOX_P(1);
628 :
629 56199 : PG_RETURN_BOOL(FPge(box1->low.x, box2->low.x));
630 : }
631 :
632 : /* box_below - is box1 strictly below box2?
633 : */
634 : Datum
6498 635 13839 : box_below(PG_FUNCTION_ARGS)
6498 tgl 636 ECB : {
6498 tgl 637 GIC 13839 : BOX *box1 = PG_GETARG_BOX_P(0);
6498 tgl 638 CBC 13839 : BOX *box2 = PG_GETARG_BOX_P(1);
6498 tgl 639 ECB :
6498 tgl 640 GIC 13839 : PG_RETURN_BOOL(FPlt(box1->high.y, box2->low.y));
6498 tgl 641 ECB : }
642 :
643 : /* box_overbelow - is the upper edge of box1 at or below
644 : * the upper edge of box2?
645 : */
646 : Datum
6498 tgl 647 CBC 40218 : box_overbelow(PG_FUNCTION_ARGS)
648 : {
649 40218 : BOX *box1 = PG_GETARG_BOX_P(0);
650 40218 : BOX *box2 = PG_GETARG_BOX_P(1);
651 :
652 40218 : PG_RETURN_BOOL(FPle(box1->high.y, box2->high.y));
653 : }
654 :
655 : /* box_above - is box1 strictly above box2?
656 : */
657 : Datum
6498 tgl 658 GIC 28860 : box_above(PG_FUNCTION_ARGS)
6498 tgl 659 ECB : {
6498 tgl 660 GIC 28860 : BOX *box1 = PG_GETARG_BOX_P(0);
6498 tgl 661 CBC 28860 : BOX *box2 = PG_GETARG_BOX_P(1);
6498 tgl 662 ECB :
6498 tgl 663 GIC 28860 : PG_RETURN_BOOL(FPgt(box1->low.y, box2->high.y));
6498 tgl 664 ECB : }
665 :
666 : /* box_overabove - is the lower edge of box1 at or above
667 : * the lower edge of box2?
668 : */
669 : Datum
6498 tgl 670 CBC 55575 : box_overabove(PG_FUNCTION_ARGS)
671 : {
672 55575 : BOX *box1 = PG_GETARG_BOX_P(0);
673 55575 : BOX *box2 = PG_GETARG_BOX_P(1);
674 :
675 55575 : PG_RETURN_BOOL(FPge(box1->low.y, box2->low.y));
676 : }
677 :
678 : /* box_contained - is box1 contained by box2?
679 : */
680 : Datum
8288 tgl 681 GIC 79146 : box_contained(PG_FUNCTION_ARGS)
9770 scrappy 682 ECB : {
8288 tgl 683 GIC 79146 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 684 CBC 79146 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 685 ECB :
1715 tomas.vondra 686 GIC 79146 : PG_RETURN_BOOL(box_contain_box(box2, box1));
9770 scrappy 687 ECB : }
688 :
689 : /* box_contain - does box1 contain box2?
690 : */
691 : Datum
8288 tgl 692 GIC 6126 : box_contain(PG_FUNCTION_ARGS)
9770 scrappy 693 ECB : {
8288 tgl 694 GIC 6126 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 695 CBC 6126 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 696 ECB :
1715 tomas.vondra 697 GIC 6126 : PG_RETURN_BOOL(box_contain_box(box1, box2));
1715 tomas.vondra 698 ECB : }
699 :
700 : /*
701 : * Check whether the second box is in the first box or on its border
702 : */
703 : static bool
1606 alvherre 704 CBC 127737 : box_contain_box(BOX *contains_box, BOX *contained_box)
705 : {
706 208776 : return FPge(contains_box->high.x, contained_box->high.x) &&
1418 tgl 707 138927 : FPle(contains_box->low.x, contained_box->low.x) &&
1418 tgl 708 GIC 266664 : FPge(contains_box->high.y, contained_box->high.y) &&
1418 tgl 709 CBC 48747 : FPle(contains_box->low.y, contained_box->low.y);
710 : }
711 :
712 :
713 : /* box_positionop -
714 : * is box1 entirely {above,below} box2?
715 : *
6498 tgl 716 ECB : * box_below_eq and box_above_eq are obsolete versions that (probably
717 : * erroneously) accept the equal-boundaries case. Since these are not
718 : * in sync with the box_left and box_right code, they are deprecated and
719 : * not supported in the PG 8.1 rtree operator class extension.
9770 scrappy 720 : */
8288 tgl 721 : Datum
6498 tgl 722 GIC 75 : box_below_eq(PG_FUNCTION_ARGS)
723 : {
8288 724 75 : BOX *box1 = PG_GETARG_BOX_P(0);
725 75 : BOX *box2 = PG_GETARG_BOX_P(1);
726 :
727 75 : PG_RETURN_BOOL(FPle(box1->high.y, box2->low.y));
728 : }
729 :
730 : Datum
6498 731 75 : box_above_eq(PG_FUNCTION_ARGS)
732 : {
8288 733 75 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 734 CBC 75 : BOX *box2 = PG_GETARG_BOX_P(1);
735 :
736 75 : PG_RETURN_BOOL(FPge(box1->low.y, box2->high.y));
9770 scrappy 737 ECB : }
738 :
739 :
740 : /* box_relop - is area(box1) relop area(box2), within
741 : * our accuracy constraint?
742 : */
8288 tgl 743 : Datum
8288 tgl 744 GIC 15 : box_lt(PG_FUNCTION_ARGS)
9770 scrappy 745 ECB : {
8288 tgl 746 CBC 15 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 747 GIC 15 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 748 ECB :
8288 tgl 749 GIC 15 : PG_RETURN_BOOL(FPlt(box_ar(box1), box_ar(box2)));
750 : }
751 :
752 : Datum
753 15 : box_gt(PG_FUNCTION_ARGS)
754 : {
755 15 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 756 CBC 15 : BOX *box2 = PG_GETARG_BOX_P(1);
757 :
758 15 : PG_RETURN_BOOL(FPgt(box_ar(box1), box_ar(box2)));
9770 scrappy 759 ECB : }
760 :
8288 tgl 761 : Datum
8288 tgl 762 GIC 15 : box_eq(PG_FUNCTION_ARGS)
763 : {
764 15 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 765 CBC 15 : BOX *box2 = PG_GETARG_BOX_P(1);
766 :
767 15 : PG_RETURN_BOOL(FPeq(box_ar(box1), box_ar(box2)));
9770 scrappy 768 ECB : }
769 :
8288 tgl 770 : Datum
8288 tgl 771 GIC 15 : box_le(PG_FUNCTION_ARGS)
772 : {
773 15 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 774 CBC 15 : BOX *box2 = PG_GETARG_BOX_P(1);
775 :
776 15 : PG_RETURN_BOOL(FPle(box_ar(box1), box_ar(box2)));
9770 scrappy 777 ECB : }
778 :
8288 tgl 779 : Datum
8288 tgl 780 GIC 15 : box_ge(PG_FUNCTION_ARGS)
781 : {
782 15 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 783 CBC 15 : BOX *box2 = PG_GETARG_BOX_P(1);
784 :
785 15 : PG_RETURN_BOOL(FPge(box_ar(box1), box_ar(box2)));
9770 scrappy 786 ECB : }
787 :
788 :
789 : /*----------------------------------------------------------
790 : * "Arithmetic" operators on boxes.
791 : *---------------------------------------------------------*/
792 :
793 : /* box_area - returns the area of the box.
794 : */
8288 tgl 795 : Datum
8288 tgl 796 GIC 15 : box_area(PG_FUNCTION_ARGS)
9770 scrappy 797 ECB : {
8288 tgl 798 GIC 15 : BOX *box = PG_GETARG_BOX_P(0);
799 :
800 15 : PG_RETURN_FLOAT8(box_ar(box));
801 : }
802 :
803 :
804 : /* box_width - returns the width of the box
805 : * (horizontal magnitude).
806 : */
807 : Datum
8288 tgl 808 CBC 15 : box_width(PG_FUNCTION_ARGS)
809 : {
810 15 : BOX *box = PG_GETARG_BOX_P(0);
811 :
1715 tomas.vondra 812 15 : PG_RETURN_FLOAT8(box_wd(box));
813 : }
814 :
815 :
816 : /* box_height - returns the height of the box
817 : * (vertical magnitude).
818 : */
819 : Datum
8288 tgl 820 15 : box_height(PG_FUNCTION_ARGS)
821 : {
822 15 : BOX *box = PG_GETARG_BOX_P(0);
823 :
1715 tomas.vondra 824 15 : PG_RETURN_FLOAT8(box_ht(box));
825 : }
826 :
827 :
828 : /* box_distance - returns the distance between the
829 : * center points of two boxes.
830 : */
831 : Datum
8288 tgl 832 75 : box_distance(PG_FUNCTION_ARGS)
833 : {
834 75 : BOX *box1 = PG_GETARG_BOX_P(0);
8288 tgl 835 GIC 75 : BOX *box2 = PG_GETARG_BOX_P(1);
8288 tgl 836 ECB : Point a,
837 : b;
838 :
8288 tgl 839 GIC 75 : box_cn(&a, box1);
840 75 : box_cn(&b, box2);
841 :
1715 tomas.vondra 842 75 : PG_RETURN_FLOAT8(point_dt(&a, &b));
843 : }
9770 scrappy 844 ECB :
845 :
9345 bruce 846 : /* box_center - returns the center point of the box.
9770 scrappy 847 : */
848 : Datum
8288 tgl 849 GIC 45 : box_center(PG_FUNCTION_ARGS)
850 : {
8288 tgl 851 CBC 45 : BOX *box = PG_GETARG_BOX_P(0);
852 45 : Point *result = (Point *) palloc(sizeof(Point));
853 :
854 45 : box_cn(result, box);
855 :
8288 tgl 856 GIC 45 : PG_RETURN_POINT_P(result);
857 : }
858 :
859 :
860 : /* box_ar - returns the area of the box.
9770 scrappy 861 ECB : */
862 : static float8
9344 bruce 863 CBC 165 : box_ar(BOX *box)
9770 scrappy 864 ECB : {
1697 tomas.vondra 865 GIC 165 : return float8_mul(box_wd(box), box_ht(box));
9770 scrappy 866 ECB : }
867 :
868 :
869 : /* box_cn - stores the centerpoint of the box into *center.
870 : */
871 : static void
8288 tgl 872 GIC 237 : box_cn(Point *center, BOX *box)
873 : {
1697 tomas.vondra 874 237 : center->x = float8_div(float8_pl(box->high.x, box->low.x), 2.0);
1697 tomas.vondra 875 CBC 237 : center->y = float8_div(float8_pl(box->high.y, box->low.y), 2.0);
8288 tgl 876 GIC 237 : }
8288 tgl 877 ECB :
878 :
879 : /* box_wd - returns the width (length) of the box
880 : * (horizontal magnitude).
881 : */
882 : static float8
9344 bruce 883 GIC 180 : box_wd(BOX *box)
9770 scrappy 884 ECB : {
1697 tomas.vondra 885 GIC 180 : return float8_mi(box->high.x, box->low.x);
9770 scrappy 886 ECB : }
887 :
888 :
889 : /* box_ht - returns the height of the box
890 : * (vertical magnitude).
891 : */
892 : static float8
9344 bruce 893 GIC 180 : box_ht(BOX *box)
894 : {
1697 tomas.vondra 895 CBC 180 : return float8_mi(box->high.y, box->low.y);
896 : }
9770 scrappy 897 ECB :
898 :
899 : /*----------------------------------------------------------
900 : * Funky operations.
901 : *---------------------------------------------------------*/
902 :
903 : /* box_intersect -
904 : * returns the overlapping portion of two boxes,
9345 bruce 905 : * or NULL if they do not intersect.
906 : */
8288 tgl 907 : Datum
8288 tgl 908 GIC 75 : box_intersect(PG_FUNCTION_ARGS)
909 : {
910 75 : BOX *box1 = PG_GETARG_BOX_P(0);
911 75 : BOX *box2 = PG_GETARG_BOX_P(1);
912 : BOX *result;
913 :
914 75 : if (!box_ov(box1, box2))
915 42 : PG_RETURN_NULL();
916 :
917 33 : result = (BOX *) palloc(sizeof(BOX));
918 :
1697 tomas.vondra 919 33 : result->high.x = float8_min(box1->high.x, box2->high.x);
1697 tomas.vondra 920 CBC 33 : result->low.x = float8_max(box1->low.x, box2->low.x);
1697 tomas.vondra 921 GIC 33 : result->high.y = float8_min(box1->high.y, box2->high.y);
1697 tomas.vondra 922 CBC 33 : result->low.y = float8_max(box1->low.y, box2->low.y);
9469 lockhart 923 ECB :
8288 tgl 924 GIC 33 : PG_RETURN_BOX_P(result);
925 : }
9770 scrappy 926 ECB :
927 :
928 : /* box_diagonal -
9345 bruce 929 : * returns a line segment which happens to be the
930 : * positive-slope diagonal of "box".
9770 scrappy 931 : */
8288 tgl 932 : Datum
8288 tgl 933 CBC 15 : box_diagonal(PG_FUNCTION_ARGS)
9770 scrappy 934 ECB : {
8288 tgl 935 GIC 15 : BOX *box = PG_GETARG_BOX_P(0);
8288 tgl 936 CBC 15 : LSEG *result = (LSEG *) palloc(sizeof(LSEG));
937 :
8288 tgl 938 GIC 15 : statlseg_construct(result, &box->high, &box->low);
939 :
940 15 : PG_RETURN_LSEG_P(result);
941 : }
942 :
943 : /***********************************************************************
944 : **
9345 bruce 945 ECB : ** Routines for 2D lines.
946 : **
9770 scrappy 947 : ***********************************************************************/
948 :
949 : static bool
116 tgl 950 GNC 69 : line_decode(char *s, const char *str, LINE *line, Node *escontext)
951 : {
2566 tgl 952 ECB : /* s was already advanced over leading '{' */
116 tgl 953 GNC 69 : if (!single_decode(s, &line->A, &s, "line", str, escontext))
116 tgl 954 UIC 0 : return false;
2566 tgl 955 GIC 66 : if (*s++ != DELIM)
116 tgl 956 GNC 3 : goto fail;
957 63 : if (!single_decode(s, &line->B, &s, "line", str, escontext))
3469 peter_e 958 UNC 0 : return false;
2566 tgl 959 GNC 63 : if (*s++ != DELIM)
116 960 9 : goto fail;
961 54 : if (!single_decode(s, &line->C, &s, "line", str, escontext))
3469 peter_e 962 GIC 12 : return false;
1715 tomas.vondra 963 42 : if (*s++ != RDELIM_L)
116 tgl 964 GNC 3 : goto fail;
2566 tgl 965 CBC 42 : while (isspace((unsigned char) *s))
2566 tgl 966 GIC 3 : s++;
967 39 : if (*s != '\0')
116 tgl 968 GNC 3 : goto fail;
3469 peter_e 969 GBC 36 : return true;
970 :
116 tgl 971 GNC 18 : fail:
972 18 : ereturn(escontext, false,
973 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
974 : errmsg("invalid input syntax for type %s: \"%s\"",
975 : "line", str)));
3469 peter_e 976 ECB : }
977 :
8288 tgl 978 : Datum
8288 tgl 979 GBC 105 : line_in(PG_FUNCTION_ARGS)
9101 lockhart 980 ECB : {
8288 tgl 981 CBC 105 : char *str = PG_GETARG_CSTRING(0);
116 tgl 982 GNC 105 : Node *escontext = fcinfo->context;
2566 tgl 983 CBC 105 : LINE *line = (LINE *) palloc(sizeof(LINE));
9101 lockhart 984 ECB : LSEG lseg;
2566 tgl 985 : bool isopen;
9101 lockhart 986 : char *s;
8986 bruce 987 :
2566 tgl 988 CBC 105 : s = str;
989 108 : while (isspace((unsigned char) *s))
990 3 : s++;
1715 tomas.vondra 991 105 : if (*s == LDELIM_L)
992 : {
116 tgl 993 GNC 69 : if (!line_decode(s + 1, str, line, escontext))
994 18 : PG_RETURN_NULL();
3469 peter_e 995 GIC 36 : if (FPzero(line->A) && FPzero(line->B))
116 tgl 996 GNC 9 : ereturn(escontext, (Datum) 0,
997 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
3469 peter_e 998 ECB : errmsg("invalid line specification: A and B cannot both be zero")));
999 : }
1000 : else
2566 tgl 1001 : {
116 tgl 1002 GNC 36 : if (!path_decode(s, true, 2, &lseg.p[0], &isopen, NULL, "line", str,
1003 : escontext))
1004 6 : PG_RETURN_NULL();
1715 tomas.vondra 1005 GIC 18 : if (point_eq_point(&lseg.p[0], &lseg.p[1]))
116 tgl 1006 GNC 3 : ereturn(escontext, (Datum) 0,
1007 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1008 : errmsg("invalid line specification: must be two distinct points")));
1009 :
1010 : /*
1011 : * XXX lseg_sl() and line_construct() can throw overflow/underflow
1012 : * errors. Eventually we should allow those to be soft, but the
1013 : * notational pain seems to outweigh the value for now.
1014 : */
1715 tomas.vondra 1015 CBC 15 : line_construct(line, &lseg.p[0], lseg_sl(&lseg));
2566 tgl 1016 ECB : }
9101 lockhart 1017 :
8288 tgl 1018 CBC 42 : PG_RETURN_LINE_P(line);
1019 : }
9101 lockhart 1020 ECB :
1021 :
8288 tgl 1022 : Datum
8288 tgl 1023 CBC 3482 : line_out(PG_FUNCTION_ARGS)
1024 : {
8288 tgl 1025 GIC 3482 : LINE *line = PG_GETARG_LINE_P(0);
2566 1026 3482 : char *astr = float8out_internal(line->A);
1027 3482 : char *bstr = float8out_internal(line->B);
1028 3482 : char *cstr = float8out_internal(line->C);
9101 lockhart 1029 ECB :
1715 tomas.vondra 1030 GIC 3482 : PG_RETURN_CSTRING(psprintf("%c%s%c%s%c%s%c", LDELIM_L, astr, DELIM, bstr,
1715 tomas.vondra 1031 ECB : DELIM, cstr, RDELIM_L));
8288 tgl 1032 : }
9101 lockhart 1033 :
1034 : /*
1035 : * line_recv - converts external binary format to line
1036 : */
1037 : Datum
7271 tgl 1038 UIC 0 : line_recv(PG_FUNCTION_ARGS)
1039 : {
3260 bruce 1040 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
1041 : LINE *line;
3469 peter_e 1042 ECB :
3469 peter_e 1043 UIC 0 : line = (LINE *) palloc(sizeof(LINE));
1044 :
3469 peter_e 1045 LBC 0 : line->A = pq_getmsgfloat8(buf);
3469 peter_e 1046 UIC 0 : line->B = pq_getmsgfloat8(buf);
1047 0 : line->C = pq_getmsgfloat8(buf);
1048 :
1656 tomas.vondra 1049 0 : if (FPzero(line->A) && FPzero(line->B))
1656 tomas.vondra 1050 LBC 0 : ereport(ERROR,
1051 : (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
1656 tomas.vondra 1052 ECB : errmsg("invalid line specification: A and B cannot both be zero")));
1053 :
3469 peter_e 1054 LBC 0 : PG_RETURN_LINE_P(line);
7271 tgl 1055 ECB : }
1056 :
1057 : /*
1058 : * line_send - converts line to binary format
1059 : */
1060 : Datum
7271 tgl 1061 UIC 0 : line_send(PG_FUNCTION_ARGS)
1062 : {
3469 peter_e 1063 0 : LINE *line = PG_GETARG_LINE_P(0);
1064 : StringInfoData buf;
3469 peter_e 1065 EUB :
3469 peter_e 1066 UIC 0 : pq_begintypsend(&buf);
3469 peter_e 1067 UBC 0 : pq_sendfloat8(&buf, line->A);
3469 peter_e 1068 UIC 0 : pq_sendfloat8(&buf, line->B);
1069 0 : pq_sendfloat8(&buf, line->C);
3469 peter_e 1070 UBC 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
1071 : }
7271 tgl 1072 EUB :
9101 lockhart 1073 :
9770 scrappy 1074 : /*----------------------------------------------------------
1075 : * Conversion routines from one line formula to internal.
9345 bruce 1076 : * Internal form: Ax+By+C=0
9770 scrappy 1077 : *---------------------------------------------------------*/
1078 :
1079 : /*
1080 : * Fill already-allocated LINE struct from the point and the slope
9101 lockhart 1081 : */
1082 : static inline void
1715 tomas.vondra 1083 GIC 3272730 : line_construct(LINE *result, Point *pt, float8 m)
1084 : {
869 tgl 1085 3272730 : if (isinf(m))
1086 : {
1087 : /* vertical - use "x = C" */
1697 tomas.vondra 1088 GBC 747348 : result->A = -1.0;
1697 tomas.vondra 1089 GIC 747348 : result->B = 0.0;
4533 tgl 1090 GBC 747348 : result->C = pt->x;
1091 : }
869 tgl 1092 GIC 2525382 : else if (m == 0)
869 tgl 1093 EUB : {
1094 : /* horizontal - use "y = C" */
869 tgl 1095 GBC 739209 : result->A = 0.0;
1096 739209 : result->B = -1.0;
1097 739209 : result->C = pt->y;
1098 : }
1099 : else
1100 : {
1101 : /* use "mx - y + yinter = 0" */
4533 tgl 1102 GIC 1786173 : result->A = m;
1103 1786173 : result->B = -1.0;
1697 tomas.vondra 1104 1786173 : result->C = float8_mi(pt->y, float8_mul(m, pt->x));
1105 : /* on some platforms, the preceding expression tends to produce -0 */
1715 1106 1786173 : if (result->C == 0.0)
1107 2430 : result->C = 0.0;
1108 : }
8288 tgl 1109 3272730 : }
8288 tgl 1110 ECB :
1111 : /* line_construct_pp()
1112 : * two points
1113 : */
1114 : Datum
8288 tgl 1115 CBC 270 : line_construct_pp(PG_FUNCTION_ARGS)
8288 tgl 1116 ECB : {
8288 tgl 1117 CBC 270 : Point *pt1 = PG_GETARG_POINT_P(0);
8288 tgl 1118 GIC 270 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1119 CBC 270 : LINE *result = (LINE *) palloc(sizeof(LINE));
1120 :
1656 tomas.vondra 1121 GIC 270 : if (point_eq_point(pt1, pt2))
1656 tomas.vondra 1122 CBC 3 : ereport(ERROR,
1656 tomas.vondra 1123 ECB : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
1124 : errmsg("invalid line specification: must be two distinct points")));
1125 :
1715 tomas.vondra 1126 GIC 267 : line_construct(result, pt1, point_sl(pt1, pt2));
1127 :
8288 tgl 1128 267 : PG_RETURN_LINE_P(result);
8288 tgl 1129 ECB : }
9770 scrappy 1130 :
1131 :
1132 : /*----------------------------------------------------------
9345 bruce 1133 : * Relative position routines.
9770 scrappy 1134 : *---------------------------------------------------------*/
1135 :
8288 tgl 1136 : Datum
8288 tgl 1137 GIC 300 : line_intersect(PG_FUNCTION_ARGS)
1138 : {
1139 300 : LINE *l1 = PG_GETARG_LINE_P(0);
1140 300 : LINE *l2 = PG_GETARG_LINE_P(1);
1141 :
1715 tomas.vondra 1142 CBC 300 : PG_RETURN_BOOL(line_interpt_line(NULL, l1, l2));
1143 : }
9770 scrappy 1144 ECB :
8288 tgl 1145 : Datum
8288 tgl 1146 CBC 300 : line_parallel(PG_FUNCTION_ARGS)
1147 : {
1148 300 : LINE *l1 = PG_GETARG_LINE_P(0);
1149 300 : LINE *l2 = PG_GETARG_LINE_P(1);
1150 :
1715 tomas.vondra 1151 GIC 300 : PG_RETURN_BOOL(!line_interpt_line(NULL, l1, l2));
1152 : }
9770 scrappy 1153 ECB :
1154 : Datum
8288 tgl 1155 CBC 300 : line_perp(PG_FUNCTION_ARGS)
1156 : {
8288 tgl 1157 GIC 300 : LINE *l1 = PG_GETARG_LINE_P(0);
1158 300 : LINE *l2 = PG_GETARG_LINE_P(1);
1159 :
9345 bruce 1160 300 : if (FPzero(l1->A))
8288 tgl 1161 90 : PG_RETURN_BOOL(FPzero(l2->B));
1656 tomas.vondra 1162 210 : if (FPzero(l2->A))
1163 63 : PG_RETURN_BOOL(FPzero(l1->B));
1656 tomas.vondra 1164 CBC 147 : if (FPzero(l1->B))
8288 tgl 1165 GIC 42 : PG_RETURN_BOOL(FPzero(l2->A));
1656 tomas.vondra 1166 CBC 105 : if (FPzero(l2->B))
1167 30 : PG_RETURN_BOOL(FPzero(l1->A));
1168 :
1169 75 : PG_RETURN_BOOL(FPeq(float8_div(float8_mul(l1->A, l2->A),
1170 : float8_mul(l1->B, l2->B)), -1.0));
1171 : }
1172 :
8288 tgl 1173 ECB : Datum
8288 tgl 1174 GIC 30 : line_vertical(PG_FUNCTION_ARGS)
9770 scrappy 1175 ECB : {
8288 tgl 1176 CBC 30 : LINE *line = PG_GETARG_LINE_P(0);
1177 :
1178 30 : PG_RETURN_BOOL(FPzero(line->B));
1179 : }
1180 :
1181 : Datum
1182 30 : line_horizontal(PG_FUNCTION_ARGS)
1183 : {
1184 30 : LINE *line = PG_GETARG_LINE_P(0);
9770 scrappy 1185 ECB :
8288 tgl 1186 GIC 30 : PG_RETURN_BOOL(FPzero(line->A));
8288 tgl 1187 ECB : }
1188 :
1697 tomas.vondra 1189 :
1190 : /*
1191 : * Check whether the two lines are the same
1192 : */
8288 tgl 1193 : Datum
8288 tgl 1194 CBC 306 : line_eq(PG_FUNCTION_ARGS)
1195 : {
1196 306 : LINE *l1 = PG_GETARG_LINE_P(0);
8288 tgl 1197 GIC 306 : LINE *l2 = PG_GETARG_LINE_P(1);
1198 : float8 ratio;
1199 :
1200 : /* If any NaNs are involved, insist on exact equality */
869 tgl 1201 CBC 306 : if (unlikely(isnan(l1->A) || isnan(l1->B) || isnan(l1->C) ||
1202 : isnan(l2->A) || isnan(l2->B) || isnan(l2->C)))
869 tgl 1203 ECB : {
869 tgl 1204 GIC 114 : PG_RETURN_BOOL(float8_eq(l1->A, l2->A) &&
869 tgl 1205 ECB : float8_eq(l1->B, l2->B) &&
1206 : float8_eq(l1->C, l2->C));
1207 : }
1208 :
1209 : /* Otherwise, lines whose parameters are proportional are the same */
869 tgl 1210 GIC 192 : if (!FPzero(l2->A))
1697 tomas.vondra 1211 CBC 120 : ratio = float8_div(l1->A, l2->A);
869 tgl 1212 GIC 72 : else if (!FPzero(l2->B))
1697 tomas.vondra 1213 CBC 72 : ratio = float8_div(l1->B, l2->B);
869 tgl 1214 UIC 0 : else if (!FPzero(l2->C))
1697 tomas.vondra 1215 0 : ratio = float8_div(l1->C, l2->C);
1216 : else
1217 0 : ratio = 1.0;
1218 :
869 tgl 1219 GIC 192 : PG_RETURN_BOOL(FPeq(l1->A, float8_mul(ratio, l2->A)) &&
1220 : FPeq(l1->B, float8_mul(ratio, l2->B)) &&
869 tgl 1221 ECB : FPeq(l1->C, float8_mul(ratio, l2->C)));
1222 : }
9345 bruce 1223 :
9770 scrappy 1224 :
1225 : /*----------------------------------------------------------
1226 : * Line arithmetic routines.
1227 : *---------------------------------------------------------*/
1228 :
1229 : /*
1230 : * Return slope of the line
1656 tomas.vondra 1231 : */
1232 : static inline float8
1656 tomas.vondra 1233 GIC 240 : line_sl(LINE *line)
1234 : {
1235 240 : if (FPzero(line->A))
1236 72 : return 0.0;
1656 tomas.vondra 1237 CBC 168 : if (FPzero(line->B))
869 tgl 1238 48 : return get_float8_infinity();
1656 tomas.vondra 1239 120 : return float8_div(line->A, -line->B);
1656 tomas.vondra 1240 ECB : }
1656 tomas.vondra 1241 EUB :
1242 :
1243 : /*
1715 1244 : * Return inverse slope of the line
1245 : */
1715 tomas.vondra 1246 ECB : static inline float8
1715 tomas.vondra 1247 GIC 896580 : line_invsl(LINE *line)
1248 : {
1249 896580 : if (FPzero(line->A))
869 tgl 1250 357660 : return get_float8_infinity();
1715 tomas.vondra 1251 538920 : if (FPzero(line->B))
1252 347802 : return 0.0;
1697 1253 191118 : return float8_div(line->B, line->A);
1254 : }
1255 :
1256 :
1257 : /* line_distance()
1258 : * Distance between two lines.
1259 : */
8288 tgl 1260 ECB : Datum
8288 tgl 1261 GIC 300 : line_distance(PG_FUNCTION_ARGS)
9345 bruce 1262 ECB : {
8288 tgl 1263 CBC 300 : LINE *l1 = PG_GETARG_LINE_P(0);
1264 300 : LINE *l2 = PG_GETARG_LINE_P(1);
1656 tomas.vondra 1265 ECB : float8 ratio;
9345 bruce 1266 :
1715 tomas.vondra 1267 GIC 300 : if (line_interpt_line(NULL, l1, l2)) /* intersecting? */
8288 tgl 1268 252 : PG_RETURN_FLOAT8(0.0);
1269 :
1656 tomas.vondra 1270 48 : if (!FPzero(l1->A) && !isnan(l1->A) && !FPzero(l2->A) && !isnan(l2->A))
1271 21 : ratio = float8_div(l1->A, l2->A);
1272 27 : else if (!FPzero(l1->B) && !isnan(l1->B) && !FPzero(l2->B) && !isnan(l2->B))
1273 27 : ratio = float8_div(l1->B, l2->B);
1656 tomas.vondra 1274 ECB : else
1656 tomas.vondra 1275 UIC 0 : ratio = 1.0;
1656 tomas.vondra 1276 ECB :
1656 tomas.vondra 1277 CBC 48 : PG_RETURN_FLOAT8(float8_div(fabs(float8_mi(l1->C,
1656 tomas.vondra 1278 ECB : float8_mul(ratio, l2->C))),
1279 : HYPOT(l1->A, l1->B)));
9770 scrappy 1280 : }
1281 :
1282 : /* line_interpt()
1283 : * Point where two lines l1, l2 intersect (if any)
1284 : */
1285 : Datum
8288 tgl 1286 GIC 300 : line_interpt(PG_FUNCTION_ARGS)
1287 : {
8288 tgl 1288 CBC 300 : LINE *l1 = PG_GETARG_LINE_P(0);
8288 tgl 1289 GIC 300 : LINE *l2 = PG_GETARG_LINE_P(1);
8288 tgl 1290 ECB : Point *result;
1291 :
1715 tomas.vondra 1292 GIC 300 : result = (Point *) palloc(sizeof(Point));
1293 :
1715 tomas.vondra 1294 CBC 300 : if (!line_interpt_line(result, l1, l2))
8288 tgl 1295 48 : PG_RETURN_NULL();
8288 tgl 1296 GIC 252 : PG_RETURN_POINT_P(result);
8288 tgl 1297 ECB : }
1298 :
1299 : /*
1300 : * Internal version of line_interpt
1301 : *
1606 alvherre 1302 EUB : * Return whether two lines intersect. If *result is not NULL, it is set to
1303 : * the intersection point.
1715 tomas.vondra 1304 ECB : *
1305 : * NOTE: If the lines are identical then we will find they are parallel
1306 : * and report "no intersection". This is a little weird, but since
1307 : * there's no *unique* intersection, maybe it's appropriate behavior.
1308 : *
1309 : * If the lines have NaN constants, we will return true, and the intersection
1310 : * point would have NaN coordinates. We shouldn't return false in this case
1311 : * because that would mean the lines are parallel.
1312 : */
1313 : static bool
1715 tomas.vondra 1314 GIC 2086425 : line_interpt_line(Point *result, LINE *l1, LINE *l2)
9770 scrappy 1315 ECB : {
1697 tomas.vondra 1316 : float8 x,
1317 : y;
1318 :
1656 tomas.vondra 1319 CBC 2086425 : if (!FPzero(l1->B))
1320 : {
1321 1518225 : if (FPeq(l2->A, float8_mul(l1->A, float8_div(l2->B, l1->B))))
1715 1322 4794 : return false;
1715 tomas.vondra 1323 ECB :
1656 tomas.vondra 1324 GIC 1513431 : x = float8_div(float8_mi(float8_mul(l1->B, l2->C),
1325 : float8_mul(l2->B, l1->C)),
1326 : float8_mi(float8_mul(l1->A, l2->B),
1327 : float8_mul(l2->A, l1->B)));
1328 1513431 : y = float8_div(-float8_pl(float8_mul(l1->A, x), l1->C), l1->B);
1329 : }
1330 568200 : else if (!FPzero(l2->B))
1331 : {
1332 566721 : if (FPeq(l1->A, float8_mul(l2->A, float8_div(l1->B, l2->B))))
1715 tomas.vondra 1333 UIC 0 : return false;
1334 :
1656 tomas.vondra 1335 GIC 566721 : x = float8_div(float8_mi(float8_mul(l2->B, l1->C),
1336 : float8_mul(l1->B, l2->C)),
1337 : float8_mi(float8_mul(l2->A, l1->B),
1338 : float8_mul(l1->A, l2->B)));
1339 566721 : y = float8_div(-float8_pl(float8_mul(l2->A, x), l2->C), l2->B);
1340 : }
1656 tomas.vondra 1341 ECB : else
1656 tomas.vondra 1342 GIC 1479 : return false;
1343 :
1344 : /* On some platforms, the preceding expressions tend to produce -0. */
1345 2080152 : if (x == 0.0)
1656 tomas.vondra 1346 CBC 60855 : x = 0.0;
1656 tomas.vondra 1347 GIC 2080152 : if (y == 0.0)
1656 tomas.vondra 1348 CBC 59964 : y = 0.0;
9385 lockhart 1349 ECB :
1715 tomas.vondra 1350 GIC 2080152 : if (result != NULL)
1715 tomas.vondra 1351 CBC 2079396 : point_construct(result, x, y);
1352 :
1715 tomas.vondra 1353 GIC 2080152 : return true;
1354 : }
9385 lockhart 1355 ECB :
1356 :
9770 scrappy 1357 : /***********************************************************************
1358 : **
9345 bruce 1359 : ** Routines for 2D paths (sequences of line segments, also
9345 bruce 1360 EUB : ** called `polylines').
1361 : **
9345 bruce 1362 ECB : ** This is not a general package for geometric paths,
1363 : ** which of course include polygons; the emphasis here
1364 : ** is on (for example) usefulness in wire layout.
1365 : **
9770 scrappy 1366 : ***********************************************************************/
1367 :
1368 : /*----------------------------------------------------------
9345 bruce 1369 : * String to path / path to string conversion.
1370 : * External format:
1371 : * "((xcoord, ycoord),... )"
1372 : * "[(xcoord, ycoord),... ]"
1373 : * "(xcoord, ycoord),... "
1374 : * "[xcoord, ycoord,... ]"
1375 : * Also support older format:
1376 : * "(closed, npts, xcoord, ycoord,... )"
9770 scrappy 1377 : *---------------------------------------------------------*/
1378 :
1379 : Datum
6892 bruce 1380 CBC 27 : path_area(PG_FUNCTION_ARGS)
1381 : {
6797 bruce 1382 GIC 27 : PATH *path = PG_GETARG_PATH_P(0);
1697 tomas.vondra 1383 27 : float8 area = 0.0;
1384 : int i,
1385 : j;
1386 :
6892 bruce 1387 27 : if (!path->closed)
1388 12 : PG_RETURN_NULL();
1389 :
6797 1390 42 : for (i = 0; i < path->npts; i++)
1391 : {
6892 1392 27 : j = (i + 1) % path->npts;
1697 tomas.vondra 1393 27 : area = float8_pl(area, float8_mul(path->p[i].x, path->p[j].y));
1394 27 : area = float8_mi(area, float8_mul(path->p[i].y, path->p[j].x));
1395 : }
1396 :
1397 15 : PG_RETURN_FLOAT8(float8_div(fabs(area), 2.0));
1398 : }
1399 :
1400 :
1401 : Datum
8289 tgl 1402 15461 : path_in(PG_FUNCTION_ARGS)
1403 : {
1404 15461 : char *str = PG_GETARG_CSTRING(0);
116 tgl 1405 GNC 15461 : Node *escontext = fcinfo->context;
1406 : PATH *path;
1407 : bool isopen;
9344 bruce 1408 ECB : char *s;
1409 : int npts;
1410 : int size;
3338 noah 1411 : int base_size;
9344 bruce 1412 GIC 15461 : int depth = 0;
1413 :
9345 1414 15461 : if ((npts = pair_count(str, ',')) <= 0)
116 tgl 1415 GNC 9 : ereturn(escontext, (Datum) 0,
7196 tgl 1416 ECB : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1417 : errmsg("invalid input syntax for type %s: \"%s\"",
2566 1418 : "path", str)));
1419 :
9345 bruce 1420 CBC 15452 : s = str;
8162 tgl 1421 15458 : while (isspace((unsigned char) *s))
9345 bruce 1422 6 : s++;
1423 :
1424 : /* skip single leading paren */
1425 15452 : if ((*s == LDELIM) && (strrchr(s, LDELIM) == s))
1426 : {
9345 bruce 1427 GIC 12 : s++;
1428 12 : depth++;
1429 : }
9483 scrappy 1430 ECB :
3338 noah 1431 GIC 15452 : base_size = sizeof(path->p[0]) * npts;
2118 tgl 1432 CBC 15452 : size = offsetof(PATH, p) + base_size;
3338 noah 1433 ECB :
1434 : /* Check for integer overflow */
3338 noah 1435 GIC 15452 : if (base_size / npts != sizeof(path->p[0]) || size <= base_size)
116 tgl 1436 UNC 0 : ereturn(escontext, (Datum) 0,
1437 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1438 : errmsg("too many points requested")));
1439 :
8288 tgl 1440 CBC 15452 : path = (PATH *) palloc(size);
1441 :
5885 1442 15452 : SET_VARSIZE(path, size);
9345 bruce 1443 15452 : path->npts = npts;
1444 :
116 tgl 1445 GNC 15452 : if (!path_decode(s, true, npts, &(path->p[0]), &isopen, &s, "path", str,
1446 : escontext))
1447 6 : PG_RETURN_NULL();
1448 :
2566 tgl 1449 GIC 15440 : if (depth >= 1)
2566 tgl 1450 ECB : {
2566 tgl 1451 CBC 12 : if (*s++ != RDELIM)
116 tgl 1452 GNC 3 : ereturn(escontext, (Datum) 0,
1453 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1454 : errmsg("invalid input syntax for type %s: \"%s\"",
2566 tgl 1455 ECB : "path", str)));
2566 tgl 1456 GIC 12 : while (isspace((unsigned char) *s))
2566 tgl 1457 CBC 3 : s++;
2566 tgl 1458 ECB : }
2566 tgl 1459 GIC 15437 : if (*s != '\0')
116 tgl 1460 GNC 3 : ereturn(escontext, (Datum) 0,
7196 tgl 1461 ECB : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2566 1462 : errmsg("invalid input syntax for type %s: \"%s\"",
1463 : "path", str)));
1464 :
9345 bruce 1465 CBC 15434 : path->closed = (!isopen);
5476 tgl 1466 EUB : /* prevent instability in unused pad bytes */
5476 tgl 1467 GIC 15434 : path->dummy = 0;
1468 :
8289 1469 15434 : PG_RETURN_PATH_P(path);
8289 tgl 1470 ECB : }
1471 :
9770 scrappy 1472 :
8289 tgl 1473 : Datum
8289 tgl 1474 GIC 30027 : path_out(PG_FUNCTION_ARGS)
9770 scrappy 1475 ECB : {
8289 tgl 1476 GIC 30027 : PATH *path = PG_GETARG_PATH_P(0);
9483 scrappy 1477 ECB :
3562 peter_e 1478 GIC 30027 : PG_RETURN_CSTRING(path_encode(path->closed ? PATH_CLOSED : PATH_OPEN, path->npts, path->p));
8289 tgl 1479 ECB : }
1480 :
7271 1481 : /*
1482 : * path_recv - converts external binary format to path
1483 : *
1484 : * External representation is closed flag (a boolean byte), int32 number
1485 : * of points, and the points.
1486 : */
1487 : Datum
7271 tgl 1488 UIC 0 : path_recv(PG_FUNCTION_ARGS)
7271 tgl 1489 ECB : {
7271 tgl 1490 LBC 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
1491 : PATH *path;
1492 : int closed;
1493 : int32 npts;
1494 : int32 i;
7271 tgl 1495 ECB : int size;
1496 :
7271 tgl 1497 LBC 0 : closed = pq_getmsgbyte(buf);
7271 tgl 1498 UIC 0 : npts = pq_getmsgint(buf, sizeof(int32));
2970 tgl 1499 LBC 0 : if (npts <= 0 || npts >= (int32) ((INT_MAX - offsetof(PATH, p)) / sizeof(Point)))
7196 tgl 1500 UIC 0 : ereport(ERROR,
1501 : (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
1502 : errmsg("invalid number of points in external \"path\" value")));
1503 :
2118 tgl 1504 LBC 0 : size = offsetof(PATH, p) + sizeof(path->p[0]) * npts;
7271 tgl 1505 UIC 0 : path = (PATH *) palloc(size);
7271 tgl 1506 ECB :
5885 tgl 1507 UIC 0 : SET_VARSIZE(path, size);
7271 tgl 1508 LBC 0 : path->npts = npts;
7271 tgl 1509 UIC 0 : path->closed = (closed ? 1 : 0);
1510 : /* prevent instability in unused pad bytes */
4365 1511 0 : path->dummy = 0;
1512 :
7271 1513 0 : for (i = 0; i < npts; i++)
1514 : {
1515 0 : path->p[i].x = pq_getmsgfloat8(buf);
1516 0 : path->p[i].y = pq_getmsgfloat8(buf);
1517 : }
7271 tgl 1518 EUB :
7271 tgl 1519 UIC 0 : PG_RETURN_PATH_P(path);
7271 tgl 1520 EUB : }
1521 :
1522 : /*
1523 : * path_send - converts path to binary format
1524 : */
1525 : Datum
7271 tgl 1526 UIC 0 : path_send(PG_FUNCTION_ARGS)
7271 tgl 1527 EUB : {
7271 tgl 1528 UBC 0 : PATH *path = PG_GETARG_PATH_P(0);
7271 tgl 1529 EUB : StringInfoData buf;
1530 : int32 i;
1531 :
7271 tgl 1532 UIC 0 : pq_begintypsend(&buf);
1533 0 : pq_sendbyte(&buf, path->closed ? 1 : 0);
2006 andres 1534 UBC 0 : pq_sendint32(&buf, path->npts);
7271 tgl 1535 0 : for (i = 0; i < path->npts; i++)
1536 : {
1537 0 : pq_sendfloat8(&buf, path->p[i].x);
1538 0 : pq_sendfloat8(&buf, path->p[i].y);
7271 tgl 1539 EUB : }
7271 tgl 1540 UIC 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
7271 tgl 1541 EUB : }
1542 :
9770 scrappy 1543 :
1544 : /*----------------------------------------------------------
9345 bruce 1545 : * Relational operators.
1546 : * These are based on the path cardinality,
1547 : * as stupid as that sounds.
1548 : *
1549 : * Better relops and access methods coming soon.
1550 : *---------------------------------------------------------*/
1551 :
1552 : Datum
8289 tgl 1553 GIC 243 : path_n_lt(PG_FUNCTION_ARGS)
1554 : {
1555 243 : PATH *p1 = PG_GETARG_PATH_P(0);
8289 tgl 1556 GBC 243 : PATH *p2 = PG_GETARG_PATH_P(1);
1557 :
1558 243 : PG_RETURN_BOOL(p1->npts < p2->npts);
1559 : }
1560 :
1561 : Datum
1562 243 : path_n_gt(PG_FUNCTION_ARGS)
9770 scrappy 1563 EUB : {
8289 tgl 1564 GBC 243 : PATH *p1 = PG_GETARG_PATH_P(0);
1565 243 : PATH *p2 = PG_GETARG_PATH_P(1);
1566 :
1567 243 : PG_RETURN_BOOL(p1->npts > p2->npts);
9770 scrappy 1568 EUB : }
1569 :
8289 tgl 1570 : Datum
8289 tgl 1571 GIC 244 : path_n_eq(PG_FUNCTION_ARGS)
1572 : {
1573 244 : PATH *p1 = PG_GETARG_PATH_P(0);
1574 244 : PATH *p2 = PG_GETARG_PATH_P(1);
1575 :
1576 244 : PG_RETURN_BOOL(p1->npts == p2->npts);
1577 : }
1578 :
1579 : Datum
1580 243 : path_n_le(PG_FUNCTION_ARGS)
1581 : {
1582 243 : PATH *p1 = PG_GETARG_PATH_P(0);
8289 tgl 1583 CBC 243 : PATH *p2 = PG_GETARG_PATH_P(1);
1584 :
1585 243 : PG_RETURN_BOOL(p1->npts <= p2->npts);
9770 scrappy 1586 ECB : }
1587 :
8289 tgl 1588 : Datum
8289 tgl 1589 GIC 243 : path_n_ge(PG_FUNCTION_ARGS)
1590 : {
1591 243 : PATH *p1 = PG_GETARG_PATH_P(0);
8289 tgl 1592 CBC 243 : PATH *p2 = PG_GETARG_PATH_P(1);
1593 :
1594 243 : PG_RETURN_BOOL(p1->npts >= p2->npts);
8289 tgl 1595 ECB : }
1596 :
9483 scrappy 1597 : /*----------------------------------------------------------
1598 : * Conversion operators.
1599 : *---------------------------------------------------------*/
1600 :
8289 tgl 1601 : Datum
8289 tgl 1602 GIC 81 : path_isclosed(PG_FUNCTION_ARGS)
9483 scrappy 1603 ECB : {
8289 tgl 1604 CBC 81 : PATH *path = PG_GETARG_PATH_P(0);
1605 :
1606 81 : PG_RETURN_BOOL(path->closed);
1607 : }
1608 :
1609 : Datum
1610 57 : path_isopen(PG_FUNCTION_ARGS)
1611 : {
1612 57 : PATH *path = PG_GETARG_PATH_P(0);
9483 scrappy 1613 ECB :
8053 bruce 1614 GIC 57 : PG_RETURN_BOOL(!path->closed);
8289 tgl 1615 ECB : }
1616 :
1617 : Datum
8289 tgl 1618 GIC 2715 : path_npoints(PG_FUNCTION_ARGS)
9483 scrappy 1619 ECB : {
8289 tgl 1620 GIC 2715 : PATH *path = PG_GETARG_PATH_P(0);
9441 lockhart 1621 ECB :
8289 tgl 1622 CBC 2715 : PG_RETURN_INT32(path->npts);
1623 : }
9483 scrappy 1624 ECB :
1625 :
1626 : Datum
8289 tgl 1627 GIC 39 : path_close(PG_FUNCTION_ARGS)
1628 : {
1629 39 : PATH *path = PG_GETARG_PATH_P_COPY(0);
1630 :
2062 peter_e 1631 39 : path->closed = true;
9483 scrappy 1632 ECB :
8289 tgl 1633 GIC 39 : PG_RETURN_PATH_P(path);
8289 tgl 1634 ECB : }
1635 :
1636 : Datum
8289 tgl 1637 GIC 27 : path_open(PG_FUNCTION_ARGS)
1638 : {
1639 27 : PATH *path = PG_GETARG_PATH_P_COPY(0);
9483 scrappy 1640 ECB :
2062 peter_e 1641 GIC 27 : path->closed = false;
9483 scrappy 1642 ECB :
8289 tgl 1643 GIC 27 : PG_RETURN_PATH_P(path);
8289 tgl 1644 ECB : }
1645 :
1646 :
1647 : /* path_inter -
9345 bruce 1648 : * Does p1 intersect p2 at any point?
1649 : * Use bounding boxes for a quick (O(n)) check, then do a
1650 : * O(n^2) iterative edge check.
1651 : */
8289 tgl 1652 : Datum
8289 tgl 1653 GIC 690459 : path_inter(PG_FUNCTION_ARGS)
1654 : {
1655 690459 : PATH *p1 = PG_GETARG_PATH_P(0);
1656 690459 : PATH *p2 = PG_GETARG_PATH_P(1);
9344 bruce 1657 ECB : BOX b1,
1658 : b2;
1659 : int i,
1660 : j;
1661 : LSEG seg1,
1662 : seg2;
9345 1663 :
1715 tomas.vondra 1664 GIC 690459 : Assert(p1->npts > 0 && p2->npts > 0);
1665 :
9345 bruce 1666 690459 : b1.high.x = b1.low.x = p1->p[0].x;
9345 bruce 1667 CBC 690459 : b1.high.y = b1.low.y = p1->p[0].y;
9345 bruce 1668 GIC 2626050 : for (i = 1; i < p1->npts; i++)
9345 bruce 1669 ECB : {
1697 tomas.vondra 1670 GIC 1935591 : b1.high.x = float8_max(p1->p[i].x, b1.high.x);
1697 tomas.vondra 1671 CBC 1935591 : b1.high.y = float8_max(p1->p[i].y, b1.high.y);
1697 tomas.vondra 1672 GIC 1935591 : b1.low.x = float8_min(p1->p[i].x, b1.low.x);
1697 tomas.vondra 1673 CBC 1935591 : b1.low.y = float8_min(p1->p[i].y, b1.low.y);
1674 : }
9345 bruce 1675 GIC 690459 : b2.high.x = b2.low.x = p2->p[0].x;
1676 690459 : b2.high.y = b2.low.y = p2->p[0].y;
1677 1975662 : for (i = 1; i < p2->npts; i++)
1678 : {
1697 tomas.vondra 1679 1285203 : b2.high.x = float8_max(p2->p[i].x, b2.high.x);
1680 1285203 : b2.high.y = float8_max(p2->p[i].y, b2.high.y);
1681 1285203 : b2.low.x = float8_min(p2->p[i].x, b2.low.x);
1682 1285203 : b2.low.y = float8_min(p2->p[i].y, b2.low.y);
9345 bruce 1683 ECB : }
8288 tgl 1684 GIC 690459 : if (!box_ov(&b1, &b2))
8289 tgl 1685 CBC 673710 : PG_RETURN_BOOL(false);
9345 bruce 1686 ECB :
1687 : /* pairwise check lseg intersections */
7848 tgl 1688 GIC 82506 : for (i = 0; i < p1->npts; i++)
1689 : {
1690 : int iprev;
1691 :
1692 69444 : if (i > 0)
7836 bruce 1693 52695 : iprev = i - 1;
7848 tgl 1694 ECB : else
1695 : {
7848 tgl 1696 CBC 16749 : if (!p1->closed)
1697 3993 : continue;
2118 1698 12756 : iprev = p1->npts - 1; /* include the closure segment */
1699 : }
7848 tgl 1700 ECB :
7848 tgl 1701 CBC 217833 : for (j = 0; j < p2->npts; j++)
7848 tgl 1702 ECB : {
7836 bruce 1703 : int jprev;
1704 :
7848 tgl 1705 CBC 156069 : if (j > 0)
7836 bruce 1706 90618 : jprev = j - 1;
7848 tgl 1707 ECB : else
1708 : {
7848 tgl 1709 CBC 65451 : if (!p2->closed)
1710 61869 : continue;
7836 bruce 1711 3582 : jprev = p2->npts - 1; /* include the closure segment */
7848 tgl 1712 ECB : }
1713 :
7848 tgl 1714 CBC 94200 : statlseg_construct(&seg1, &p1->p[iprev], &p1->p[i]);
1715 94200 : statlseg_construct(&seg2, &p2->p[jprev], &p2->p[j]);
1715 tomas.vondra 1716 GIC 94200 : if (lseg_interpt_lseg(NULL, &seg1, &seg2))
8289 tgl 1717 3687 : PG_RETURN_BOOL(true);
9345 bruce 1718 ECB : }
1719 : }
1720 :
1721 : /* if we dropped through, no two segs intersected */
8289 tgl 1722 CBC 13062 : PG_RETURN_BOOL(false);
8289 tgl 1723 ECB : }
1724 :
1725 : /* path_distance()
9196 lockhart 1726 : * This essentially does a cartesian product of the lsegs in the
8288 tgl 1727 : * two paths, and finds the min distance between any two lsegs
9196 lockhart 1728 : */
1729 : Datum
8289 tgl 1730 GIC 243 : path_distance(PG_FUNCTION_ARGS)
9770 scrappy 1731 ECB : {
8289 tgl 1732 GIC 243 : PATH *p1 = PG_GETARG_PATH_P(0);
1733 243 : PATH *p2 = PG_GETARG_PATH_P(1);
8288 1734 243 : float8 min = 0.0; /* initialize to keep compiler quiet */
7848 tgl 1735 CBC 243 : bool have_min = false;
8289 tgl 1736 ECB : float8 tmp;
1737 : int i,
1738 : j;
9344 bruce 1739 : LSEG seg1,
1740 : seg2;
9483 scrappy 1741 :
7848 tgl 1742 GIC 756 : for (i = 0; i < p1->npts; i++)
1743 : {
7836 bruce 1744 ECB : int iprev;
7848 tgl 1745 :
7848 tgl 1746 CBC 513 : if (i > 0)
7836 bruce 1747 270 : iprev = i - 1;
1748 : else
1749 : {
7848 tgl 1750 GIC 243 : if (!p1->closed)
1751 108 : continue;
2118 tgl 1752 CBC 135 : iprev = p1->npts - 1; /* include the closure segment */
1753 : }
1754 :
7848 tgl 1755 GIC 1260 : for (j = 0; j < p2->npts; j++)
1756 : {
1757 : int jprev;
1758 :
1759 855 : if (j > 0)
7836 bruce 1760 CBC 450 : jprev = j - 1;
1761 : else
7848 tgl 1762 ECB : {
7848 tgl 1763 CBC 405 : if (!p2->closed)
1764 180 : continue;
7836 bruce 1765 225 : jprev = p2->npts - 1; /* include the closure segment */
1766 : }
1767 :
7848 tgl 1768 GIC 675 : statlseg_construct(&seg1, &p1->p[iprev], &p1->p[i]);
1769 675 : statlseg_construct(&seg2, &p2->p[jprev], &p2->p[j]);
1770 :
1715 tomas.vondra 1771 675 : tmp = lseg_closept_lseg(NULL, &seg1, &seg2);
1697 tomas.vondra 1772 CBC 675 : if (!have_min || float8_lt(tmp, min))
1773 : {
8288 tgl 1774 GIC 291 : min = tmp;
1775 291 : have_min = true;
9345 bruce 1776 ECB : }
9347 1777 : }
1778 : }
1779 :
8053 bruce 1780 CBC 243 : if (!have_min)
8289 tgl 1781 LBC 0 : PG_RETURN_NULL();
9483 scrappy 1782 ECB :
8288 tgl 1783 GIC 243 : PG_RETURN_FLOAT8(min);
1784 : }
9770 scrappy 1785 ECB :
1786 :
1787 : /*----------------------------------------------------------
1788 : * "Arithmetic" operations.
1789 : *---------------------------------------------------------*/
1790 :
1791 : Datum
8289 tgl 1792 GIC 27 : path_length(PG_FUNCTION_ARGS)
9770 scrappy 1793 ECB : {
8289 tgl 1794 CBC 27 : PATH *path = PG_GETARG_PATH_P(0);
7848 1795 27 : float8 result = 0.0;
1796 : int i;
1797 :
1798 84 : for (i = 0; i < path->npts; i++)
7848 tgl 1799 ECB : {
1800 : int iprev;
1801 :
7848 tgl 1802 CBC 57 : if (i > 0)
7836 bruce 1803 GIC 30 : iprev = i - 1;
7848 tgl 1804 ECB : else
1805 : {
7848 tgl 1806 GIC 27 : if (!path->closed)
1807 12 : continue;
2118 1808 15 : iprev = path->npts - 1; /* include the closure segment */
1809 : }
7848 tgl 1810 ECB :
1697 tomas.vondra 1811 GBC 45 : result = float8_pl(result, point_dt(&path->p[iprev], &path->p[i]));
1812 : }
9345 bruce 1813 ECB :
8289 tgl 1814 GIC 27 : PG_RETURN_FLOAT8(result);
1815 : }
1816 :
1817 : /***********************************************************************
1818 : **
1819 : ** Routines for 2D points.
1820 : **
1821 : ***********************************************************************/
9770 scrappy 1822 ECB :
1823 : /*----------------------------------------------------------
9345 bruce 1824 : * String to point, point to string conversion.
1825 : * External format:
1826 : * "(x,y)"
1827 : * "x,y"
9770 scrappy 1828 : *---------------------------------------------------------*/
1829 :
1830 : Datum
8288 tgl 1831 GIC 863 : point_in(PG_FUNCTION_ARGS)
9770 scrappy 1832 ECB : {
8288 tgl 1833 CBC 863 : char *str = PG_GETARG_CSTRING(0);
2566 tgl 1834 GIC 863 : Point *point = (Point *) palloc(sizeof(Point));
1835 :
1836 : /* Ignore failure from pair_decode, since our return value won't matter */
116 tgl 1837 GNC 863 : pair_decode(str, &point->x, &point->y, NULL, "point", str, fcinfo->context);
8288 tgl 1838 CBC 848 : PG_RETURN_POINT_P(point);
8288 tgl 1839 ECB : }
1840 :
1841 : Datum
8288 tgl 1842 CBC 129934 : point_out(PG_FUNCTION_ARGS)
1843 : {
8288 tgl 1844 GIC 129934 : Point *pt = PG_GETARG_POINT_P(0);
9483 scrappy 1845 ECB :
3562 peter_e 1846 GIC 129934 : PG_RETURN_CSTRING(path_encode(PATH_NONE, 1, pt));
1847 : }
1848 :
1849 : /*
1850 : * point_recv - converts external binary format to point
1851 : */
1852 : Datum
7275 tgl 1853 9 : point_recv(PG_FUNCTION_ARGS)
1854 : {
1855 9 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
1856 : Point *point;
1857 :
1858 9 : point = (Point *) palloc(sizeof(Point));
1859 9 : point->x = pq_getmsgfloat8(buf);
1860 9 : point->y = pq_getmsgfloat8(buf);
1861 9 : PG_RETURN_POINT_P(point);
7275 tgl 1862 ECB : }
1863 :
1864 : /*
1865 : * point_send - converts point to binary format
1866 : */
1867 : Datum
7275 tgl 1868 CBC 9 : point_send(PG_FUNCTION_ARGS)
7275 tgl 1869 ECB : {
7275 tgl 1870 GIC 9 : Point *pt = PG_GETARG_POINT_P(0);
1871 : StringInfoData buf;
1872 :
7275 tgl 1873 CBC 9 : pq_begintypsend(&buf);
7275 tgl 1874 GIC 9 : pq_sendfloat8(&buf, pt->x);
7275 tgl 1875 CBC 9 : pq_sendfloat8(&buf, pt->y);
7275 tgl 1876 GIC 9 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
7275 tgl 1877 ECB : }
1878 :
1879 :
1880 : /*
1881 : * Initialize a point
1882 : */
1883 : static inline void
1715 tomas.vondra 1884 CBC 2610679 : point_construct(Point *result, float8 x, float8 y)
1885 : {
9345 bruce 1886 2610679 : result->x = x;
9345 bruce 1887 GIC 2610679 : result->y = y;
9770 scrappy 1888 2610679 : }
9770 scrappy 1889 ECB :
1890 :
1891 : /*----------------------------------------------------------
9345 bruce 1892 : * Relational operators for Points.
1893 : * Since we do have a sense of coordinates being
1894 : * "equal" to a given accuracy (point_vert, point_horiz),
1895 : * the other ops must preserve that sense. This means
1896 : * that results may, strictly speaking, be a lie (unless
1897 : * EPSILON = 0.0).
1898 : *---------------------------------------------------------*/
9770 scrappy 1899 :
1900 : Datum
8288 tgl 1901 CBC 353131 : point_left(PG_FUNCTION_ARGS)
1902 : {
8288 tgl 1903 GIC 353131 : Point *pt1 = PG_GETARG_POINT_P(0);
8288 tgl 1904 CBC 353131 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1905 ECB :
8288 tgl 1906 CBC 353131 : PG_RETURN_BOOL(FPlt(pt1->x, pt2->x));
9770 scrappy 1907 ECB : }
1908 :
1909 : Datum
8288 tgl 1910 GIC 8418567 : point_right(PG_FUNCTION_ARGS)
1911 : {
1912 8418567 : Point *pt1 = PG_GETARG_POINT_P(0);
1913 8418567 : Point *pt2 = PG_GETARG_POINT_P(1);
1914 :
8288 tgl 1915 CBC 8418567 : PG_RETURN_BOOL(FPgt(pt1->x, pt2->x));
1916 : }
9770 scrappy 1917 ECB :
8288 tgl 1918 : Datum
8288 tgl 1919 CBC 8537907 : point_above(PG_FUNCTION_ARGS)
1920 : {
8288 tgl 1921 GIC 8537907 : Point *pt1 = PG_GETARG_POINT_P(0);
1922 8537907 : Point *pt2 = PG_GETARG_POINT_P(1);
1923 :
1924 8537907 : PG_RETURN_BOOL(FPgt(pt1->y, pt2->y));
1925 : }
1926 :
1927 : Datum
1928 624876 : point_below(PG_FUNCTION_ARGS)
1929 : {
1930 624876 : Point *pt1 = PG_GETARG_POINT_P(0);
1931 624876 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1932 ECB :
8288 tgl 1933 GIC 624876 : PG_RETURN_BOOL(FPlt(pt1->y, pt2->y));
9770 scrappy 1934 ECB : }
1935 :
1936 : Datum
8288 tgl 1937 CBC 248220 : point_vert(PG_FUNCTION_ARGS)
1938 : {
8288 tgl 1939 GIC 248220 : Point *pt1 = PG_GETARG_POINT_P(0);
1940 248220 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1941 ECB :
8288 tgl 1942 GIC 248220 : PG_RETURN_BOOL(FPeq(pt1->x, pt2->x));
9770 scrappy 1943 ECB : }
1944 :
1945 : Datum
8288 tgl 1946 CBC 265852 : point_horiz(PG_FUNCTION_ARGS)
1947 : {
8288 tgl 1948 GIC 265852 : Point *pt1 = PG_GETARG_POINT_P(0);
1949 265852 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1950 ECB :
8288 tgl 1951 GIC 265852 : PG_RETURN_BOOL(FPeq(pt1->y, pt2->y));
9770 scrappy 1952 ECB : }
1953 :
1954 : Datum
8288 tgl 1955 CBC 40102 : point_eq(PG_FUNCTION_ARGS)
1956 : {
8288 tgl 1957 GIC 40102 : Point *pt1 = PG_GETARG_POINT_P(0);
1958 40102 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1959 ECB :
1715 tomas.vondra 1960 GIC 40102 : PG_RETURN_BOOL(point_eq_point(pt1, pt2));
9770 scrappy 1961 ECB : }
1962 :
1963 : Datum
8288 tgl 1964 CBC 351 : point_ne(PG_FUNCTION_ARGS)
1965 : {
8288 tgl 1966 GIC 351 : Point *pt1 = PG_GETARG_POINT_P(0);
1967 351 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 1968 ECB :
1715 tomas.vondra 1969 GIC 351 : PG_RETURN_BOOL(!point_eq_point(pt1, pt2));
1715 tomas.vondra 1970 ECB : }
1971 :
1972 :
1697 1973 : /*
1974 : * Check whether the two points are the same
1975 : */
1976 : static inline bool
1715 tomas.vondra 1977 CBC 151697 : point_eq_point(Point *pt1, Point *pt2)
1978 : {
869 tgl 1979 ECB : /* If any NaNs are involved, insist on exact equality */
869 tgl 1980 CBC 151697 : if (unlikely(isnan(pt1->x) || isnan(pt1->y) ||
1981 : isnan(pt2->x) || isnan(pt2->y)))
1982 213 : return (float8_eq(pt1->x, pt2->x) && float8_eq(pt1->y, pt2->y));
1983 :
869 tgl 1984 GIC 151484 : return (FPeq(pt1->x, pt2->x) && FPeq(pt1->y, pt2->y));
1985 : }
9332 lockhart 1986 ECB :
1987 :
9770 scrappy 1988 : /*----------------------------------------------------------
9345 bruce 1989 : * "Arithmetic" operators on points.
1990 : *---------------------------------------------------------*/
9770 scrappy 1991 :
1992 : Datum
8288 tgl 1993 GIC 369528 : point_distance(PG_FUNCTION_ARGS)
1994 : {
8288 tgl 1995 CBC 369528 : Point *pt1 = PG_GETARG_POINT_P(0);
8288 tgl 1996 GIC 369528 : Point *pt2 = PG_GETARG_POINT_P(1);
9469 lockhart 1997 ECB :
1715 tomas.vondra 1998 CBC 369528 : PG_RETURN_FLOAT8(point_dt(pt1, pt2));
1999 : }
9770 scrappy 2000 ECB :
2001 : static inline float8
9344 bruce 2002 GIC 7773063 : point_dt(Point *pt1, Point *pt2)
2003 : {
1697 tomas.vondra 2004 7773063 : return HYPOT(float8_mi(pt1->x, pt2->x), float8_mi(pt1->y, pt2->y));
2005 : }
2006 :
2007 : Datum
8288 tgl 2008 CBC 300 : point_slope(PG_FUNCTION_ARGS)
2009 : {
8288 tgl 2010 GIC 300 : Point *pt1 = PG_GETARG_POINT_P(0);
8288 tgl 2011 CBC 300 : Point *pt2 = PG_GETARG_POINT_P(1);
2012 :
2013 300 : PG_RETURN_FLOAT8(point_sl(pt1, pt2));
2014 : }
9770 scrappy 2015 ECB :
2016 :
2017 : /*
2018 : * Return slope of two points
2019 : *
2020 : * Note that this function returns Inf when the points are the same.
2021 : */
2022 : static inline float8
9344 bruce 2023 GIC 1924602 : point_sl(Point *pt1, Point *pt2)
9770 scrappy 2024 ECB : {
1715 tomas.vondra 2025 GIC 1924602 : if (FPeq(pt1->x, pt2->x))
869 tgl 2026 CBC 214251 : return get_float8_infinity();
1715 tomas.vondra 2027 1710351 : if (FPeq(pt1->y, pt2->y))
1715 tomas.vondra 2028 GIC 212247 : return 0.0;
1697 tomas.vondra 2029 CBC 1498104 : return float8_div(float8_mi(pt1->y, pt2->y), float8_mi(pt1->x, pt2->x));
2030 : }
2031 :
2032 :
1715 tomas.vondra 2033 ECB : /*
2034 : * Return inverse slope of two points
2035 : *
2036 : * Note that this function returns 0.0 when the points are the same.
2037 : */
2038 : static inline float8
1715 tomas.vondra 2039 CBC 453240 : point_invsl(Point *pt1, Point *pt2)
2040 : {
2041 453240 : if (FPeq(pt1->x, pt2->x))
2042 179304 : return 0.0;
1715 tomas.vondra 2043 GIC 273936 : if (FPeq(pt1->y, pt2->y))
869 tgl 2044 CBC 175602 : return get_float8_infinity();
1697 tomas.vondra 2045 GIC 98334 : return float8_div(float8_mi(pt1->x, pt2->x), float8_mi(pt2->y, pt1->y));
2046 : }
2047 :
2048 :
2049 : /***********************************************************************
2050 : **
2051 : ** Routines for 2D line segments.
2052 : **
2053 : ***********************************************************************/
9770 scrappy 2054 ECB :
2055 : /*----------------------------------------------------------
9345 bruce 2056 : * String to lseg, lseg to string conversion.
2057 : * External forms: "[(x1, y1), (x2, y2)]"
2058 : * "(x1, y1), (x2, y2)"
2059 : * "x1, y1, x2, y2"
2060 : * closed form ok "((x1, y1), (x2, y2))"
2061 : * (old form) "(x1, y1, x2, y2)"
2062 : *---------------------------------------------------------*/
2063 :
2064 : Datum
8288 tgl 2065 GIC 53 : lseg_in(PG_FUNCTION_ARGS)
2066 : {
2067 53 : char *str = PG_GETARG_CSTRING(0);
116 tgl 2068 GNC 53 : Node *escontext = fcinfo->context;
2566 tgl 2069 GIC 53 : LSEG *lseg = (LSEG *) palloc(sizeof(LSEG));
2070 : bool isopen;
9483 scrappy 2071 ECB :
116 tgl 2072 GNC 53 : if (!path_decode(str, true, 2, &lseg->p[0], &isopen, NULL, "lseg", str,
2073 : escontext))
2074 6 : PG_RETURN_NULL();
2075 :
8288 tgl 2076 CBC 35 : PG_RETURN_LSEG_P(lseg);
8288 tgl 2077 ECB : }
9770 scrappy 2078 :
2079 :
8288 tgl 2080 : Datum
8288 tgl 2081 GIC 3663 : lseg_out(PG_FUNCTION_ARGS)
2082 : {
2083 3663 : LSEG *ls = PG_GETARG_LSEG_P(0);
2084 :
1715 tomas.vondra 2085 3663 : PG_RETURN_CSTRING(path_encode(PATH_OPEN, 2, &ls->p[0]));
2086 : }
2087 :
2088 : /*
2089 : * lseg_recv - converts external binary format to lseg
2090 : */
2091 : Datum
7271 tgl 2092 UIC 0 : lseg_recv(PG_FUNCTION_ARGS)
2093 : {
2094 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
2095 : LSEG *lseg;
2096 :
2097 0 : lseg = (LSEG *) palloc(sizeof(LSEG));
2098 :
2099 0 : lseg->p[0].x = pq_getmsgfloat8(buf);
7271 tgl 2100 LBC 0 : lseg->p[0].y = pq_getmsgfloat8(buf);
7271 tgl 2101 UIC 0 : lseg->p[1].x = pq_getmsgfloat8(buf);
7271 tgl 2102 LBC 0 : lseg->p[1].y = pq_getmsgfloat8(buf);
7271 tgl 2103 ECB :
7271 tgl 2104 LBC 0 : PG_RETURN_LSEG_P(lseg);
2105 : }
2106 :
7271 tgl 2107 ECB : /*
2108 : * lseg_send - converts lseg to binary format
2109 : */
2110 : Datum
7271 tgl 2111 LBC 0 : lseg_send(PG_FUNCTION_ARGS)
2112 : {
7271 tgl 2113 UIC 0 : LSEG *ls = PG_GETARG_LSEG_P(0);
2114 : StringInfoData buf;
2115 :
7271 tgl 2116 LBC 0 : pq_begintypsend(&buf);
7271 tgl 2117 UIC 0 : pq_sendfloat8(&buf, ls->p[0].x);
7271 tgl 2118 LBC 0 : pq_sendfloat8(&buf, ls->p[0].y);
7271 tgl 2119 UIC 0 : pq_sendfloat8(&buf, ls->p[1].x);
7271 tgl 2120 LBC 0 : pq_sendfloat8(&buf, ls->p[1].y);
7271 tgl 2121 UIC 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
2122 : }
2123 :
2124 :
2125 : /* lseg_construct -
2126 : * form a LSEG from two Points.
9770 scrappy 2127 EUB : */
2128 : Datum
8288 tgl 2129 GBC 3 : lseg_construct(PG_FUNCTION_ARGS)
2130 : {
8288 tgl 2131 GIC 3 : Point *pt1 = PG_GETARG_POINT_P(0);
8288 tgl 2132 GBC 3 : Point *pt2 = PG_GETARG_POINT_P(1);
8288 tgl 2133 GIC 3 : LSEG *result = (LSEG *) palloc(sizeof(LSEG));
9469 lockhart 2134 EUB :
1715 tomas.vondra 2135 GBC 3 : statlseg_construct(result, pt1, pt2);
9483 scrappy 2136 EUB :
8288 tgl 2137 GBC 3 : PG_RETURN_LSEG_P(result);
2138 : }
9770 scrappy 2139 EUB :
2140 : /* like lseg_construct, but assume space already allocated */
2141 : static inline void
9344 bruce 2142 GIC 505461 : statlseg_construct(LSEG *lseg, Point *pt1, Point *pt2)
2143 : {
9345 2144 505461 : lseg->p[0].x = pt1->x;
2145 505461 : lseg->p[0].y = pt1->y;
9345 bruce 2146 GBC 505461 : lseg->p[1].x = pt2->x;
9345 bruce 2147 GIC 505461 : lseg->p[1].y = pt2->y;
9770 scrappy 2148 GBC 505461 : }
2149 :
2150 :
1715 tomas.vondra 2151 EUB : /*
2152 : * Return slope of the line segment
2153 : */
2154 : static inline float8
1715 tomas.vondra 2155 GBC 1924035 : lseg_sl(LSEG *lseg)
1715 tomas.vondra 2156 EUB : {
1715 tomas.vondra 2157 GIC 1924035 : return point_sl(&lseg->p[0], &lseg->p[1]);
2158 : }
2159 :
2160 :
2161 : /*
2162 : * Return inverse slope of the line segment
2163 : */
1715 tomas.vondra 2164 ECB : static inline float8
1715 tomas.vondra 2165 GIC 192 : lseg_invsl(LSEG *lseg)
1715 tomas.vondra 2166 ECB : {
1715 tomas.vondra 2167 CBC 192 : return point_invsl(&lseg->p[0], &lseg->p[1]);
1715 tomas.vondra 2168 ECB : }
2169 :
2170 :
2171 : Datum
8288 tgl 2172 CBC 24 : lseg_length(PG_FUNCTION_ARGS)
2173 : {
8288 tgl 2174 GIC 24 : LSEG *lseg = PG_GETARG_LSEG_P(0);
2175 :
2176 24 : PG_RETURN_FLOAT8(point_dt(&lseg->p[0], &lseg->p[1]));
8288 tgl 2177 ECB : }
2178 :
9770 scrappy 2179 : /*----------------------------------------------------------
9345 bruce 2180 : * Relative position routines.
9770 scrappy 2181 : *---------------------------------------------------------*/
2182 :
2183 : /*
2184 : ** find intersection of the two lines, and see if it falls on
2185 : ** both segments.
2186 : */
2187 : Datum
8288 tgl 2188 GIC 12684 : lseg_intersect(PG_FUNCTION_ARGS)
2189 : {
8288 tgl 2190 CBC 12684 : LSEG *l1 = PG_GETARG_LSEG_P(0);
8288 tgl 2191 GIC 12684 : LSEG *l2 = PG_GETARG_LSEG_P(1);
8288 tgl 2192 ECB :
1715 tomas.vondra 2193 GIC 12684 : PG_RETURN_BOOL(lseg_interpt_lseg(NULL, l1, l2));
2194 : }
2195 :
2196 :
2197 : Datum
8288 tgl 2198 192 : lseg_parallel(PG_FUNCTION_ARGS)
2199 : {
8288 tgl 2200 CBC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
8288 tgl 2201 GIC 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
8288 tgl 2202 ECB :
1715 tomas.vondra 2203 GIC 192 : PG_RETURN_BOOL(FPeq(lseg_sl(l1), lseg_sl(l2)));
2204 : }
2205 :
2206 : /*
9196 lockhart 2207 ECB : * Determine if two line segments are perpendicular.
2208 : */
8288 tgl 2209 : Datum
8288 tgl 2210 GIC 192 : lseg_perp(PG_FUNCTION_ARGS)
9770 scrappy 2211 ECB : {
8288 tgl 2212 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2213 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2214 :
1715 tomas.vondra 2215 192 : PG_RETURN_BOOL(FPeq(lseg_sl(l1), lseg_invsl(l2)));
2216 : }
2217 :
2218 : Datum
8288 tgl 2219 24 : lseg_vertical(PG_FUNCTION_ARGS)
2220 : {
2221 24 : LSEG *lseg = PG_GETARG_LSEG_P(0);
2222 :
8288 tgl 2223 CBC 24 : PG_RETURN_BOOL(FPeq(lseg->p[0].x, lseg->p[1].x));
2224 : }
9770 scrappy 2225 ECB :
8288 tgl 2226 : Datum
8288 tgl 2227 GIC 24 : lseg_horizontal(PG_FUNCTION_ARGS)
9770 scrappy 2228 ECB : {
8288 tgl 2229 GIC 24 : LSEG *lseg = PG_GETARG_LSEG_P(0);
2230 :
2231 24 : PG_RETURN_BOOL(FPeq(lseg->p[0].y, lseg->p[1].y));
2232 : }
9770 scrappy 2233 ECB :
2234 :
8288 tgl 2235 : Datum
8288 tgl 2236 CBC 193 : lseg_eq(PG_FUNCTION_ARGS)
2237 : {
2238 193 : LSEG *l1 = PG_GETARG_LSEG_P(0);
8288 tgl 2239 GIC 193 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2240 :
1715 tomas.vondra 2241 193 : PG_RETURN_BOOL(point_eq_point(&l1->p[0], &l2->p[0]) &&
2242 : point_eq_point(&l1->p[1], &l2->p[1]));
2243 : }
2244 :
8288 tgl 2245 ECB : Datum
8288 tgl 2246 GIC 192 : lseg_ne(PG_FUNCTION_ARGS)
9196 lockhart 2247 ECB : {
8288 tgl 2248 CBC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
8288 tgl 2249 GIC 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
9196 lockhart 2250 ECB :
1715 tomas.vondra 2251 GIC 192 : PG_RETURN_BOOL(!point_eq_point(&l1->p[0], &l2->p[0]) ||
2252 : !point_eq_point(&l1->p[1], &l2->p[1]));
2253 : }
8288 tgl 2254 ECB :
2255 : Datum
8288 tgl 2256 CBC 192 : lseg_lt(PG_FUNCTION_ARGS)
2257 : {
2258 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
8288 tgl 2259 GIC 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2260 :
2261 192 : PG_RETURN_BOOL(FPlt(point_dt(&l1->p[0], &l1->p[1]),
8288 tgl 2262 ECB : point_dt(&l2->p[0], &l2->p[1])));
2263 : }
9196 lockhart 2264 :
2265 : Datum
8288 tgl 2266 CBC 192 : lseg_le(PG_FUNCTION_ARGS)
2267 : {
8288 tgl 2268 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2269 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2270 :
8288 tgl 2271 CBC 192 : PG_RETURN_BOOL(FPle(point_dt(&l1->p[0], &l1->p[1]),
2272 : point_dt(&l2->p[0], &l2->p[1])));
8288 tgl 2273 ECB : }
9196 lockhart 2274 :
2275 : Datum
8288 tgl 2276 CBC 192 : lseg_gt(PG_FUNCTION_ARGS)
2277 : {
8288 tgl 2278 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2279 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2280 :
8288 tgl 2281 CBC 192 : PG_RETURN_BOOL(FPgt(point_dt(&l1->p[0], &l1->p[1]),
2282 : point_dt(&l2->p[0], &l2->p[1])));
8288 tgl 2283 ECB : }
9196 lockhart 2284 :
2285 : Datum
8288 tgl 2286 CBC 192 : lseg_ge(PG_FUNCTION_ARGS)
2287 : {
8288 tgl 2288 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2289 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2290 :
8288 tgl 2291 CBC 192 : PG_RETURN_BOOL(FPge(point_dt(&l1->p[0], &l1->p[1]),
2292 : point_dt(&l2->p[0], &l2->p[1])));
8288 tgl 2293 ECB : }
9770 scrappy 2294 :
2295 :
2296 : /*----------------------------------------------------------
2297 : * Line arithmetic routines.
2298 : *---------------------------------------------------------*/
2299 :
2300 : /* lseg_distance -
9345 bruce 2301 : * If two segments don't intersect, then the closest
2302 : * point will be from one of the endpoints to the other
2303 : * segment.
9770 scrappy 2304 : */
2305 : Datum
8288 tgl 2306 CBC 192 : lseg_distance(PG_FUNCTION_ARGS)
2307 : {
8288 tgl 2308 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2309 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2310 :
1715 tomas.vondra 2311 CBC 192 : PG_RETURN_FLOAT8(lseg_closept_lseg(NULL, l1, l2));
2312 : }
9385 lockhart 2313 ECB :
2314 :
2315 : Datum
8288 tgl 2316 CBC 48 : lseg_center(PG_FUNCTION_ARGS)
2317 : {
8288 tgl 2318 GIC 48 : LSEG *lseg = PG_GETARG_LSEG_P(0);
2319 : Point *result;
2320 :
8288 tgl 2321 CBC 48 : result = (Point *) palloc(sizeof(Point));
2322 :
1697 tomas.vondra 2323 48 : result->x = float8_div(float8_pl(lseg->p[0].x, lseg->p[1].x), 2.0);
2324 48 : result->y = float8_div(float8_pl(lseg->p[0].y, lseg->p[1].y), 2.0);
2325 :
8288 tgl 2326 48 : PG_RETURN_POINT_P(result);
2327 : }
2328 :
2329 :
2330 : /*
2331 : * Return whether the two segments intersect. If *result is not NULL,
2332 : * it is set to the intersection point.
2333 : *
2334 : * This function is almost perfectly symmetric, even though it doesn't look
2335 : * like it. See lseg_interpt_line() for the other half of it.
2336 : */
2337 : static bool
1715 tomas.vondra 2338 GIC 734175 : lseg_interpt_lseg(Point *result, LSEG *l1, LSEG *l2)
2339 : {
2340 : Point interpt;
1715 tomas.vondra 2341 ECB : LINE tmp;
2342 :
1715 tomas.vondra 2343 CBC 734175 : line_construct(&tmp, &l2->p[0], lseg_sl(l2));
2344 734175 : if (!lseg_interpt_line(&interpt, l1, &tmp))
1715 tomas.vondra 2345 GIC 692928 : return false;
8053 bruce 2346 ECB :
2347 : /*
2348 : * If the line intersection point isn't within l2, there is no valid
2349 : * segment intersection point at all.
2350 : */
1715 tomas.vondra 2351 CBC 41247 : if (!lseg_contain_point(l2, &interpt))
1715 tomas.vondra 2352 GIC 30891 : return false;
8053 bruce 2353 ECB :
1715 tomas.vondra 2354 GIC 10356 : if (result != NULL)
2355 3357 : *result = interpt;
9345 bruce 2356 ECB :
1715 tomas.vondra 2357 GIC 10356 : return true;
5003 teodor 2358 ECB : }
2359 :
2360 : Datum
5003 teodor 2361 CBC 2874 : lseg_interpt(PG_FUNCTION_ARGS)
2362 : {
5003 teodor 2363 GIC 2874 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2364 2874 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2365 : Point *result;
2366 :
1715 tomas.vondra 2367 2874 : result = (Point *) palloc(sizeof(Point));
2368 :
2369 2874 : if (!lseg_interpt_lseg(result, l1, l2))
2370 192 : PG_RETURN_NULL();
8288 tgl 2371 2682 : PG_RETURN_POINT_P(result);
2372 : }
9770 scrappy 2373 ECB :
2374 : /***********************************************************************
2375 : **
2376 : ** Routines for position comparisons of differently-typed
2377 : ** 2D objects.
2378 : **
2379 : ***********************************************************************/
2380 :
2381 : /*---------------------------------------------------------------------
2382 : * dist_
2383 : * Minimum distance from one object to another.
2384 : *-------------------------------------------------------------------*/
2385 :
3037 heikki.linnakangas 2386 : /*
2387 : * Distance from a point to a line
2388 : */
8288 tgl 2389 : Datum
8288 tgl 2390 CBC 300 : dist_pl(PG_FUNCTION_ARGS)
2391 : {
2392 300 : Point *pt = PG_GETARG_POINT_P(0);
8288 tgl 2393 GIC 300 : LINE *line = PG_GETARG_LINE_P(1);
2394 :
1715 tomas.vondra 2395 300 : PG_RETURN_FLOAT8(line_closept_point(NULL, line, pt));
8288 tgl 2396 ECB : }
2397 :
1365 akorotkov 2398 : /*
2399 : * Distance from a line to a point
2400 : */
2401 : Datum
1365 akorotkov 2402 CBC 300 : dist_lp(PG_FUNCTION_ARGS)
2403 : {
2404 300 : LINE *line = PG_GETARG_LINE_P(0);
2405 300 : Point *pt = PG_GETARG_POINT_P(1);
1365 akorotkov 2406 ECB :
1365 akorotkov 2407 GIC 300 : PG_RETURN_FLOAT8(line_closept_point(NULL, line, pt));
2408 : }
2409 :
2410 : /*
2411 : * Distance from a point to a lseg
2412 : */
2413 : Datum
8288 tgl 2414 240 : dist_ps(PG_FUNCTION_ARGS)
2415 : {
2416 240 : Point *pt = PG_GETARG_POINT_P(0);
2417 240 : LSEG *lseg = PG_GETARG_LSEG_P(1);
2418 :
1715 tomas.vondra 2419 240 : PG_RETURN_FLOAT8(lseg_closept_point(NULL, lseg, pt));
2420 : }
2421 :
2422 : /*
2423 : * Distance from a lseg to a point
2424 : */
8289 tgl 2425 ECB : Datum
1365 akorotkov 2426 GIC 240 : dist_sp(PG_FUNCTION_ARGS)
1365 akorotkov 2427 ECB : {
1365 akorotkov 2428 CBC 240 : LSEG *lseg = PG_GETARG_LSEG_P(0);
1365 akorotkov 2429 GIC 240 : Point *pt = PG_GETARG_POINT_P(1);
1365 akorotkov 2430 ECB :
1365 akorotkov 2431 GIC 240 : PG_RETURN_FLOAT8(lseg_closept_point(NULL, lseg, pt));
2432 : }
2433 :
2434 : static float8
2435 540 : dist_ppath_internal(Point *pt, PATH *path)
2436 : {
8289 tgl 2437 CBC 540 : float8 result = 0.0; /* keep compiler quiet */
7848 tgl 2438 GIC 540 : bool have_min = false;
8289 tgl 2439 ECB : float8 tmp;
9344 bruce 2440 : int i;
2441 : LSEG lseg;
9345 2442 :
1715 tomas.vondra 2443 GIC 540 : Assert(path->npts > 0);
2444 :
2445 : /*
2446 : * The distance from a point to a path is the smallest distance from the
2447 : * point to any of its constituent segments.
2448 : */
1715 tomas.vondra 2449 CBC 1680 : for (i = 0; i < path->npts; i++)
2450 : {
1715 tomas.vondra 2451 ECB : int iprev;
7848 tgl 2452 :
1715 tomas.vondra 2453 GIC 1140 : if (i > 0)
1715 tomas.vondra 2454 CBC 600 : iprev = i - 1;
2455 : else
2456 : {
1715 tomas.vondra 2457 GIC 540 : if (!path->closed)
2458 240 : continue;
2459 300 : iprev = path->npts - 1; /* Include the closure segment */
2460 : }
7848 tgl 2461 ECB :
1715 tomas.vondra 2462 GIC 900 : statlseg_construct(&lseg, &path->p[iprev], &path->p[i]);
1715 tomas.vondra 2463 CBC 900 : tmp = lseg_closept_point(NULL, &lseg, pt);
1697 2464 900 : if (!have_min || float8_lt(tmp, result))
2465 : {
1715 2466 564 : result = tmp;
1715 tomas.vondra 2467 GIC 564 : have_min = true;
2468 : }
2469 : }
1715 tomas.vondra 2470 ECB :
1365 akorotkov 2471 GIC 540 : return result;
1365 akorotkov 2472 ECB : }
2473 :
2474 : /*
2475 : * Distance from a point to a path
2476 : */
2477 : Datum
1365 akorotkov 2478 CBC 270 : dist_ppath(PG_FUNCTION_ARGS)
2479 : {
1365 akorotkov 2480 GIC 270 : Point *pt = PG_GETARG_POINT_P(0);
2481 270 : PATH *path = PG_GETARG_PATH_P(1);
2482 :
2483 270 : PG_RETURN_FLOAT8(dist_ppath_internal(pt, path));
1365 akorotkov 2484 ECB : }
2485 :
2486 : /*
2487 : * Distance from a path to a point
2488 : */
2489 : Datum
1365 akorotkov 2490 GIC 270 : dist_pathp(PG_FUNCTION_ARGS)
2491 : {
1365 akorotkov 2492 CBC 270 : PATH *path = PG_GETARG_PATH_P(0);
2493 270 : Point *pt = PG_GETARG_POINT_P(1);
1365 akorotkov 2494 ECB :
1365 akorotkov 2495 GIC 270 : PG_RETURN_FLOAT8(dist_ppath_internal(pt, path));
2496 : }
9770 scrappy 2497 ECB :
3037 heikki.linnakangas 2498 : /*
2499 : * Distance from a point to a box
2500 : */
8288 tgl 2501 : Datum
8288 tgl 2502 CBC 213 : dist_pb(PG_FUNCTION_ARGS)
2503 : {
8288 tgl 2504 GIC 213 : Point *pt = PG_GETARG_POINT_P(0);
2505 213 : BOX *box = PG_GETARG_BOX_P(1);
9483 scrappy 2506 ECB :
1715 tomas.vondra 2507 GIC 213 : PG_RETURN_FLOAT8(box_closept_point(NULL, box, pt));
2508 : }
2509 :
2510 : /*
2511 : * Distance from a box to a point
2512 : */
1365 akorotkov 2513 ECB : Datum
1365 akorotkov 2514 GIC 77631 : dist_bp(PG_FUNCTION_ARGS)
1365 akorotkov 2515 ECB : {
1365 akorotkov 2516 CBC 77631 : BOX *box = PG_GETARG_BOX_P(0);
1365 akorotkov 2517 GIC 77631 : Point *pt = PG_GETARG_POINT_P(1);
1365 akorotkov 2518 ECB :
1365 akorotkov 2519 GIC 77631 : PG_RETURN_FLOAT8(box_closept_point(NULL, box, pt));
2520 : }
2521 :
2522 : /*
2523 : * Distance from a lseg to a line
2524 : */
8288 tgl 2525 ECB : Datum
8288 tgl 2526 GIC 240 : dist_sl(PG_FUNCTION_ARGS)
9770 scrappy 2527 ECB : {
8288 tgl 2528 CBC 240 : LSEG *lseg = PG_GETARG_LSEG_P(0);
8288 tgl 2529 GIC 240 : LINE *line = PG_GETARG_LINE_P(1);
9345 bruce 2530 ECB :
1656 tomas.vondra 2531 GIC 240 : PG_RETURN_FLOAT8(lseg_closept_line(NULL, lseg, line));
2532 : }
2533 :
2534 : /*
2535 : * Distance from a line to a lseg
2536 : */
1365 akorotkov 2537 ECB : Datum
1365 akorotkov 2538 GIC 240 : dist_ls(PG_FUNCTION_ARGS)
1365 akorotkov 2539 ECB : {
1365 akorotkov 2540 CBC 240 : LINE *line = PG_GETARG_LINE_P(0);
1365 akorotkov 2541 GIC 240 : LSEG *lseg = PG_GETARG_LSEG_P(1);
1365 akorotkov 2542 ECB :
1365 akorotkov 2543 GIC 240 : PG_RETURN_FLOAT8(lseg_closept_line(NULL, lseg, line));
2544 : }
2545 :
2546 : /*
2547 : * Distance from a lseg to a box
2548 : */
8288 tgl 2549 ECB : Datum
8288 tgl 2550 GIC 120 : dist_sb(PG_FUNCTION_ARGS)
9770 scrappy 2551 ECB : {
8288 tgl 2552 CBC 120 : LSEG *lseg = PG_GETARG_LSEG_P(0);
8288 tgl 2553 GIC 120 : BOX *box = PG_GETARG_BOX_P(1);
9345 bruce 2554 ECB :
1715 tomas.vondra 2555 GIC 120 : PG_RETURN_FLOAT8(box_closept_lseg(NULL, box, lseg));
2556 : }
2557 :
2558 : /*
2559 : * Distance from a box to a lseg
2560 : */
1365 akorotkov 2561 ECB : Datum
1365 akorotkov 2562 GIC 120 : dist_bs(PG_FUNCTION_ARGS)
1365 akorotkov 2563 ECB : {
1365 akorotkov 2564 CBC 120 : BOX *box = PG_GETARG_BOX_P(0);
1365 akorotkov 2565 GIC 120 : LSEG *lseg = PG_GETARG_LSEG_P(1);
1365 akorotkov 2566 ECB :
1365 akorotkov 2567 GIC 120 : PG_RETURN_FLOAT8(box_closept_lseg(NULL, box, lseg));
2568 : }
2569 :
2570 : static float8
2571 168 : dist_cpoly_internal(CIRCLE *circle, POLYGON *poly)
2572 : {
8289 tgl 2573 ECB : float8 result;
2574 :
3037 heikki.linnakangas 2575 : /* calculate distance to center, and subtract radius */
1697 tomas.vondra 2576 CBC 168 : result = float8_mi(dist_ppoly_internal(&circle->center, poly),
2577 : circle->radius);
2578 168 : if (result < 0.0)
1697 tomas.vondra 2579 GIC 90 : result = 0.0;
2580 :
1365 akorotkov 2581 168 : return result;
2582 : }
2583 :
2584 : /*
1365 akorotkov 2585 ECB : * Distance from a circle to a polygon
2586 : */
2587 : Datum
1365 akorotkov 2588 CBC 168 : dist_cpoly(PG_FUNCTION_ARGS)
2589 : {
2590 168 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
1365 akorotkov 2591 GIC 168 : POLYGON *poly = PG_GETARG_POLYGON_P(1);
2592 :
2593 168 : PG_RETURN_FLOAT8(dist_cpoly_internal(circle, poly));
2594 : }
2595 :
2596 : /*
1365 akorotkov 2597 ECB : * Distance from a polygon to a circle
2598 : */
2599 : Datum
1365 akorotkov 2600 LBC 0 : dist_polyc(PG_FUNCTION_ARGS)
2601 : {
2602 0 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
1365 akorotkov 2603 UIC 0 : CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
2604 :
2605 0 : PG_RETURN_FLOAT8(dist_cpoly_internal(circle, poly));
3037 heikki.linnakangas 2606 ECB : }
2607 :
2608 : /*
2609 : * Distance from a point to a polygon
2610 : */
2611 : Datum
3037 heikki.linnakangas 2612 GIC 210 : dist_ppoly(PG_FUNCTION_ARGS)
3037 heikki.linnakangas 2613 ECB : {
3037 heikki.linnakangas 2614 CBC 210 : Point *point = PG_GETARG_POINT_P(0);
3037 heikki.linnakangas 2615 GIC 210 : POLYGON *poly = PG_GETARG_POLYGON_P(1);
3037 heikki.linnakangas 2616 ECB :
1715 tomas.vondra 2617 GIC 210 : PG_RETURN_FLOAT8(dist_ppoly_internal(point, poly));
2618 : }
2619 :
2620 : Datum
2886 heikki.linnakangas 2621 17154 : dist_polyp(PG_FUNCTION_ARGS)
2622 : {
2886 heikki.linnakangas 2623 CBC 17154 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
2886 heikki.linnakangas 2624 GIC 17154 : Point *point = PG_GETARG_POINT_P(1);
2886 heikki.linnakangas 2625 ECB :
1715 tomas.vondra 2626 CBC 17154 : PG_RETURN_FLOAT8(dist_ppoly_internal(point, poly));
2627 : }
2886 heikki.linnakangas 2628 ECB :
2629 : static float8
3037 heikki.linnakangas 2630 GIC 17532 : dist_ppoly_internal(Point *pt, POLYGON *poly)
2631 : {
2632 : float8 result;
2633 : float8 d;
2634 : int i;
9344 bruce 2635 EUB : LSEG seg;
2636 :
3037 heikki.linnakangas 2637 GBC 17532 : if (point_inside(pt, poly->npts, poly->p) != 0)
tgl 2638 90 : return 0.0;
2639 :
9345 bruce 2640 EUB : /* initialize distance with segment between first and last points */
9345 bruce 2641 GIC 17442 : seg.p[0].x = poly->p[0].x;
2642 17442 : seg.p[0].y = poly->p[0].y;
2643 17442 : seg.p[1].x = poly->p[poly->npts - 1].x;
2644 17442 : seg.p[1].y = poly->p[poly->npts - 1].y;
1715 tomas.vondra 2645 17442 : result = lseg_closept_point(NULL, &seg, pt);
2646 :
9345 bruce 2647 ECB : /* check distances for other segments */
1715 tomas.vondra 2648 GIC 129006 : for (i = 0; i < poly->npts - 1; i++)
9345 bruce 2649 ECB : {
9345 bruce 2650 CBC 111564 : seg.p[0].x = poly->p[i].x;
9345 bruce 2651 GIC 111564 : seg.p[0].y = poly->p[i].y;
9345 bruce 2652 CBC 111564 : seg.p[1].x = poly->p[i + 1].x;
9345 bruce 2653 GIC 111564 : seg.p[1].y = poly->p[i + 1].y;
1715 tomas.vondra 2654 111564 : d = lseg_closept_point(NULL, &seg, pt);
1697 2655 111564 : if (float8_lt(d, result))
8289 tgl 2656 CBC 3294 : result = d;
2657 : }
9385 lockhart 2658 ECB :
3037 heikki.linnakangas 2659 CBC 17442 : return result;
2660 : }
9385 lockhart 2661 ECB :
2662 :
2663 : /*---------------------------------------------------------------------
2664 : * interpt_
9345 bruce 2665 : * Intersection point of objects.
2666 : * We choose to ignore the "point" of intersection between
2667 : * lines and boxes, since there are typically two.
2668 : *-------------------------------------------------------------------*/
2669 :
2670 : /*
2671 : * Return whether the line segment intersect with the line. If *result is not
1606 alvherre 2672 : * NULL, it is set to the intersection point.
1715 tomas.vondra 2673 : */
2674 : static bool
1715 tomas.vondra 2675 GIC 1188645 : lseg_interpt_line(Point *result, LSEG *lseg, LINE *line)
9770 scrappy 2676 ECB : {
1715 tomas.vondra 2677 : Point interpt;
8288 tgl 2678 : LINE tmp;
9345 bruce 2679 :
1715 tomas.vondra 2680 : /*
2681 : * First, we promote the line segment to a line, because we know how to
2682 : * find the intersection point of two lines. If they don't have an
1418 tgl 2683 : * intersection point, we are done.
2684 : */
1715 tomas.vondra 2685 CBC 1188645 : line_construct(&tmp, &lseg->p[0], lseg_sl(lseg));
2686 1188645 : if (!line_interpt_line(&interpt, &tmp, line))
2687 6081 : return false;
9770 scrappy 2688 ECB :
1715 tomas.vondra 2689 : /*
2690 : * Then, we check whether the intersection point is actually on the line
2691 : * segment.
2692 : */
1715 tomas.vondra 2693 GIC 1182564 : if (!lseg_contain_point(lseg, &interpt))
1715 tomas.vondra 2694 CBC 1135326 : return false;
1606 alvherre 2695 GIC 47238 : if (result != NULL)
2696 : {
2697 : /*
2698 : * If there is an intersection, then check explicitly for matching
2699 : * endpoints since there may be rounding effects with annoying LSB
2700 : * residue.
2701 : */
2702 47046 : if (point_eq_point(&lseg->p[0], &interpt))
2703 3306 : *result = lseg->p[0];
2704 43740 : else if (point_eq_point(&lseg->p[1], &interpt))
2705 6627 : *result = lseg->p[1];
2706 : else
2707 37113 : *result = interpt;
2708 : }
2709 :
1715 tomas.vondra 2710 CBC 47238 : return true;
2711 : }
2712 :
2713 : /*---------------------------------------------------------------------
2714 : * close_
2715 : * Point of closest proximity between objects.
2716 : *-------------------------------------------------------------------*/
2717 :
2718 : /*
2719 : * If *result is not NULL, it is set to the intersection point of a
1606 alvherre 2720 ECB : * perpendicular of the line through the point. Returns the distance
2721 : * of those two points.
9770 scrappy 2722 : */
2723 : static float8
1715 tomas.vondra 2724 GIC 896580 : line_closept_point(Point *result, LINE *line, Point *point)
2725 : {
2726 : Point closept;
2727 : LINE tmp;
1715 tomas.vondra 2728 ECB :
1656 2729 : /*
1418 tgl 2730 : * We drop a perpendicular to find the intersection point. Ordinarily we
2731 : * should always find it, but that can fail in the presence of NaN
2732 : * coordinates, and perhaps even from simple roundoff issues.
2733 : */
1715 tomas.vondra 2734 GIC 896580 : line_construct(&tmp, point, line_invsl(line));
1656 2735 896580 : if (!line_interpt_line(&closept, &tmp, line))
2736 : {
1656 tomas.vondra 2737 LBC 0 : if (result != NULL)
2738 0 : *result = *point;
1715 tomas.vondra 2739 ECB :
1656 tomas.vondra 2740 LBC 0 : return get_float8_nan();
2741 : }
1715 tomas.vondra 2742 ECB :
1715 tomas.vondra 2743 GIC 896580 : if (result != NULL)
2744 300 : *result = closept;
1715 tomas.vondra 2745 ECB :
1715 tomas.vondra 2746 GIC 896580 : return point_dt(&closept, point);
2747 : }
2748 :
2749 : Datum
8288 tgl 2750 300 : close_pl(PG_FUNCTION_ARGS)
2751 : {
2752 300 : Point *pt = PG_GETARG_POINT_P(0);
2753 300 : LINE *line = PG_GETARG_LINE_P(1);
2754 : Point *result;
2755 :
2756 300 : result = (Point *) palloc(sizeof(Point));
2757 :
1697 tomas.vondra 2758 300 : if (isnan(line_closept_point(result, line, pt)))
1697 tomas.vondra 2759 CBC 108 : PG_RETURN_NULL();
2760 :
8288 tgl 2761 GIC 192 : PG_RETURN_POINT_P(result);
2762 : }
2763 :
2764 :
2765 : /*
2766 : * Closest point on line segment to specified point.
2767 : *
2768 : * If *result is not NULL, set it to the closest point on the line segment
1606 alvherre 2769 ECB : * to the point. Returns the distance of the two points.
9345 bruce 2770 : */
2771 : static float8
1715 tomas.vondra 2772 GBC 453048 : lseg_closept_point(Point *result, LSEG *lseg, Point *pt)
9345 bruce 2773 EUB : {
2774 : Point closept;
1715 tomas.vondra 2775 : LINE tmp;
2776 :
2777 : /*
1715 tomas.vondra 2778 ECB : * To find the closest point, we draw a perpendicular line from the point
2779 : * to the line segment.
2780 : */
1715 tomas.vondra 2781 CBC 453048 : line_construct(&tmp, pt, point_invsl(&lseg->p[0], &lseg->p[1]));
1715 tomas.vondra 2782 GIC 453048 : lseg_closept_line(&closept, lseg, &tmp);
2783 :
2784 453048 : if (result != NULL)
1715 tomas.vondra 2785 CBC 238083 : *result = closept;
2786 :
2787 453048 : return point_dt(&closept, pt);
1715 tomas.vondra 2788 ECB : }
2789 :
2790 : Datum
1715 tomas.vondra 2791 CBC 240 : close_ps(PG_FUNCTION_ARGS)
2792 : {
2793 240 : Point *pt = PG_GETARG_POINT_P(0);
2794 240 : LSEG *lseg = PG_GETARG_LSEG_P(1);
2795 : Point *result;
1715 tomas.vondra 2796 ECB :
1715 tomas.vondra 2797 GIC 240 : result = (Point *) palloc(sizeof(Point));
2798 :
2799 240 : if (isnan(lseg_closept_point(result, lseg, pt)))
2458 tgl 2800 48 : PG_RETURN_NULL();
2801 :
8288 2802 192 : PG_RETURN_POINT_P(result);
2803 : }
2804 :
2805 :
2806 : /*
1715 tomas.vondra 2807 ECB : * Closest point on line segment to line segment
2808 : */
2809 : static float8
1606 alvherre 2810 GIC 2634 : lseg_closept_lseg(Point *result, LSEG *on_lseg, LSEG *to_lseg)
2811 : {
2812 : Point point;
2813 : float8 dist,
2814 : d;
2815 :
1656 tomas.vondra 2816 ECB : /* First, we handle the case when the line segments are intersecting. */
1606 alvherre 2817 CBC 2634 : if (lseg_interpt_lseg(result, on_lseg, to_lseg))
1656 tomas.vondra 2818 GIC 12 : return 0.0;
9196 lockhart 2819 ECB :
1656 tomas.vondra 2820 : /*
2821 : * Then, we find the closest points from the endpoints of the second line
1418 tgl 2822 : * segment, and keep the closest one.
2823 : */
1606 alvherre 2824 GIC 2622 : dist = lseg_closept_point(result, on_lseg, &to_lseg->p[0]);
2825 2622 : d = lseg_closept_point(&point, on_lseg, &to_lseg->p[1]);
1697 tomas.vondra 2826 CBC 2622 : if (float8_lt(d, dist))
2827 : {
8288 tgl 2828 873 : dist = d;
1715 tomas.vondra 2829 873 : if (result != NULL)
1656 tomas.vondra 2830 GIC 408 : *result = point;
2831 : }
9196 lockhart 2832 ECB :
2833 : /* The closest point can still be one of the endpoints, so we test them. */
1606 alvherre 2834 CBC 2622 : d = lseg_closept_point(NULL, to_lseg, &on_lseg->p[0]);
1697 tomas.vondra 2835 2622 : if (float8_lt(d, dist))
2836 : {
1715 2837 576 : dist = d;
1656 tomas.vondra 2838 GIC 576 : if (result != NULL)
1606 alvherre 2839 372 : *result = on_lseg->p[0];
2840 : }
2841 2622 : d = lseg_closept_point(NULL, to_lseg, &on_lseg->p[1]);
1656 tomas.vondra 2842 2622 : if (float8_lt(d, dist))
2843 : {
2844 222 : dist = d;
1656 tomas.vondra 2845 CBC 222 : if (result != NULL)
1606 alvherre 2846 GIC 126 : *result = on_lseg->p[1];
2847 : }
2848 :
1715 tomas.vondra 2849 2622 : return dist;
2850 : }
2851 :
1715 tomas.vondra 2852 ECB : Datum
1715 tomas.vondra 2853 CBC 192 : close_lseg(PG_FUNCTION_ARGS)
2854 : {
1715 tomas.vondra 2855 GIC 192 : LSEG *l1 = PG_GETARG_LSEG_P(0);
2856 192 : LSEG *l2 = PG_GETARG_LSEG_P(1);
2857 : Point *result;
2858 :
1656 tomas.vondra 2859 CBC 192 : if (lseg_sl(l1) == lseg_sl(l2))
2860 39 : PG_RETURN_NULL();
1656 tomas.vondra 2861 ECB :
1715 tomas.vondra 2862 GIC 153 : result = (Point *) palloc(sizeof(Point));
1715 tomas.vondra 2863 ECB :
1697 tomas.vondra 2864 CBC 153 : if (isnan(lseg_closept_lseg(result, l2, l1)))
2865 45 : PG_RETURN_NULL();
2866 :
8288 tgl 2867 GIC 108 : PG_RETURN_POINT_P(result);
2868 : }
9770 scrappy 2869 ECB :
1715 tomas.vondra 2870 :
2871 : /*
9196 lockhart 2872 : * Closest point on or in box to specified point.
1715 tomas.vondra 2873 : *
1606 alvherre 2874 : * If *result is not NULL, set it to the closest point on the box to the
2875 : * given point, and return the distance of the two points.
9196 lockhart 2876 : */
1715 tomas.vondra 2877 : static float8
1715 tomas.vondra 2878 GIC 77994 : box_closept_point(Point *result, BOX *box, Point *pt)
9770 scrappy 2879 ECB : {
1697 tomas.vondra 2880 : float8 dist,
2881 : d;
2882 : Point point,
2883 : closept;
2884 : LSEG lseg;
2885 :
1715 tomas.vondra 2886 GIC 77994 : if (box_contain_point(box, pt))
2887 : {
1715 tomas.vondra 2888 CBC 21 : if (result != NULL)
1715 tomas.vondra 2889 GIC 3 : *result = *pt;
1715 tomas.vondra 2890 ECB :
1715 tomas.vondra 2891 CBC 21 : return 0.0;
2892 : }
2893 :
9196 lockhart 2894 ECB : /* pairwise check lseg distances */
9196 lockhart 2895 CBC 77973 : point.x = box->low.x;
9196 lockhart 2896 GIC 77973 : point.y = box->high.y;
9196 lockhart 2897 CBC 77973 : statlseg_construct(&lseg, &box->low, &point);
1715 tomas.vondra 2898 GIC 77973 : dist = lseg_closept_point(result, &lseg, pt);
9196 lockhart 2899 ECB :
1715 tomas.vondra 2900 CBC 77973 : statlseg_construct(&lseg, &box->high, &point);
1715 tomas.vondra 2901 GIC 77973 : d = lseg_closept_point(&closept, &lseg, pt);
1697 tomas.vondra 2902 CBC 77973 : if (float8_lt(d, dist))
2903 : {
8288 tgl 2904 GIC 3717 : dist = d;
1715 tomas.vondra 2905 3717 : if (result != NULL)
2906 27 : *result = closept;
2907 : }
2908 :
9196 lockhart 2909 77973 : point.x = box->high.x;
2910 77973 : point.y = box->low.y;
1715 tomas.vondra 2911 77973 : statlseg_construct(&lseg, &box->low, &point);
2912 77973 : d = lseg_closept_point(&closept, &lseg, pt);
1697 tomas.vondra 2913 CBC 77973 : if (float8_lt(d, dist))
2914 : {
8288 tgl 2915 GIC 3969 : dist = d;
1715 tomas.vondra 2916 3969 : if (result != NULL)
2917 3 : *result = closept;
2918 : }
2919 :
2920 77973 : statlseg_construct(&lseg, &box->high, &point);
1715 tomas.vondra 2921 CBC 77973 : d = lseg_closept_point(&closept, &lseg, pt);
1697 tomas.vondra 2922 GIC 77973 : if (float8_lt(d, dist))
9196 lockhart 2923 ECB : {
8288 tgl 2924 CBC 18 : dist = d;
1715 tomas.vondra 2925 GIC 18 : if (result != NULL)
1715 tomas.vondra 2926 CBC 6 : *result = closept;
2927 : }
2928 :
1715 tomas.vondra 2929 GIC 77973 : return dist;
8288 tgl 2930 ECB : }
9196 lockhart 2931 :
1715 tomas.vondra 2932 : Datum
1715 tomas.vondra 2933 CBC 150 : close_pb(PG_FUNCTION_ARGS)
2934 : {
2935 150 : Point *pt = PG_GETARG_POINT_P(0);
2936 150 : BOX *box = PG_GETARG_BOX_P(1);
1715 tomas.vondra 2937 ECB : Point *result;
2938 :
1715 tomas.vondra 2939 CBC 150 : result = (Point *) palloc(sizeof(Point));
1715 tomas.vondra 2940 ECB :
1697 tomas.vondra 2941 CBC 150 : if (isnan(box_closept_point(result, box, pt)))
1697 tomas.vondra 2942 GIC 15 : PG_RETURN_NULL();
2943 :
1715 tomas.vondra 2944 CBC 135 : PG_RETURN_POINT_P(result);
1715 tomas.vondra 2945 ECB : }
2946 :
2947 : /*
9196 lockhart 2948 : * Closest point on line segment to line.
2949 : *
1606 alvherre 2950 : * Return the distance between the line and the closest point of the line
2951 : * segment to the line. If *result is not NULL, set it to that point.
1715 tomas.vondra 2952 : *
2953 : * NOTE: When the lines are parallel, endpoints of one of the line segment
2954 : * are FPeq(), in presence of NaN or Infinite coordinates, or perhaps =
2955 : * even because of simple roundoff issues, there may not be a single closest
2956 : * point. We are likely to set the result to the second endpoint in these
2957 : * cases.
2958 : */
2959 : static float8
1715 tomas.vondra 2960 CBC 453741 : lseg_closept_line(Point *result, LSEG *lseg, LINE *line)
1715 tomas.vondra 2961 ECB : {
2962 : float8 dist1,
2963 : dist2;
2964 :
1715 tomas.vondra 2965 GIC 453741 : if (lseg_interpt_line(result, lseg, line))
2966 5901 : return 0.0;
2967 :
1715 tomas.vondra 2968 CBC 447840 : dist1 = line_closept_point(NULL, line, &lseg->p[0]);
1715 tomas.vondra 2969 GIC 447840 : dist2 = line_closept_point(NULL, line, &lseg->p[1]);
1715 tomas.vondra 2970 ECB :
1715 tomas.vondra 2971 CBC 447840 : if (dist1 < dist2)
2972 : {
1715 tomas.vondra 2973 GIC 237855 : if (result != NULL)
1715 tomas.vondra 2974 CBC 237753 : *result = lseg->p[0];
2975 :
2976 237855 : return dist1;
1715 tomas.vondra 2977 ECB : }
2978 : else
2979 : {
1715 tomas.vondra 2980 GIC 209985 : if (result != NULL)
2981 209709 : *result = lseg->p[1];
2982 :
2983 209985 : return dist2;
2984 : }
2985 : }
2986 :
2987 : Datum
8288 tgl 2988 240 : close_ls(PG_FUNCTION_ARGS)
2989 : {
2990 240 : LINE *line = PG_GETARG_LINE_P(0);
2991 240 : LSEG *lseg = PG_GETARG_LSEG_P(1);
2992 : Point *result;
2993 :
1656 tomas.vondra 2994 240 : if (lseg_sl(lseg) == line_sl(line))
1656 tomas.vondra 2995 CBC 27 : PG_RETURN_NULL();
2996 :
1715 tomas.vondra 2997 GIC 213 : result = (Point *) palloc(sizeof(Point));
2998 :
1697 2999 213 : if (isnan(lseg_closept_line(result, lseg, line)))
1697 tomas.vondra 3000 CBC 72 : PG_RETURN_NULL();
9196 lockhart 3001 ECB :
8288 tgl 3002 GIC 141 : PG_RETURN_POINT_P(result);
8288 tgl 3003 ECB : }
9196 lockhart 3004 :
3005 :
1715 tomas.vondra 3006 : /*
3007 : * Closest point on or in box to line segment.
3008 : *
1606 alvherre 3009 : * Returns the distance between the closest point on or in the box to
3010 : * the line segment. If *result is not NULL, it is set to that point.
9196 lockhart 3011 : */
3012 : static float8
1715 tomas.vondra 3013 GIC 360 : box_closept_lseg(Point *result, BOX *box, LSEG *lseg)
3014 : {
1697 tomas.vondra 3015 ECB : float8 dist,
3016 : d;
3017 : Point point,
1715 3018 : closept;
3019 : LSEG bseg;
3020 :
1715 tomas.vondra 3021 GIC 360 : if (box_interpt_lseg(result, box, lseg))
3022 72 : return 0.0;
9196 lockhart 3023 ECB :
3024 : /* pairwise check lseg distances */
9196 lockhart 3025 CBC 288 : point.x = box->low.x;
3026 288 : point.y = box->high.y;
9196 lockhart 3027 GIC 288 : statlseg_construct(&bseg, &box->low, &point);
1715 tomas.vondra 3028 288 : dist = lseg_closept_lseg(result, &bseg, lseg);
9196 lockhart 3029 ECB :
1715 tomas.vondra 3030 CBC 288 : statlseg_construct(&bseg, &box->high, &point);
1715 tomas.vondra 3031 GIC 288 : d = lseg_closept_lseg(&closept, &bseg, lseg);
1697 tomas.vondra 3032 CBC 288 : if (float8_lt(d, dist))
3033 : {
9196 lockhart 3034 72 : dist = d;
1715 tomas.vondra 3035 72 : if (result != NULL)
1715 tomas.vondra 3036 GIC 24 : *result = closept;
9196 lockhart 3037 ECB : }
3038 :
9196 lockhart 3039 GIC 288 : point.x = box->high.x;
3040 288 : point.y = box->low.y;
1715 tomas.vondra 3041 288 : statlseg_construct(&bseg, &box->low, &point);
3042 288 : d = lseg_closept_lseg(&closept, &bseg, lseg);
1697 3043 288 : if (float8_lt(d, dist))
3044 : {
9196 lockhart 3045 9 : dist = d;
1715 tomas.vondra 3046 9 : if (result != NULL)
3047 3 : *result = closept;
9196 lockhart 3048 ECB : }
3049 :
1715 tomas.vondra 3050 GIC 288 : statlseg_construct(&bseg, &box->high, &point);
3051 288 : d = lseg_closept_lseg(&closept, &bseg, lseg);
1697 3052 288 : if (float8_lt(d, dist))
3053 : {
9196 lockhart 3054 9 : dist = d;
1715 tomas.vondra 3055 9 : if (result != NULL)
1715 tomas.vondra 3056 CBC 3 : *result = closept;
9196 lockhart 3057 ECB : }
3058 :
1715 tomas.vondra 3059 GIC 288 : return dist;
8288 tgl 3060 ECB : }
9770 scrappy 3061 :
1715 tomas.vondra 3062 : Datum
1715 tomas.vondra 3063 CBC 120 : close_sb(PG_FUNCTION_ARGS)
3064 : {
3065 120 : LSEG *lseg = PG_GETARG_LSEG_P(0);
3066 120 : BOX *box = PG_GETARG_BOX_P(1);
1715 tomas.vondra 3067 ECB : Point *result;
3068 :
1715 tomas.vondra 3069 CBC 120 : result = (Point *) palloc(sizeof(Point));
1715 tomas.vondra 3070 ECB :
1697 tomas.vondra 3071 CBC 120 : if (isnan(box_closept_lseg(result, box, lseg)))
1697 tomas.vondra 3072 GIC 15 : PG_RETURN_NULL();
3073 :
1715 tomas.vondra 3074 CBC 105 : PG_RETURN_POINT_P(result);
1715 tomas.vondra 3075 ECB : }
3076 :
3077 :
9770 scrappy 3078 : /*---------------------------------------------------------------------
3079 : * on_
9345 bruce 3080 : * Whether one object lies completely within another.
9770 scrappy 3081 : *-------------------------------------------------------------------*/
3082 :
3083 : /*
3084 : * Does the point satisfy the equation?
3085 : */
1715 tomas.vondra 3086 : static bool
1715 tomas.vondra 3087 CBC 552 : line_contain_point(LINE *line, Point *point)
3088 : {
1697 3089 552 : return FPzero(float8_pl(float8_pl(float8_mul(line->A, point->x),
1697 tomas.vondra 3090 ECB : float8_mul(line->B, point->y)),
3091 : line->C));
3092 : }
3093 :
8288 tgl 3094 : Datum
8288 tgl 3095 GIC 300 : on_pl(PG_FUNCTION_ARGS)
3096 : {
3097 300 : Point *pt = PG_GETARG_POINT_P(0);
8288 tgl 3098 CBC 300 : LINE *line = PG_GETARG_LINE_P(1);
3099 :
1715 tomas.vondra 3100 300 : PG_RETURN_BOOL(line_contain_point(line, pt));
9770 scrappy 3101 ECB : }
3102 :
3103 :
1715 tomas.vondra 3104 : /*
3105 : * Determine colinearity by detecting a triangle inequality.
9385 lockhart 3106 : * This algorithm seems to behave nicely even with lsb residues - tgl 1997-07-09
9770 scrappy 3107 : */
3108 : static bool
1715 tomas.vondra 3109 CBC 2007429 : lseg_contain_point(LSEG *lseg, Point *pt)
3110 : {
1715 tomas.vondra 3111 GIC 4014858 : return FPeq(point_dt(pt, &lseg->p[0]) +
3112 2007429 : point_dt(pt, &lseg->p[1]),
3113 : point_dt(&lseg->p[0], &lseg->p[1]));
3114 : }
3115 :
3116 : Datum
8288 tgl 3117 240 : on_ps(PG_FUNCTION_ARGS)
3118 : {
3119 240 : Point *pt = PG_GETARG_POINT_P(0);
3120 240 : LSEG *lseg = PG_GETARG_LSEG_P(1);
3121 :
1715 tomas.vondra 3122 CBC 240 : PG_RETURN_BOOL(lseg_contain_point(lseg, pt));
3123 : }
9770 scrappy 3124 ECB :
3125 :
3126 : /*
3127 : * Check whether the point is in the box or on its border
3128 : */
3129 : static bool
1715 tomas.vondra 3130 CBC 218892 : box_contain_point(BOX *box, Point *point)
3131 : {
3132 126891 : return box->high.x >= point->x && box->low.x <= point->x &&
1418 tgl 3133 345783 : box->high.y >= point->y && box->low.y <= point->y;
3134 : }
8288 tgl 3135 ECB :
3136 : Datum
8288 tgl 3137 GIC 69126 : on_pb(PG_FUNCTION_ARGS)
3138 : {
3139 69126 : Point *pt = PG_GETARG_POINT_P(0);
3140 69126 : BOX *box = PG_GETARG_BOX_P(1);
3141 :
1715 tomas.vondra 3142 69126 : PG_RETURN_BOOL(box_contain_point(box, pt));
3143 : }
9770 scrappy 3144 ECB :
3145 : Datum
4790 bruce 3146 CBC 71343 : box_contain_pt(PG_FUNCTION_ARGS)
4833 teodor 3147 ECB : {
4833 teodor 3148 GIC 71343 : BOX *box = PG_GETARG_BOX_P(0);
3149 71343 : Point *pt = PG_GETARG_POINT_P(1);
3150 :
1715 tomas.vondra 3151 71343 : PG_RETURN_BOOL(box_contain_point(box, pt));
4833 teodor 3152 ECB : }
3153 :
9345 bruce 3154 : /* on_ppath -
3155 : * Whether a point lies within (on) a polyline.
3156 : * If open, we have to (groan) check each segment.
9385 lockhart 3157 : * (uses same algorithm as for point intersecting segment - tgl 1997-07-09)
3158 : * If closed, we use the old O(n) ray method for point-in-polygon.
3159 : * The ray is horizontal, from pt out to the right.
3160 : * Each segment that crosses the ray counts as an
3161 : * intersection; note that an endpoint or edge may touch
3162 : * but not cross.
3163 : * (we can do p-in-p in lg(n), but it takes preprocessing)
3164 : */
8289 tgl 3165 : Datum
8289 tgl 3166 GIC 300 : on_ppath(PG_FUNCTION_ARGS)
9770 scrappy 3167 ECB : {
8289 tgl 3168 CBC 300 : Point *pt = PG_GETARG_POINT_P(0);
8289 tgl 3169 GIC 300 : PATH *path = PG_GETARG_PATH_P(1);
3170 : int i,
3171 : n;
1697 tomas.vondra 3172 ECB : float8 a,
3173 : b;
9345 bruce 3174 :
8928 lockhart 3175 : /*-- OPEN --*/
9345 bruce 3176 GIC 300 : if (!path->closed)
8928 lockhart 3177 ECB : {
9345 bruce 3178 GIC 150 : n = path->npts - 1;
3179 150 : a = point_dt(pt, &path->p[0]);
3180 354 : for (i = 0; i < n; i++)
9345 bruce 3181 ECB : {
9345 bruce 3182 GIC 219 : b = point_dt(pt, &path->p[i + 1]);
1697 tomas.vondra 3183 CBC 219 : if (FPeq(float8_pl(a, b), point_dt(&path->p[i], &path->p[i + 1])))
8289 tgl 3184 15 : PG_RETURN_BOOL(true);
9345 bruce 3185 GIC 204 : a = b;
9345 bruce 3186 ECB : }
8289 tgl 3187 GIC 135 : PG_RETURN_BOOL(false);
3188 : }
3189 :
3190 : /*-- CLOSED --*/
3191 150 : PG_RETURN_BOOL(point_inside(pt, path->npts, path->p) != 0);
3192 : }
3193 :
3194 :
3195 : /*
3196 : * Check whether the line segment is on the line or close enough
3197 : *
3198 : * It is, if both of its points are on the line or close enough.
3199 : */
3200 : Datum
8288 tgl 3201 CBC 240 : on_sl(PG_FUNCTION_ARGS)
3202 : {
3203 240 : LSEG *lseg = PG_GETARG_LSEG_P(0);
3204 240 : LINE *line = PG_GETARG_LINE_P(1);
3205 :
1715 tomas.vondra 3206 GIC 240 : PG_RETURN_BOOL(line_contain_point(line, &lseg->p[0]) &&
3207 : line_contain_point(line, &lseg->p[1]));
3208 : }
3209 :
3210 :
1715 tomas.vondra 3211 ECB : /*
3212 : * Check whether the line segment is in the box or on its border
3213 : *
3214 : * It is, if both of its points are in the box or on its border.
3215 : */
3216 : static bool
1715 tomas.vondra 3217 CBC 120 : box_contain_lseg(BOX *box, LSEG *lseg)
1715 tomas.vondra 3218 ECB : {
1715 tomas.vondra 3219 CBC 129 : return box_contain_point(box, &lseg->p[0]) &&
1418 tgl 3220 9 : box_contain_point(box, &lseg->p[1]);
3221 : }
9770 scrappy 3222 ECB :
3223 : Datum
8288 tgl 3224 GIC 120 : on_sb(PG_FUNCTION_ARGS)
3225 : {
8288 tgl 3226 CBC 120 : LSEG *lseg = PG_GETARG_LSEG_P(0);
8288 tgl 3227 GIC 120 : BOX *box = PG_GETARG_BOX_P(1);
3228 :
1715 tomas.vondra 3229 120 : PG_RETURN_BOOL(box_contain_lseg(box, lseg));
3230 : }
3231 :
3232 : /*---------------------------------------------------------------------
3233 : * inter_
3234 : * Whether one object intersects another.
3235 : *-------------------------------------------------------------------*/
9770 scrappy 3236 ECB :
3237 : Datum
8288 tgl 3238 CBC 240 : inter_sl(PG_FUNCTION_ARGS)
9770 scrappy 3239 ECB : {
8288 tgl 3240 GIC 240 : LSEG *lseg = PG_GETARG_LSEG_P(0);
8288 tgl 3241 CBC 240 : LINE *line = PG_GETARG_LINE_P(1);
3242 :
1715 tomas.vondra 3243 GIC 240 : PG_RETURN_BOOL(lseg_interpt_line(NULL, lseg, line));
3244 : }
3245 :
3246 :
3247 : /*
3248 : * Do line segment and box intersect?
3249 : *
3250 : * Segment completely inside box counts as intersection.
3251 : * If you want only segments crossing box boundaries,
9173 bruce 3252 ECB : * try converting box to path first.
3253 : *
1715 tomas.vondra 3254 : * This function also sets the *result to the closest point on the line
3255 : * segment to the center of the box when they overlap and the result is
3256 : * not NULL. It is somewhat arbitrary, but maybe the best we can do as
3257 : * there are typically two points they intersect.
3258 : *
9196 lockhart 3259 : * Optimize for non-intersection by checking for box intersection first.
3260 : * - thomas 1998-01-30
3261 : */
1715 tomas.vondra 3262 : static bool
1715 tomas.vondra 3263 GIC 480 : box_interpt_lseg(Point *result, BOX *box, LSEG *lseg)
9770 scrappy 3264 ECB : {
3265 : BOX lbox;
3266 : LSEG bseg;
3267 : Point point;
3268 :
1697 tomas.vondra 3269 GIC 480 : lbox.low.x = float8_min(lseg->p[0].x, lseg->p[1].x);
3270 480 : lbox.low.y = float8_min(lseg->p[0].y, lseg->p[1].y);
3271 480 : lbox.high.x = float8_max(lseg->p[0].x, lseg->p[1].x);
3272 480 : lbox.high.y = float8_max(lseg->p[0].y, lseg->p[1].y);
9196 lockhart 3273 ECB :
3274 : /* nothing close to overlap? then not going to intersect */
8288 tgl 3275 CBC 480 : if (!box_ov(&lbox, box))
1715 tomas.vondra 3276 312 : return false;
3277 :
3278 168 : if (result != NULL)
3279 : {
1715 tomas.vondra 3280 GIC 42 : box_cn(&point, box);
3281 42 : lseg_closept_point(result, lseg, &point);
3282 : }
3283 :
3284 : /* an endpoint of segment is inside box? then clearly intersects */
3285 300 : if (box_contain_point(box, &lseg->p[0]) ||
3286 132 : box_contain_point(box, &lseg->p[1]))
3287 48 : return true;
3288 :
3289 : /* pairwise check lseg intersections */
9196 lockhart 3290 120 : point.x = box->low.x;
3291 120 : point.y = box->high.y;
3292 120 : statlseg_construct(&bseg, &box->low, &point);
1715 tomas.vondra 3293 120 : if (lseg_interpt_lseg(NULL, &bseg, lseg))
3294 48 : return true;
3295 :
9196 lockhart 3296 72 : statlseg_construct(&bseg, &box->high, &point);
1715 tomas.vondra 3297 72 : if (lseg_interpt_lseg(NULL, &bseg, lseg))
1715 tomas.vondra 3298 LBC 0 : return true;
3299 :
9196 lockhart 3300 GIC 72 : point.x = box->high.x;
3301 72 : point.y = box->low.y;
3302 72 : statlseg_construct(&bseg, &box->low, &point);
1715 tomas.vondra 3303 72 : if (lseg_interpt_lseg(NULL, &bseg, lseg))
1715 tomas.vondra 3304 LBC 0 : return true;
9196 lockhart 3305 ECB :
9196 lockhart 3306 CBC 72 : statlseg_construct(&bseg, &box->high, &point);
1715 tomas.vondra 3307 72 : if (lseg_interpt_lseg(NULL, &bseg, lseg))
1715 tomas.vondra 3308 UIC 0 : return true;
3309 :
9196 lockhart 3310 ECB : /* if we dropped through, no two segs intersected */
1715 tomas.vondra 3311 CBC 72 : return false;
3312 : }
9483 scrappy 3313 ECB :
3314 : Datum
1715 tomas.vondra 3315 CBC 120 : inter_sb(PG_FUNCTION_ARGS)
1715 tomas.vondra 3316 ECB : {
1715 tomas.vondra 3317 GIC 120 : LSEG *lseg = PG_GETARG_LSEG_P(0);
3318 120 : BOX *box = PG_GETARG_BOX_P(1);
3319 :
1715 tomas.vondra 3320 CBC 120 : PG_RETURN_BOOL(box_interpt_lseg(NULL, box, lseg));
1715 tomas.vondra 3321 ECB : }
3322 :
3323 :
3324 : /* inter_lb()
9196 lockhart 3325 : * Do line and box intersect?
3326 : */
8288 tgl 3327 : Datum
8288 tgl 3328 CBC 150 : inter_lb(PG_FUNCTION_ARGS)
9770 scrappy 3329 ECB : {
8288 tgl 3330 GIC 150 : LINE *line = PG_GETARG_LINE_P(0);
8288 tgl 3331 CBC 150 : BOX *box = PG_GETARG_BOX_P(1);
9196 lockhart 3332 ECB : LSEG bseg;
9196 lockhart 3333 EUB : Point p1,
3334 : p2;
9196 lockhart 3335 ECB :
3336 : /* pairwise check lseg intersections */
9196 lockhart 3337 CBC 150 : p1.x = box->low.x;
3338 150 : p1.y = box->low.y;
9196 lockhart 3339 GBC 150 : p2.x = box->low.x;
9196 lockhart 3340 GIC 150 : p2.y = box->high.y;
9196 lockhart 3341 CBC 150 : statlseg_construct(&bseg, &p1, &p2);
1715 tomas.vondra 3342 150 : if (lseg_interpt_line(NULL, &bseg, line))
8288 tgl 3343 GBC 33 : PG_RETURN_BOOL(true);
9196 lockhart 3344 GIC 117 : p1.x = box->high.x;
3345 117 : p1.y = box->high.y;
9196 lockhart 3346 CBC 117 : statlseg_construct(&bseg, &p1, &p2);
1715 tomas.vondra 3347 GIC 117 : if (lseg_interpt_line(NULL, &bseg, line))
8288 tgl 3348 6 : PG_RETURN_BOOL(true);
9196 lockhart 3349 111 : p2.x = box->high.x;
9196 lockhart 3350 CBC 111 : p2.y = box->low.y;
9196 lockhart 3351 GIC 111 : statlseg_construct(&bseg, &p1, &p2);
1715 tomas.vondra 3352 CBC 111 : if (lseg_interpt_line(NULL, &bseg, line))
8288 tgl 3353 LBC 0 : PG_RETURN_BOOL(true);
9196 lockhart 3354 GIC 111 : p1.x = box->low.x;
9196 lockhart 3355 CBC 111 : p1.y = box->low.y;
9196 lockhart 3356 GIC 111 : statlseg_construct(&bseg, &p1, &p2);
1715 tomas.vondra 3357 111 : if (lseg_interpt_line(NULL, &bseg, line))
8288 tgl 3358 UIC 0 : PG_RETURN_BOOL(true);
3359 :
3360 : /* if we dropped through, no intersection */
8288 tgl 3361 GIC 111 : PG_RETURN_BOOL(false);
3362 : }
9770 scrappy 3363 ECB :
3364 : /*------------------------------------------------------------------
3365 : * The following routines define a data type and operator class for
9345 bruce 3366 : * POLYGONS .... Part of which (the polygon's bounding box) is built on
3367 : * top of the BOX data type.
3368 : *
3369 : * make_bound_box - create the bounding box for the input polygon
3370 : *------------------------------------------------------------------*/
3371 :
9770 scrappy 3372 : /*---------------------------------------------------------------------
3373 : * Make the smallest bounding box for the given polygon.
3374 : *---------------------------------------------------------------------*/
9345 bruce 3375 : static void
9344 bruce 3376 CBC 30255 : make_bound_box(POLYGON *poly)
9345 bruce 3377 ECB : {
9344 3378 : int i;
1697 tomas.vondra 3379 : float8 x1,
9344 bruce 3380 : y1,
3381 : x2,
3382 : y2;
9345 3383 :
1715 tomas.vondra 3384 CBC 30255 : Assert(poly->npts > 0);
9483 scrappy 3385 ECB :
1715 tomas.vondra 3386 CBC 30255 : x1 = x2 = poly->p[0].x;
3387 30255 : y2 = y1 = poly->p[0].y;
1715 tomas.vondra 3388 GBC 361039 : for (i = 1; i < poly->npts; i++)
1715 tomas.vondra 3389 ECB : {
1697 tomas.vondra 3390 CBC 330784 : if (float8_lt(poly->p[i].x, x1))
1715 3391 33 : x1 = poly->p[i].x;
1697 3392 330784 : if (float8_gt(poly->p[i].x, x2))
1715 tomas.vondra 3393 GBC 180533 : x2 = poly->p[i].x;
1697 tomas.vondra 3394 GIC 330784 : if (float8_lt(poly->p[i].y, y1))
1715 3395 90201 : y1 = poly->p[i].y;
1697 tomas.vondra 3396 CBC 330784 : if (float8_gt(poly->p[i].y, y2))
1715 tomas.vondra 3397 GIC 90305 : y2 = poly->p[i].y;
3398 : }
3399 :
3400 30255 : poly->boundbox.low.x = x1;
3401 30255 : poly->boundbox.high.x = x2;
3402 30255 : poly->boundbox.low.y = y1;
3403 30255 : poly->boundbox.high.y = y2;
9770 scrappy 3404 30255 : }
3405 :
3406 : /*------------------------------------------------------------------
3407 : * poly_in - read in the polygon from a string specification
3408 : *
3409 : * External format:
3410 : * "((x0,y0),...,(xn,yn))"
9345 bruce 3411 ECB : * "x0,y0,...,xn,yn"
3412 : * also supports the older style "(x1,...,xn,y1,...yn)"
3413 : *------------------------------------------------------------------*/
3414 : Datum
8289 tgl 3415 GIC 203 : poly_in(PG_FUNCTION_ARGS)
3416 : {
3417 203 : char *str = PG_GETARG_CSTRING(0);
116 tgl 3418 GNC 203 : Node *escontext = fcinfo->context;
3419 : POLYGON *poly;
9344 bruce 3420 ECB : int npts;
3421 : int size;
3338 noah 3422 : int base_size;
2566 tgl 3423 : bool isopen;
9483 scrappy 3424 :
9345 bruce 3425 GIC 203 : if ((npts = pair_count(str, ',')) <= 0)
116 tgl 3426 GNC 18 : ereturn(escontext, (Datum) 0,
7196 tgl 3427 ECB : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2566 3428 : errmsg("invalid input syntax for type %s: \"%s\"",
3429 : "polygon", str)));
9483 scrappy 3430 :
3338 noah 3431 CBC 185 : base_size = sizeof(poly->p[0]) * npts;
2118 tgl 3432 185 : size = offsetof(POLYGON, p) + base_size;
3338 noah 3433 ECB :
3434 : /* Check for integer overflow */
3338 noah 3435 GIC 185 : if (base_size / npts != sizeof(poly->p[0]) || size <= base_size)
116 tgl 3436 UNC 0 : ereturn(escontext, (Datum) 0,
3338 noah 3437 ECB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
3438 : errmsg("too many points requested")));
3439 :
7452 bruce 3440 CBC 185 : poly = (POLYGON *) palloc0(size); /* zero any holes */
3441 :
5885 tgl 3442 GIC 185 : SET_VARSIZE(poly, size);
9345 bruce 3443 185 : poly->npts = npts;
3444 :
116 tgl 3445 GNC 185 : if (!path_decode(str, false, npts, &(poly->p[0]), &isopen, NULL, "polygon",
3446 : str, escontext))
3447 6 : PG_RETURN_NULL();
3448 :
9345 bruce 3449 GIC 176 : make_bound_box(poly);
3450 :
8289 tgl 3451 176 : PG_RETURN_POLYGON_P(poly);
3452 : }
9770 scrappy 3453 ECB :
3454 : /*---------------------------------------------------------------
9345 bruce 3455 : * poly_out - convert internal POLYGON representation to the
3456 : * character string format "((f8,f8),...,(f8,f8))"
3457 : *---------------------------------------------------------------*/
3458 : Datum
8289 tgl 3459 GIC 46833 : poly_out(PG_FUNCTION_ARGS)
3460 : {
8053 bruce 3461 46833 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
3462 :
3562 peter_e 3463 CBC 46833 : PG_RETURN_CSTRING(path_encode(PATH_CLOSED, poly->npts, poly->p));
8289 tgl 3464 ECB : }
3465 :
3466 : /*
3467 : * poly_recv - converts external binary format to polygon
3468 : *
7271 3469 : * External representation is int32 number of points, and the points.
3470 : * We recompute the bounding box on read, instead of trusting it to
3471 : * be valid. (Checking it would take just as long, so may as well
3472 : * omit it from external representation.)
3473 : */
7271 tgl 3474 EUB : Datum
7271 tgl 3475 UIC 0 : poly_recv(PG_FUNCTION_ARGS)
3476 : {
3477 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
7188 bruce 3478 ECB : POLYGON *poly;
3479 : int32 npts;
7271 tgl 3480 : int32 i;
3481 : int size;
3482 :
7271 tgl 3483 LBC 0 : npts = pq_getmsgint(buf, sizeof(int32));
2970 tgl 3484 UIC 0 : if (npts <= 0 || npts >= (int32) ((INT_MAX - offsetof(POLYGON, p)) / sizeof(Point)))
7196 tgl 3485 LBC 0 : ereport(ERROR,
3486 : (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
2118 tgl 3487 ECB : errmsg("invalid number of points in external \"polygon\" value")));
3488 :
2118 tgl 3489 LBC 0 : size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * npts;
7271 tgl 3490 UIC 0 : poly = (POLYGON *) palloc0(size); /* zero any holes */
3491 :
5885 3492 0 : SET_VARSIZE(poly, size);
7271 3493 0 : poly->npts = npts;
3494 :
3495 0 : for (i = 0; i < npts; i++)
3496 : {
7271 tgl 3497 LBC 0 : poly->p[i].x = pq_getmsgfloat8(buf);
7271 tgl 3498 UIC 0 : poly->p[i].y = pq_getmsgfloat8(buf);
7271 tgl 3499 ECB : }
3500 :
7271 tgl 3501 LBC 0 : make_bound_box(poly);
3502 :
7271 tgl 3503 UIC 0 : PG_RETURN_POLYGON_P(poly);
3504 : }
3505 :
3506 : /*
3507 : * poly_send - converts polygon to binary format
3508 : */
3509 : Datum
3510 0 : poly_send(PG_FUNCTION_ARGS)
3511 : {
7188 bruce 3512 0 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
7271 tgl 3513 EUB : StringInfoData buf;
3514 : int32 i;
3515 :
7271 tgl 3516 UIC 0 : pq_begintypsend(&buf);
2006 andres 3517 0 : pq_sendint32(&buf, poly->npts);
7271 tgl 3518 0 : for (i = 0; i < poly->npts; i++)
3519 : {
3520 0 : pq_sendfloat8(&buf, poly->p[i].x);
7271 tgl 3521 UBC 0 : pq_sendfloat8(&buf, poly->p[i].y);
7271 tgl 3522 EUB : }
7271 tgl 3523 UBC 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
3524 : }
3525 :
3526 :
9770 scrappy 3527 EUB : /*-------------------------------------------------------
3528 : * Is polygon A strictly left of polygon B? i.e. is
3529 : * the right most point of A left of the left most point
3530 : * of B?
3531 : *-------------------------------------------------------*/
3532 : Datum
8289 tgl 3533 GBC 147 : poly_left(PG_FUNCTION_ARGS)
3534 : {
8053 bruce 3535 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
3536 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3537 : bool result;
3538 :
8157 tgl 3539 147 : result = polya->boundbox.high.x < polyb->boundbox.low.x;
3540 :
8053 bruce 3541 EUB : /*
3542 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3543 : */
8157 tgl 3544 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3545 147 : PG_FREE_IF_COPY(polyb, 1);
3546 :
3547 147 : PG_RETURN_BOOL(result);
9770 scrappy 3548 EUB : }
3549 :
3550 : /*-------------------------------------------------------
3551 : * Is polygon A overlapping or left of polygon B? i.e. is
3552 : * the right most point of A at or left of the right most point
3553 : * of B?
3554 : *-------------------------------------------------------*/
8289 tgl 3555 : Datum
8289 tgl 3556 GBC 147 : poly_overleft(PG_FUNCTION_ARGS)
3557 : {
8053 bruce 3558 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
3559 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3560 : bool result;
8157 tgl 3561 EUB :
6498 tgl 3562 GIC 147 : result = polya->boundbox.high.x <= polyb->boundbox.high.x;
3563 :
3564 : /*
3565 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3566 : */
8157 3567 147 : PG_FREE_IF_COPY(polya, 0);
3568 147 : PG_FREE_IF_COPY(polyb, 1);
3569 :
3570 147 : PG_RETURN_BOOL(result);
9770 scrappy 3571 ECB : }
3572 :
3573 : /*-------------------------------------------------------
3574 : * Is polygon A strictly right of polygon B? i.e. is
3575 : * the left most point of A right of the right most point
3576 : * of B?
3577 : *-------------------------------------------------------*/
3578 : Datum
8289 tgl 3579 GIC 147 : poly_right(PG_FUNCTION_ARGS)
3580 : {
8053 bruce 3581 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
8053 bruce 3582 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
8157 tgl 3583 ECB : bool result;
3584 :
8157 tgl 3585 CBC 147 : result = polya->boundbox.low.x > polyb->boundbox.high.x;
3586 :
3587 : /*
3588 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3589 : */
8157 tgl 3590 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3591 147 : PG_FREE_IF_COPY(polyb, 1);
3592 :
3593 147 : PG_RETURN_BOOL(result);
9770 scrappy 3594 ECB : }
3595 :
3596 : /*-------------------------------------------------------
3597 : * Is polygon A overlapping or right of polygon B? i.e. is
3598 : * the left most point of A at or right of the left most point
3599 : * of B?
3600 : *-------------------------------------------------------*/
3601 : Datum
8289 tgl 3602 GIC 147 : poly_overright(PG_FUNCTION_ARGS)
3603 : {
8053 bruce 3604 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
8053 bruce 3605 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
8157 tgl 3606 ECB : bool result;
3607 :
6498 tgl 3608 CBC 147 : result = polya->boundbox.low.x >= polyb->boundbox.low.x;
3609 :
3610 : /*
3611 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3612 : */
6498 tgl 3613 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3614 147 : PG_FREE_IF_COPY(polyb, 1);
3615 :
3616 147 : PG_RETURN_BOOL(result);
6498 tgl 3617 ECB : }
3618 :
3619 : /*-------------------------------------------------------
3620 : * Is polygon A strictly below polygon B? i.e. is
3621 : * the upper most point of A below the lower most point
3622 : * of B?
3623 : *-------------------------------------------------------*/
3624 : Datum
6498 tgl 3625 GIC 147 : poly_below(PG_FUNCTION_ARGS)
3626 : {
3627 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
6498 tgl 3628 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
6498 tgl 3629 ECB : bool result;
3630 :
6498 tgl 3631 CBC 147 : result = polya->boundbox.high.y < polyb->boundbox.low.y;
3632 :
3633 : /*
3634 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3635 : */
8157 tgl 3636 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3637 147 : PG_FREE_IF_COPY(polyb, 1);
3638 :
3639 147 : PG_RETURN_BOOL(result);
9770 scrappy 3640 ECB : }
3641 :
6498 tgl 3642 : /*-------------------------------------------------------
3643 : * Is polygon A overlapping or below polygon B? i.e. is
3644 : * the upper most point of A at or below the upper most point
3645 : * of B?
3646 : *-------------------------------------------------------*/
3647 : Datum
6498 tgl 3648 GIC 147 : poly_overbelow(PG_FUNCTION_ARGS)
3649 : {
3650 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
6498 tgl 3651 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
6498 tgl 3652 ECB : bool result;
3653 :
6498 tgl 3654 CBC 147 : result = polya->boundbox.high.y <= polyb->boundbox.high.y;
3655 :
3656 : /*
3657 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3658 : */
6498 tgl 3659 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3660 147 : PG_FREE_IF_COPY(polyb, 1);
3661 :
3662 147 : PG_RETURN_BOOL(result);
6498 tgl 3663 ECB : }
3664 :
3665 : /*-------------------------------------------------------
3666 : * Is polygon A strictly above polygon B? i.e. is
3667 : * the lower most point of A above the upper most point
3668 : * of B?
3669 : *-------------------------------------------------------*/
3670 : Datum
6498 tgl 3671 GIC 147 : poly_above(PG_FUNCTION_ARGS)
3672 : {
3673 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
6498 tgl 3674 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
6498 tgl 3675 ECB : bool result;
3676 :
6498 tgl 3677 CBC 147 : result = polya->boundbox.low.y > polyb->boundbox.high.y;
3678 :
3679 : /*
3680 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3681 : */
6498 tgl 3682 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3683 147 : PG_FREE_IF_COPY(polyb, 1);
3684 :
3685 147 : PG_RETURN_BOOL(result);
6498 tgl 3686 ECB : }
3687 :
3688 : /*-------------------------------------------------------
3689 : * Is polygon A overlapping or above polygon B? i.e. is
3690 : * the lower most point of A at or above the lower most point
3691 : * of B?
3692 : *-------------------------------------------------------*/
3693 : Datum
6498 tgl 3694 GIC 147 : poly_overabove(PG_FUNCTION_ARGS)
3695 : {
3696 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
6498 tgl 3697 CBC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
6498 tgl 3698 ECB : bool result;
3699 :
6498 tgl 3700 CBC 147 : result = polya->boundbox.low.y >= polyb->boundbox.low.y;
3701 :
3702 : /*
3703 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3704 : */
6498 tgl 3705 GIC 147 : PG_FREE_IF_COPY(polya, 0);
3706 147 : PG_FREE_IF_COPY(polyb, 1);
3707 :
3708 147 : PG_RETURN_BOOL(result);
6498 tgl 3709 ECB : }
3710 :
3711 :
9770 scrappy 3712 : /*-------------------------------------------------------
3713 : * Is polygon A the same as polygon B? i.e. are all the
3714 : * points the same?
9385 lockhart 3715 : * Check all points for matches in both forward and reverse
3716 : * direction since polygons are non-directional and are
3717 : * closed shapes.
3718 : *-------------------------------------------------------*/
3719 : Datum
8289 tgl 3720 CBC 3148 : poly_same(PG_FUNCTION_ARGS)
9770 scrappy 3721 ECB : {
8053 bruce 3722 GIC 3148 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
8053 bruce 3723 CBC 3148 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3724 : bool result;
3725 :
9345 bruce 3726 GIC 3148 : if (polya->npts != polyb->npts)
8157 tgl 3727 102 : result = false;
3728 : else
3729 3046 : result = plist_same(polya->npts, polya->p, polyb->p);
3730 :
3731 : /*
6385 bruce 3732 ECB : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3733 : */
8157 tgl 3734 CBC 3148 : PG_FREE_IF_COPY(polya, 0);
3735 3148 : PG_FREE_IF_COPY(polyb, 1);
3736 :
8157 tgl 3737 GIC 3148 : PG_RETURN_BOOL(result);
8289 tgl 3738 ECB : }
3739 :
3740 : /*-----------------------------------------------------------------
3741 : * Determine if polygon A overlaps polygon B
3742 : *-----------------------------------------------------------------*/
482 3743 : static bool
482 tgl 3744 CBC 14709 : poly_overlap_internal(POLYGON *polya, POLYGON *polyb)
3745 : {
8157 tgl 3746 ECB : bool result;
3747 :
1715 tomas.vondra 3748 GIC 14709 : Assert(polya->npts > 0 && polyb->npts > 0);
3749 :
3750 : /* Quick check by bounding box */
3751 14709 : result = box_ov(&polya->boundbox, &polyb->boundbox);
3752 :
3753 : /*
3754 : * Brute-force algorithm - try to find intersected edges, if so then
3755 : * polygons are overlapped else check is one polygon inside other or not
3756 : * by testing single point of them.
3757 : */
5003 teodor 3758 CBC 14709 : if (result)
3759 : {
4790 bruce 3760 ECB : int ia,
3761 : ib;
3762 : LSEG sa,
3763 : sb;
5003 teodor 3764 :
3765 : /* Init first of polya's edge with last point */
5003 teodor 3766 GIC 5307 : sa.p[0] = polya->p[polya->npts - 1];
5003 teodor 3767 CBC 5307 : result = false;
3768 :
1715 tomas.vondra 3769 GIC 63273 : for (ia = 0; ia < polya->npts && !result; ia++)
3770 : {
3771 : /* Second point of polya's edge is a current one */
5003 teodor 3772 CBC 57966 : sa.p[1] = polya->p[ia];
5003 teodor 3773 ECB :
3774 : /* Init first of polyb's edge with last point */
5003 teodor 3775 CBC 57966 : sb.p[0] = polyb->p[polyb->npts - 1];
3776 :
1715 tomas.vondra 3777 GIC 288507 : for (ib = 0; ib < polyb->npts && !result; ib++)
3778 : {
5003 teodor 3779 230541 : sb.p[1] = polyb->p[ib];
1715 tomas.vondra 3780 230541 : result = lseg_interpt_lseg(NULL, &sa, &sb);
5003 teodor 3781 230541 : sb.p[0] = sb.p[1];
5003 teodor 3782 ECB : }
3783 :
3784 : /*
3785 : * move current endpoint to the first point of next edge
3786 : */
5003 teodor 3787 GIC 57966 : sa.p[0] = sa.p[1];
3788 : }
5003 teodor 3789 ECB :
1715 tomas.vondra 3790 GIC 5307 : if (!result)
3791 : {
3792 6951 : result = (point_inside(polya->p, polyb->npts, polyb->p) ||
4790 bruce 3793 2214 : point_inside(polyb->p, polya->npts, polya->p));
3794 : }
3795 : }
8157 tgl 3796 ECB :
482 tgl 3797 GIC 14709 : return result;
3798 : }
3799 :
3800 : Datum
3801 14562 : poly_overlap(PG_FUNCTION_ARGS)
3802 : {
3803 14562 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
482 tgl 3804 CBC 14562 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
482 tgl 3805 ECB : bool result;
3806 :
482 tgl 3807 CBC 14562 : result = poly_overlap_internal(polya, polyb);
3808 :
3809 : /*
6385 bruce 3810 ECB : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3811 : */
8157 tgl 3812 GIC 14562 : PG_FREE_IF_COPY(polya, 0);
8157 tgl 3813 CBC 14562 : PG_FREE_IF_COPY(polyb, 1);
3814 :
3815 14562 : PG_RETURN_BOOL(result);
3816 : }
9770 scrappy 3817 ECB :
5003 teodor 3818 : /*
3819 : * Tests special kind of segment for in/out of polygon.
3820 : * Special kind means:
3821 : * - point a should be on segment s
3822 : * - segment (a,b) should not be contained by s
3823 : * Returns true if:
3824 : * - segment (a,b) is collinear to s and (a,b) is in polygon
4790 bruce 3825 : * - segment (a,b) s not collinear to s. Note: that doesn't
3826 : * mean that segment is in polygon!
3827 : */
5003 teodor 3828 :
3829 : static bool
5003 teodor 3830 CBC 303 : touched_lseg_inside_poly(Point *a, Point *b, LSEG *s, POLYGON *poly, int start)
5003 teodor 3831 ECB : {
3832 : /* point a is on s, b is not */
3833 : LSEG t;
3834 :
5003 teodor 3835 CBC 303 : t.p[0] = *a;
5003 teodor 3836 GIC 303 : t.p[1] = *b;
3837 :
1715 tomas.vondra 3838 303 : if (point_eq_point(a, s->p))
5003 teodor 3839 ECB : {
1715 tomas.vondra 3840 GIC 36 : if (lseg_contain_point(&t, s->p + 1))
4790 bruce 3841 LBC 0 : return lseg_inside_poly(b, s->p + 1, poly, start);
5003 teodor 3842 ECB : }
1715 tomas.vondra 3843 GIC 267 : else if (point_eq_point(a, s->p + 1))
3844 : {
1715 tomas.vondra 3845 CBC 78 : if (lseg_contain_point(&t, s->p))
5003 teodor 3846 UIC 0 : return lseg_inside_poly(b, s->p, poly, start);
3847 : }
1715 tomas.vondra 3848 GIC 189 : else if (lseg_contain_point(&t, s->p))
3849 : {
5003 teodor 3850 LBC 0 : return lseg_inside_poly(b, s->p, poly, start);
5003 teodor 3851 ECB : }
1715 tomas.vondra 3852 GIC 189 : else if (lseg_contain_point(&t, s->p + 1))
5003 teodor 3853 ECB : {
4790 bruce 3854 UIC 0 : return lseg_inside_poly(b, s->p + 1, poly, start);
3855 : }
3856 :
4790 bruce 3857 GIC 303 : return true; /* may be not true, but that will check later */
3858 : }
3859 :
3860 : /*
3861 : * Returns true if segment (a,b) is in polygon, option
3862 : * start is used for optimization - function checks
3863 : * polygon's edges starting from start
3864 : */
3865 : static bool
5003 teodor 3866 99138 : lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
3867 : {
4790 bruce 3868 ECB : LSEG s,
3869 : t;
3870 : int i;
4790 bruce 3871 GIC 99138 : bool res = true,
3872 99138 : intersection = false;
5003 teodor 3873 ECB :
228 tgl 3874 : /* since this function recurses, it could be driven to stack overflow */
228 tgl 3875 GIC 99138 : check_stack_depth();
228 tgl 3876 ECB :
5003 teodor 3877 GIC 99138 : t.p[0] = *a;
5003 teodor 3878 CBC 99138 : t.p[1] = *b;
4790 bruce 3879 GBC 99138 : s.p[0] = poly->p[(start == 0) ? (poly->npts - 1) : (start - 1)];
3880 :
4529 rhaas 3881 CBC 490347 : for (i = start; i < poly->npts && res; i++)
3882 : {
1715 tomas.vondra 3883 ECB : Point interpt;
5003 teodor 3884 EUB :
2673 alvherre 3885 GIC 391443 : CHECK_FOR_INTERRUPTS();
2673 alvherre 3886 ECB :
5003 teodor 3887 GIC 391443 : s.p[1] = poly->p[i];
5003 teodor 3888 EUB :
1715 tomas.vondra 3889 GIC 391443 : if (lseg_contain_point(&s, t.p))
5003 teodor 3890 ECB : {
1715 tomas.vondra 3891 GIC 393 : if (lseg_contain_point(&s, t.p + 1))
4790 bruce 3892 GBC 234 : return true; /* t is contained by s */
3893 :
3894 : /* Y-cross */
4790 bruce 3895 CBC 159 : res = touched_lseg_inside_poly(t.p, t.p + 1, &s, poly, i + 1);
3896 : }
1715 tomas.vondra 3897 GIC 391050 : else if (lseg_contain_point(&s, t.p + 1))
3898 : {
3899 : /* Y-cross */
4790 bruce 3900 144 : res = touched_lseg_inside_poly(t.p + 1, t.p, &s, poly, i + 1);
3901 : }
1715 tomas.vondra 3902 390906 : else if (lseg_interpt_lseg(&interpt, &t, &s))
3903 : {
5003 teodor 3904 ECB : /*
3905 : * segments are X-crossing, go to check each subsegment
3906 : */
3907 :
5003 teodor 3908 GIC 675 : intersection = true;
1715 tomas.vondra 3909 CBC 675 : res = lseg_inside_poly(t.p, &interpt, poly, i + 1);
5003 teodor 3910 675 : if (res)
1715 tomas.vondra 3911 GIC 579 : res = lseg_inside_poly(t.p + 1, &interpt, poly, i + 1);
3912 : }
5003 teodor 3913 ECB :
5003 teodor 3914 GIC 391209 : s.p[0] = s.p[1];
5003 teodor 3915 ECB : }
3916 :
5003 teodor 3917 CBC 98904 : if (res && !intersection)
3918 : {
4790 bruce 3919 ECB : Point p;
3920 :
3921 : /*
3922 : * if X-intersection wasn't found, then check central point of tested
3923 : * segment. In opposite case we already check all subsegments
3924 : */
1697 tomas.vondra 3925 CBC 98229 : p.x = float8_div(float8_pl(t.p[0].x, t.p[1].x), 2.0);
1697 tomas.vondra 3926 GIC 98229 : p.y = float8_div(float8_pl(t.p[0].y, t.p[1].y), 2.0);
5003 teodor 3927 ECB :
4790 bruce 3928 GIC 98229 : res = point_inside(&p, poly->npts, poly->p);
5003 teodor 3929 ECB : }
3930 :
5003 teodor 3931 GIC 98904 : return res;
3932 : }
9385 lockhart 3933 ECB :
3934 : /*
1606 alvherre 3935 : * Check whether the first polygon contains the second
3936 : */
3937 : static bool
1606 alvherre 3938 CBC 42465 : poly_contain_poly(POLYGON *contains_poly, POLYGON *contained_poly)
3939 : {
1715 tomas.vondra 3940 ECB : int i;
3941 : LSEG s;
3942 :
1606 alvherre 3943 GIC 42465 : Assert(contains_poly->npts > 0 && contained_poly->npts > 0);
3944 :
3945 : /*
1606 alvherre 3946 ECB : * Quick check to see if contained's bounding box is contained in
3947 : * contains' bb.
8289 tgl 3948 : */
1606 alvherre 3949 CBC 42465 : if (!box_contain_box(&contains_poly->boundbox, &contained_poly->boundbox))
1715 tomas.vondra 3950 GIC 28671 : return false;
3951 :
1606 alvherre 3952 CBC 13794 : s.p[0] = contained_poly->p[contained_poly->npts - 1];
3953 :
1606 alvherre 3954 GIC 105444 : for (i = 0; i < contained_poly->npts; i++)
8157 tgl 3955 ECB : {
1606 alvherre 3956 GIC 97884 : s.p[1] = contained_poly->p[i];
3957 97884 : if (!lseg_inside_poly(s.p, s.p + 1, contains_poly, 0))
1715 tomas.vondra 3958 6234 : return false;
3959 91650 : s.p[0] = s.p[1];
3960 : }
3961 :
3962 7560 : return true;
1715 tomas.vondra 3963 ECB : }
3964 :
3965 : Datum
1715 tomas.vondra 3966 CBC 192 : poly_contain(PG_FUNCTION_ARGS)
3967 : {
1715 tomas.vondra 3968 GIC 192 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
1715 tomas.vondra 3969 CBC 192 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3970 : bool result;
3971 :
1715 tomas.vondra 3972 GIC 192 : result = poly_contain_poly(polya, polyb);
3973 :
3974 : /*
3975 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
8053 bruce 3976 ECB : */
8157 tgl 3977 GIC 192 : PG_FREE_IF_COPY(polya, 0);
3978 192 : PG_FREE_IF_COPY(polyb, 1);
3979 :
3980 192 : PG_RETURN_BOOL(result);
8289 tgl 3981 ECB : }
3982 :
3983 :
3984 : /*-----------------------------------------------------------------
3985 : * Determine if polygon A is contained by polygon B
3986 : *-----------------------------------------------------------------*/
3987 : Datum
8289 tgl 3988 CBC 42273 : poly_contained(PG_FUNCTION_ARGS)
3989 : {
1715 tomas.vondra 3990 42273 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
1715 tomas.vondra 3991 GIC 42273 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
1715 tomas.vondra 3992 ECB : bool result;
3993 :
6498 tgl 3994 : /* Just switch the arguments and pass it off to poly_contain */
1715 tomas.vondra 3995 CBC 42273 : result = poly_contain_poly(polyb, polya);
1715 tomas.vondra 3996 ECB :
3997 : /*
3998 : * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3999 : */
1715 tomas.vondra 4000 CBC 42273 : PG_FREE_IF_COPY(polya, 0);
1715 tomas.vondra 4001 GIC 42273 : PG_FREE_IF_COPY(polyb, 1);
4002 :
4003 42273 : PG_RETURN_BOOL(result);
8289 tgl 4004 ECB : }
4005 :
9385 lockhart 4006 :
8289 tgl 4007 : Datum
8289 tgl 4008 GIC 222 : poly_contain_pt(PG_FUNCTION_ARGS)
4009 : {
8053 bruce 4010 CBC 222 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
8289 tgl 4011 GIC 222 : Point *p = PG_GETARG_POINT_P(1);
4012 :
4013 222 : PG_RETURN_BOOL(point_inside(p, poly->npts, poly->p) != 0);
4014 : }
9385 lockhart 4015 ECB :
8289 tgl 4016 : Datum
8289 tgl 4017 GIC 241 : pt_contained_poly(PG_FUNCTION_ARGS)
9385 lockhart 4018 ECB : {
8289 tgl 4019 GIC 241 : Point *p = PG_GETARG_POINT_P(0);
8053 bruce 4020 241 : POLYGON *poly = PG_GETARG_POLYGON_P(1);
4021 :
8289 tgl 4022 241 : PG_RETURN_BOOL(point_inside(p, poly->npts, poly->p) != 0);
4023 : }
4024 :
4025 :
8289 tgl 4026 ECB : Datum
8289 tgl 4027 GIC 147 : poly_distance(PG_FUNCTION_ARGS)
9385 lockhart 4028 ECB : {
8053 bruce 4029 CBC 147 : POLYGON *polya = PG_GETARG_POLYGON_P(0);
8053 bruce 4030 GIC 147 : POLYGON *polyb = PG_GETARG_POLYGON_P(1);
482 tgl 4031 147 : float8 min = 0.0; /* initialize to keep compiler quiet */
4032 147 : bool have_min = false;
482 tgl 4033 ECB : float8 tmp;
4034 : int i,
4035 : j;
4036 : LSEG seg1,
4037 : seg2;
9385 lockhart 4038 :
482 tgl 4039 : /*
4040 : * Distance is zero if polygons overlap. We must check this because the
4041 : * path distance will not give the right answer if one poly is entirely
4042 : * within the other.
4043 : */
482 tgl 4044 GIC 147 : if (poly_overlap_internal(polya, polyb))
4045 75 : PG_RETURN_FLOAT8(0.0);
9385 lockhart 4046 ECB :
4047 : /*
482 tgl 4048 : * When they don't overlap, the distance calculation is identical to that
4049 : * for closed paths (i.e., we needn't care about the fact that polygons
4050 : * include their contained areas). See path_distance().
4051 : */
482 tgl 4052 GIC 264 : for (i = 0; i < polya->npts; i++)
4053 : {
4054 : int iprev;
482 tgl 4055 ECB :
482 tgl 4056 GIC 192 : if (i > 0)
482 tgl 4057 CBC 120 : iprev = i - 1;
482 tgl 4058 ECB : else
482 tgl 4059 GIC 72 : iprev = polya->npts - 1;
482 tgl 4060 ECB :
482 tgl 4061 GIC 654 : for (j = 0; j < polyb->npts; j++)
4062 : {
4063 : int jprev;
4064 :
482 tgl 4065 CBC 462 : if (j > 0)
482 tgl 4066 GIC 270 : jprev = j - 1;
482 tgl 4067 ECB : else
482 tgl 4068 CBC 192 : jprev = polyb->npts - 1;
482 tgl 4069 ECB :
482 tgl 4070 CBC 462 : statlseg_construct(&seg1, &polya->p[iprev], &polya->p[i]);
482 tgl 4071 GIC 462 : statlseg_construct(&seg2, &polyb->p[jprev], &polyb->p[j]);
4072 :
4073 462 : tmp = lseg_closept_lseg(NULL, &seg1, &seg2);
4074 462 : if (!have_min || float8_lt(tmp, min))
4075 : {
4076 96 : min = tmp;
4077 96 : have_min = true;
4078 : }
4079 : }
4080 : }
4081 :
482 tgl 4082 CBC 72 : if (!have_min)
482 tgl 4083 LBC 0 : PG_RETURN_NULL();
4084 :
482 tgl 4085 GIC 72 : PG_RETURN_FLOAT8(min);
4086 : }
4087 :
4088 :
4089 : /***********************************************************************
9483 scrappy 4090 ECB : **
4091 : ** Routines for 2D points.
4092 : **
4093 : ***********************************************************************/
4094 :
8288 tgl 4095 : Datum
8288 tgl 4096 GIC 526948 : construct_point(PG_FUNCTION_ARGS)
9483 scrappy 4097 ECB : {
8288 tgl 4098 GIC 526948 : float8 x = PG_GETARG_FLOAT8(0);
8288 tgl 4099 CBC 526948 : float8 y = PG_GETARG_FLOAT8(1);
4100 : Point *result;
4101 :
1715 tomas.vondra 4102 GIC 526948 : result = (Point *) palloc(sizeof(Point));
9483 scrappy 4103 ECB :
1715 tomas.vondra 4104 CBC 526948 : point_construct(result, x, y);
4105 :
4106 526948 : PG_RETURN_POINT_P(result);
4107 : }
1715 tomas.vondra 4108 ECB :
4109 :
4110 : static inline void
1715 tomas.vondra 4111 CBC 1536 : point_add_point(Point *result, Point *pt1, Point *pt2)
1715 tomas.vondra 4112 ECB : {
1715 tomas.vondra 4113 GIC 1536 : point_construct(result,
1697 tomas.vondra 4114 ECB : float8_pl(pt1->x, pt2->x),
4115 : float8_pl(pt1->y, pt2->y));
8288 tgl 4116 GIC 1536 : }
4117 :
4118 : Datum
4119 300 : point_add(PG_FUNCTION_ARGS)
9483 scrappy 4120 ECB : {
8288 tgl 4121 GBC 300 : Point *p1 = PG_GETARG_POINT_P(0);
8288 tgl 4122 GIC 300 : Point *p2 = PG_GETARG_POINT_P(1);
9344 bruce 4123 ECB : Point *result;
4124 :
8288 tgl 4125 GIC 300 : result = (Point *) palloc(sizeof(Point));
4126 :
1715 tomas.vondra 4127 300 : point_add_point(result, p1, p2);
4128 :
8288 tgl 4129 300 : PG_RETURN_POINT_P(result);
4130 : }
4131 :
4132 :
4133 : static inline void
1715 tomas.vondra 4134 CBC 1410 : point_sub_point(Point *result, Point *pt1, Point *pt2)
4135 : {
4136 1410 : point_construct(result,
1697 tomas.vondra 4137 ECB : float8_mi(pt1->x, pt2->x),
4138 : float8_mi(pt1->y, pt2->y));
1715 tomas.vondra 4139 GIC 1410 : }
1715 tomas.vondra 4140 ECB :
4141 : Datum
8288 tgl 4142 CBC 300 : point_sub(PG_FUNCTION_ARGS)
4143 : {
4144 300 : Point *p1 = PG_GETARG_POINT_P(0);
8288 tgl 4145 GIC 300 : Point *p2 = PG_GETARG_POINT_P(1);
4146 : Point *result;
4147 :
4148 300 : result = (Point *) palloc(sizeof(Point));
9483 scrappy 4149 ECB :
1715 tomas.vondra 4150 GIC 300 : point_sub_point(result, p1, p2);
9483 scrappy 4151 ECB :
8288 tgl 4152 GIC 300 : PG_RETURN_POINT_P(result);
4153 : }
9483 scrappy 4154 ECB :
4155 :
4156 : static inline void
1715 tomas.vondra 4157 CBC 1110 : point_mul_point(Point *result, Point *pt1, Point *pt2)
4158 : {
4159 1110 : point_construct(result,
1697 tomas.vondra 4160 ECB : float8_mi(float8_mul(pt1->x, pt2->x),
4161 : float8_mul(pt1->y, pt2->y)),
4162 : float8_pl(float8_mul(pt1->x, pt2->y),
4163 : float8_mul(pt1->y, pt2->x)));
1715 tomas.vondra 4164 GIC 1107 : }
1715 tomas.vondra 4165 ECB :
4166 : Datum
8288 tgl 4167 CBC 150 : point_mul(PG_FUNCTION_ARGS)
4168 : {
8288 tgl 4169 GIC 150 : Point *p1 = PG_GETARG_POINT_P(0);
4170 150 : Point *p2 = PG_GETARG_POINT_P(1);
4171 : Point *result;
9483 scrappy 4172 ECB :
8288 tgl 4173 GIC 150 : result = (Point *) palloc(sizeof(Point));
9483 scrappy 4174 ECB :
1715 tomas.vondra 4175 GIC 150 : point_mul_point(result, p1, p2);
4176 :
8288 tgl 4177 CBC 147 : PG_RETURN_POINT_P(result);
4178 : }
4179 :
1715 tomas.vondra 4180 ECB :
4181 : static inline void
1715 tomas.vondra 4182 CBC 297 : point_div_point(Point *result, Point *pt1, Point *pt2)
9483 scrappy 4183 ECB : {
4184 : float8 div;
4185 :
1697 tomas.vondra 4186 CBC 297 : div = float8_pl(float8_mul(pt2->x, pt2->x), float8_mul(pt2->y, pt2->y));
4187 :
1715 4188 291 : point_construct(result,
4189 : float8_div(float8_pl(float8_mul(pt1->x, pt2->x),
1697 tomas.vondra 4190 ECB : float8_mul(pt1->y, pt2->y)), div),
4191 : float8_div(float8_mi(float8_mul(pt1->y, pt2->x),
4192 : float8_mul(pt1->x, pt2->y)), div));
1715 tomas.vondra 4193 GIC 282 : }
4194 :
1715 tomas.vondra 4195 ECB : Datum
1715 tomas.vondra 4196 GIC 66 : point_div(PG_FUNCTION_ARGS)
1715 tomas.vondra 4197 ECB : {
1715 tomas.vondra 4198 GIC 66 : Point *p1 = PG_GETARG_POINT_P(0);
4199 66 : Point *p2 = PG_GETARG_POINT_P(1);
4200 : Point *result;
4201 :
1715 tomas.vondra 4202 CBC 66 : result = (Point *) palloc(sizeof(Point));
4203 :
1715 tomas.vondra 4204 GIC 66 : point_div_point(result, p1, p2);
9483 scrappy 4205 ECB :
8288 tgl 4206 GIC 60 : PG_RETURN_POINT_P(result);
8288 tgl 4207 ECB : }
9483 scrappy 4208 :
4209 :
4210 : /***********************************************************************
4211 : **
4212 : ** Routines for 2D boxes.
4213 : **
4214 : ***********************************************************************/
4215 :
4216 : Datum
8288 tgl 4217 GIC 120852 : points_box(PG_FUNCTION_ARGS)
4218 : {
4219 120852 : Point *p1 = PG_GETARG_POINT_P(0);
8288 tgl 4220 CBC 120852 : Point *p2 = PG_GETARG_POINT_P(1);
4221 : BOX *result;
4222 :
1715 tomas.vondra 4223 GIC 120852 : result = (BOX *) palloc(sizeof(BOX));
1715 tomas.vondra 4224 ECB :
1715 tomas.vondra 4225 GIC 120852 : box_construct(result, p1, p2);
1715 tomas.vondra 4226 ECB :
1715 tomas.vondra 4227 GIC 120852 : PG_RETURN_BOX_P(result);
4228 : }
4229 :
4230 : Datum
8288 tgl 4231 CBC 150 : box_add(PG_FUNCTION_ARGS)
4232 : {
8288 tgl 4233 GIC 150 : BOX *box = PG_GETARG_BOX_P(0);
8288 tgl 4234 CBC 150 : Point *p = PG_GETARG_POINT_P(1);
4235 : BOX *result;
1715 tomas.vondra 4236 ECB :
1715 tomas.vondra 4237 CBC 150 : result = (BOX *) palloc(sizeof(BOX));
4238 :
1715 tomas.vondra 4239 GIC 150 : point_add_point(&result->high, &box->high, p);
1715 tomas.vondra 4240 CBC 150 : point_add_point(&result->low, &box->low, p);
4241 :
4242 150 : PG_RETURN_BOX_P(result);
4243 : }
9483 scrappy 4244 ECB :
4245 : Datum
8288 tgl 4246 GIC 150 : box_sub(PG_FUNCTION_ARGS)
4247 : {
4248 150 : BOX *box = PG_GETARG_BOX_P(0);
4249 150 : Point *p = PG_GETARG_POINT_P(1);
4250 : BOX *result;
4251 :
1715 tomas.vondra 4252 150 : result = (BOX *) palloc(sizeof(BOX));
4253 :
4254 150 : point_sub_point(&result->high, &box->high, p);
1715 tomas.vondra 4255 CBC 150 : point_sub_point(&result->low, &box->low, p);
4256 :
4257 150 : PG_RETURN_BOX_P(result);
8288 tgl 4258 ECB : }
4259 :
4260 : Datum
8288 tgl 4261 CBC 75 : box_mul(PG_FUNCTION_ARGS)
4262 : {
4263 75 : BOX *box = PG_GETARG_BOX_P(0);
8288 tgl 4264 GIC 75 : Point *p = PG_GETARG_POINT_P(1);
9344 bruce 4265 ECB : BOX *result;
4266 : Point high,
4267 : low;
4268 :
1715 tomas.vondra 4269 CBC 75 : result = (BOX *) palloc(sizeof(BOX));
4270 :
4271 75 : point_mul_point(&high, &box->high, p);
4272 75 : point_mul_point(&low, &box->low, p);
4273 :
1715 tomas.vondra 4274 GIC 75 : box_construct(result, &high, &low);
8288 tgl 4275 ECB :
8288 tgl 4276 GIC 75 : PG_RETURN_BOX_P(result);
8288 tgl 4277 ECB : }
9483 scrappy 4278 :
4279 : Datum
8288 tgl 4280 CBC 30 : box_div(PG_FUNCTION_ARGS)
4281 : {
8288 tgl 4282 GIC 30 : BOX *box = PG_GETARG_BOX_P(0);
4283 30 : Point *p = PG_GETARG_POINT_P(1);
9344 bruce 4284 ECB : BOX *result;
4285 : Point high,
1715 tomas.vondra 4286 : low;
4287 :
1715 tomas.vondra 4288 GIC 30 : result = (BOX *) palloc(sizeof(BOX));
4289 :
1715 tomas.vondra 4290 CBC 30 : point_div_point(&high, &box->high, p);
1715 tomas.vondra 4291 GIC 30 : point_div_point(&low, &box->low, p);
9483 scrappy 4292 ECB :
1715 tomas.vondra 4293 CBC 30 : box_construct(result, &high, &low);
4294 :
8288 tgl 4295 30 : PG_RETURN_BOX_P(result);
4296 : }
4297 :
4298 : /*
2896 alvherre 4299 ECB : * Convert point to empty box
4300 : */
4301 : Datum
2896 alvherre 4302 CBC 183 : point_box(PG_FUNCTION_ARGS)
4303 : {
2896 alvherre 4304 GIC 183 : Point *pt = PG_GETARG_POINT_P(0);
4305 : BOX *box;
4306 :
2896 alvherre 4307 CBC 183 : box = (BOX *) palloc(sizeof(BOX));
4308 :
4309 183 : box->high.x = pt->x;
4310 183 : box->low.x = pt->x;
2896 alvherre 4311 GIC 183 : box->high.y = pt->y;
2896 alvherre 4312 CBC 183 : box->low.y = pt->y;
4313 :
4314 183 : PG_RETURN_BOX_P(box);
4315 : }
4316 :
4317 : /*
2896 alvherre 4318 ECB : * Smallest bounding box that includes both of the given boxes
4319 : */
4320 : Datum
2896 alvherre 4321 CBC 75 : boxes_bound_box(PG_FUNCTION_ARGS)
4322 : {
2896 alvherre 4323 GIC 75 : BOX *box1 = PG_GETARG_BOX_P(0),
4324 75 : *box2 = PG_GETARG_BOX_P(1),
4325 : *container;
2896 alvherre 4326 ECB :
2896 alvherre 4327 GIC 75 : container = (BOX *) palloc(sizeof(BOX));
2896 alvherre 4328 ECB :
1697 tomas.vondra 4329 CBC 75 : container->high.x = float8_max(box1->high.x, box2->high.x);
1697 tomas.vondra 4330 GIC 75 : container->low.x = float8_min(box1->low.x, box2->low.x);
1697 tomas.vondra 4331 CBC 75 : container->high.y = float8_max(box1->high.y, box2->high.y);
1697 tomas.vondra 4332 GIC 75 : container->low.y = float8_min(box1->low.y, box2->low.y);
2896 alvherre 4333 ECB :
2896 alvherre 4334 GIC 75 : PG_RETURN_BOX_P(container);
4335 : }
4336 :
4337 :
4338 : /***********************************************************************
4339 : **
9345 bruce 4340 ECB : ** Routines for 2D paths.
4341 : **
9483 scrappy 4342 : ***********************************************************************/
4343 :
4344 : /* path_add()
4345 : * Concatenate two paths (only if they are both open).
4346 : */
8289 tgl 4347 : Datum
8289 tgl 4348 CBC 243 : path_add(PG_FUNCTION_ARGS)
9483 scrappy 4349 ECB : {
8289 tgl 4350 CBC 243 : PATH *p1 = PG_GETARG_PATH_P(0);
8289 tgl 4351 GIC 243 : PATH *p2 = PG_GETARG_PATH_P(1);
9344 bruce 4352 ECB : PATH *result;
4353 : int size,
4354 : base_size;
4355 : int i;
4356 :
8289 tgl 4357 GIC 243 : if (p1->closed || p2->closed)
4358 195 : PG_RETURN_NULL();
9483 scrappy 4359 ECB :
7528 bruce 4360 GIC 48 : base_size = sizeof(p1->p[0]) * (p1->npts + p2->npts);
2118 tgl 4361 CBC 48 : size = offsetof(PATH, p) + base_size;
7528 bruce 4362 ECB :
4363 : /* Check for integer overflow */
7528 bruce 4364 GIC 48 : if (base_size / sizeof(p1->p[0]) != (p1->npts + p2->npts) ||
7528 bruce 4365 ECB : size <= base_size)
7196 tgl 4366 UIC 0 : ereport(ERROR,
7196 tgl 4367 ECB : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
4368 : errmsg("too many points requested")));
7528 bruce 4369 :
8289 tgl 4370 CBC 48 : result = (PATH *) palloc(size);
4371 :
5885 4372 48 : SET_VARSIZE(result, size);
9345 bruce 4373 GIC 48 : result->npts = (p1->npts + p2->npts);
4374 48 : result->closed = p1->closed;
4375 : /* prevent instability in unused pad bytes */
4365 tgl 4376 48 : result->dummy = 0;
4377 :
9345 bruce 4378 168 : for (i = 0; i < p1->npts; i++)
4379 : {
4380 120 : result->p[i].x = p1->p[i].x;
4381 120 : result->p[i].y = p1->p[i].y;
4382 : }
4383 168 : for (i = 0; i < p2->npts; i++)
4384 : {
4385 120 : result->p[i + p1->npts].x = p2->p[i].x;
9345 bruce 4386 CBC 120 : result->p[i + p1->npts].y = p2->p[i].y;
4387 : }
9483 scrappy 4388 ECB :
8289 tgl 4389 CBC 48 : PG_RETURN_PATH_P(result);
4390 : }
4391 :
4392 : /* path_add_pt()
4393 : * Translation operators.
4394 : */
8289 tgl 4395 ECB : Datum
8289 tgl 4396 CBC 270 : path_add_pt(PG_FUNCTION_ARGS)
4397 : {
4398 270 : PATH *path = PG_GETARG_PATH_P_COPY(0);
4399 270 : Point *point = PG_GETARG_POINT_P(1);
4400 : int i;
4401 :
9345 bruce 4402 840 : for (i = 0; i < path->npts; i++)
1715 tomas.vondra 4403 GIC 570 : point_add_point(&path->p[i], &path->p[i], point);
9483 scrappy 4404 EUB :
8289 tgl 4405 GIC 270 : PG_RETURN_PATH_P(path);
4406 : }
4407 :
8289 tgl 4408 ECB : Datum
8289 tgl 4409 GIC 270 : path_sub_pt(PG_FUNCTION_ARGS)
9483 scrappy 4410 ECB : {
8289 tgl 4411 CBC 270 : PATH *path = PG_GETARG_PATH_P_COPY(0);
4412 270 : Point *point = PG_GETARG_POINT_P(1);
4413 : int i;
9483 scrappy 4414 ECB :
9345 bruce 4415 GIC 840 : for (i = 0; i < path->npts; i++)
1715 tomas.vondra 4416 CBC 570 : point_sub_point(&path->p[i], &path->p[i], point);
4417 :
8289 tgl 4418 270 : PG_RETURN_PATH_P(path);
8289 tgl 4419 ECB : }
4420 :
9483 scrappy 4421 : /* path_mul_pt()
4422 : * Rotation and scaling operators.
4423 : */
8289 tgl 4424 : Datum
8289 tgl 4425 GIC 270 : path_mul_pt(PG_FUNCTION_ARGS)
4426 : {
8289 tgl 4427 CBC 270 : PATH *path = PG_GETARG_PATH_P_COPY(0);
8289 tgl 4428 GIC 270 : Point *point = PG_GETARG_POINT_P(1);
4429 : int i;
4430 :
9345 bruce 4431 840 : for (i = 0; i < path->npts; i++)
1715 tomas.vondra 4432 570 : point_mul_point(&path->p[i], &path->p[i], point);
4433 :
8289 tgl 4434 CBC 270 : PG_RETURN_PATH_P(path);
4435 : }
9483 scrappy 4436 ECB :
8289 tgl 4437 : Datum
8289 tgl 4438 GIC 57 : path_div_pt(PG_FUNCTION_ARGS)
4439 : {
8289 tgl 4440 CBC 57 : PATH *path = PG_GETARG_PATH_P_COPY(0);
4441 57 : Point *point = PG_GETARG_POINT_P(1);
4442 : int i;
9483 scrappy 4443 ECB :
9345 bruce 4444 GIC 171 : for (i = 0; i < path->npts; i++)
1715 tomas.vondra 4445 117 : point_div_point(&path->p[i], &path->p[i], point);
4446 :
8289 tgl 4447 CBC 54 : PG_RETURN_PATH_P(path);
4448 : }
9483 scrappy 4449 ECB :
4450 :
4451 : Datum
8289 tgl 4452 GIC 45 : path_poly(PG_FUNCTION_ARGS)
9483 scrappy 4453 ECB : {
8289 tgl 4454 CBC 45 : PATH *path = PG_GETARG_PATH_P(0);
4455 : POLYGON *poly;
9344 bruce 4456 ECB : int size;
4457 : int i;
4458 :
4459 : /* This is not very consistent --- other similar cases return NULL ... */
9345 bruce 4460 GIC 45 : if (!path->closed)
7196 tgl 4461 3 : ereport(ERROR,
4462 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
7196 tgl 4463 ECB : errmsg("open path cannot be converted to polygon")));
4464 :
3338 noah 4465 : /*
4466 : * Never overflows: the old size fit in MaxAllocSize, and the new size is
4467 : * just a small constant larger.
4468 : */
2118 tgl 4469 CBC 42 : size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * path->npts;
8289 4470 42 : poly = (POLYGON *) palloc(size);
4471 :
5885 4472 42 : SET_VARSIZE(poly, size);
9345 bruce 4473 GIC 42 : poly->npts = path->npts;
4474 :
4475 126 : for (i = 0; i < path->npts; i++)
9345 bruce 4476 ECB : {
9345 bruce 4477 GIC 84 : poly->p[i].x = path->p[i].x;
9345 bruce 4478 CBC 84 : poly->p[i].y = path->p[i].y;
9345 bruce 4479 ECB : }
4480 :
9345 bruce 4481 GIC 42 : make_bound_box(poly);
9483 scrappy 4482 ECB :
8289 tgl 4483 CBC 42 : PG_RETURN_POLYGON_P(poly);
4484 : }
9441 lockhart 4485 ECB :
4486 :
4487 : /***********************************************************************
4488 : **
4489 : ** Routines for 2D polygons.
9483 scrappy 4490 : **
4491 : ***********************************************************************/
4492 :
4493 : Datum
8289 tgl 4494 GIC 63 : poly_npoints(PG_FUNCTION_ARGS)
4495 : {
8053 bruce 4496 63 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
4497 :
8289 tgl 4498 CBC 63 : PG_RETURN_INT32(poly->npts);
8289 tgl 4499 ECB : }
4500 :
4501 :
4502 : Datum
8289 tgl 4503 GIC 21 : poly_center(PG_FUNCTION_ARGS)
4504 : {
8053 bruce 4505 21 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
4506 : Point *result;
1715 tomas.vondra 4507 ECB : CIRCLE circle;
4508 :
1715 tomas.vondra 4509 GIC 21 : result = (Point *) palloc(sizeof(Point));
9385 lockhart 4510 ECB :
1715 tomas.vondra 4511 CBC 21 : poly_to_circle(&circle, poly);
1715 tomas.vondra 4512 GIC 21 : *result = circle.center;
9385 lockhart 4513 ECB :
1715 tomas.vondra 4514 GIC 21 : PG_RETURN_POINT_P(result);
8289 tgl 4515 ECB : }
9385 lockhart 4516 :
4517 :
4518 : Datum
8289 tgl 4519 CBC 21 : poly_box(PG_FUNCTION_ARGS)
4520 : {
8053 bruce 4521 21 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
4522 : BOX *box;
4523 :
1715 tomas.vondra 4524 GIC 21 : box = (BOX *) palloc(sizeof(BOX));
4525 21 : *box = poly->boundbox;
4526 :
8289 tgl 4527 21 : PG_RETURN_BOX_P(box);
4528 : }
4529 :
4530 :
4531 : /* box_poly()
9469 lockhart 4532 ECB : * Convert a box to a polygon.
4533 : */
8289 tgl 4534 : Datum
8289 tgl 4535 GIC 9315 : box_poly(PG_FUNCTION_ARGS)
9483 scrappy 4536 ECB : {
8289 tgl 4537 GIC 9315 : BOX *box = PG_GETARG_BOX_P(0);
4538 : POLYGON *poly;
4539 : int size;
4540 :
9345 bruce 4541 ECB : /* map four corners of the box to a polygon */
2118 tgl 4542 GIC 9315 : size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * 4;
8289 tgl 4543 CBC 9315 : poly = (POLYGON *) palloc(size);
4544 :
5885 tgl 4545 GIC 9315 : SET_VARSIZE(poly, size);
9345 bruce 4546 9315 : poly->npts = 4;
9483 scrappy 4547 ECB :
9345 bruce 4548 GIC 9315 : poly->p[0].x = box->low.x;
9345 bruce 4549 CBC 9315 : poly->p[0].y = box->low.y;
4550 9315 : poly->p[1].x = box->low.x;
9345 bruce 4551 GIC 9315 : poly->p[1].y = box->high.y;
9345 bruce 4552 CBC 9315 : poly->p[2].x = box->high.x;
9345 bruce 4553 GIC 9315 : poly->p[2].y = box->high.y;
4554 9315 : poly->p[3].x = box->high.x;
4555 9315 : poly->p[3].y = box->low.y;
4556 :
1715 tomas.vondra 4557 CBC 9315 : box_construct(&poly->boundbox, &box->high, &box->low);
4558 :
8289 tgl 4559 9315 : PG_RETURN_POLYGON_P(poly);
4560 : }
4561 :
9385 lockhart 4562 ECB :
8289 tgl 4563 : Datum
8289 tgl 4564 GIC 21 : poly_path(PG_FUNCTION_ARGS)
9483 scrappy 4565 ECB : {
8053 bruce 4566 GIC 21 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
4567 : PATH *path;
4568 : int size;
4569 : int i;
4570 :
4571 : /*
4572 : * Never overflows: the old size fit in MaxAllocSize, and the new size is
3338 noah 4573 ECB : * smaller by a small constant.
4574 : */
2118 tgl 4575 CBC 21 : size = offsetof(PATH, p) + sizeof(path->p[0]) * poly->npts;
8289 tgl 4576 GIC 21 : path = (PATH *) palloc(size);
4577 :
5885 4578 21 : SET_VARSIZE(path, size);
9345 bruce 4579 21 : path->npts = poly->npts;
2062 peter_e 4580 CBC 21 : path->closed = true;
4365 tgl 4581 ECB : /* prevent instability in unused pad bytes */
4365 tgl 4582 GIC 21 : path->dummy = 0;
9483 scrappy 4583 ECB :
9345 bruce 4584 CBC 84 : for (i = 0; i < poly->npts; i++)
4585 : {
4586 63 : path->p[i].x = poly->p[i].x;
4587 63 : path->p[i].y = poly->p[i].y;
9345 bruce 4588 ECB : }
9483 scrappy 4589 :
8289 tgl 4590 CBC 21 : PG_RETURN_PATH_P(path);
8289 tgl 4591 ECB : }
9441 lockhart 4592 :
4593 :
4594 : /***********************************************************************
9483 scrappy 4595 : **
4596 : ** Routines for circles.
4597 : **
4598 : ***********************************************************************/
4599 :
4600 : /*----------------------------------------------------------
4601 : * Formatting and conversion routines.
4602 : *---------------------------------------------------------*/
4603 :
9345 bruce 4604 : /* circle_in - convert a string to internal form.
4605 : *
4606 : * External format: (center and radius of circle)
4607 : * "<(f8,f8),f8>"
4608 : * also supports quick entry style "f8,f8,f8"
4609 : */
4610 : Datum
8288 tgl 4611 GIC 201 : circle_in(PG_FUNCTION_ARGS)
4612 : {
8288 tgl 4613 CBC 201 : char *str = PG_GETARG_CSTRING(0);
116 tgl 4614 GNC 201 : Node *escontext = fcinfo->context;
2566 tgl 4615 CBC 201 : CIRCLE *circle = (CIRCLE *) palloc(sizeof(CIRCLE));
4616 : char *s,
9344 bruce 4617 ECB : *cp;
9344 bruce 4618 CBC 201 : int depth = 0;
9345 bruce 4619 ECB :
9345 bruce 4620 GIC 201 : s = str;
8162 tgl 4621 CBC 213 : while (isspace((unsigned char) *s))
9345 bruce 4622 GIC 12 : s++;
1097 tgl 4623 CBC 201 : if (*s == LDELIM_C)
1097 tgl 4624 GIC 162 : depth++, s++;
1097 tgl 4625 CBC 39 : else if (*s == LDELIM)
9345 bruce 4626 ECB : {
4627 : /* If there are two left parens, consume the first one */
9345 bruce 4628 GIC 27 : cp = (s + 1);
8162 tgl 4629 CBC 33 : while (isspace((unsigned char) *cp))
9345 bruce 4630 GIC 6 : cp++;
4631 27 : if (*cp == LDELIM)
1097 tgl 4632 12 : depth++, s = cp;
4633 : }
4634 :
4635 : /* pair_decode will consume parens around the pair, if any */
116 tgl 4636 GNC 201 : if (!pair_decode(s, &circle->center.x, &circle->center.y, &s, "circle", str,
4637 : escontext))
4638 6 : PG_RETURN_NULL();
4639 :
9345 bruce 4640 GIC 189 : if (*s == DELIM)
4641 189 : s++;
4642 :
116 tgl 4643 GNC 189 : if (!single_decode(s, &circle->radius, &s, "circle", str, escontext))
116 tgl 4644 UNC 0 : PG_RETURN_NULL();
4645 :
4646 : /* We have to accept NaN. */
1697 tomas.vondra 4647 GIC 189 : if (circle->radius < 0.0)
116 tgl 4648 GNC 9 : ereturn(escontext, (Datum) 0,
4649 : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
4650 : errmsg("invalid input syntax for type %s: \"%s\"",
4651 : "circle", str)));
4652 :
9345 bruce 4653 GIC 348 : while (depth > 0)
9345 bruce 4654 ECB : {
1715 tomas.vondra 4655 GIC 171 : if ((*s == RDELIM) || ((*s == RDELIM_C) && (depth == 1)))
9345 bruce 4656 ECB : {
9345 bruce 4657 CBC 168 : depth--;
4658 168 : s++;
8162 tgl 4659 GIC 177 : while (isspace((unsigned char) *s))
9345 bruce 4660 9 : s++;
9345 bruce 4661 ECB : }
4662 : else
116 tgl 4663 GNC 3 : ereturn(escontext, (Datum) 0,
7196 tgl 4664 ECB : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2566 4665 : errmsg("invalid input syntax for type %s: \"%s\"",
4666 : "circle", str)));
9347 bruce 4667 : }
9483 scrappy 4668 :
9345 bruce 4669 GIC 177 : if (*s != '\0')
116 tgl 4670 GNC 3 : ereturn(escontext, (Datum) 0,
7196 tgl 4671 ECB : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2566 4672 : errmsg("invalid input syntax for type %s: \"%s\"",
4673 : "circle", str)));
9483 scrappy 4674 :
8288 tgl 4675 CBC 174 : PG_RETURN_CIRCLE_P(circle);
4676 : }
4677 :
4678 : /* circle_out - convert a circle to external form.
9483 scrappy 4679 ECB : */
4680 : Datum
8288 tgl 4681 CBC 4588 : circle_out(PG_FUNCTION_ARGS)
4682 : {
4683 4588 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
2566 tgl 4684 ECB : StringInfoData str;
4685 :
2566 tgl 4686 CBC 4588 : initStringInfo(&str);
9483 scrappy 4687 EUB :
2566 tgl 4688 GIC 4588 : appendStringInfoChar(&str, LDELIM_C);
4689 4588 : appendStringInfoChar(&str, LDELIM);
2566 tgl 4690 CBC 4588 : pair_encode(circle->center.x, circle->center.y, &str);
4691 4588 : appendStringInfoChar(&str, RDELIM);
2566 tgl 4692 GIC 4588 : appendStringInfoChar(&str, DELIM);
4693 4588 : single_encode(circle->radius, &str);
4694 4588 : appendStringInfoChar(&str, RDELIM_C);
4695 :
2566 tgl 4696 CBC 4588 : PG_RETURN_CSTRING(str.data);
4697 : }
9483 scrappy 4698 ECB :
4699 : /*
7271 tgl 4700 : * circle_recv - converts external binary format to circle
4701 : */
4702 : Datum
7271 tgl 4703 LBC 0 : circle_recv(PG_FUNCTION_ARGS)
4704 : {
7271 tgl 4705 UIC 0 : StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
7271 tgl 4706 ECB : CIRCLE *circle;
4707 :
7271 tgl 4708 UIC 0 : circle = (CIRCLE *) palloc(sizeof(CIRCLE));
4709 :
4710 0 : circle->center.x = pq_getmsgfloat8(buf);
4711 0 : circle->center.y = pq_getmsgfloat8(buf);
7271 tgl 4712 LBC 0 : circle->radius = pq_getmsgfloat8(buf);
7271 tgl 4713 ECB :
4714 : /* We have to accept NaN. */
1697 tomas.vondra 4715 UIC 0 : if (circle->radius < 0.0)
7196 tgl 4716 0 : ereport(ERROR,
4717 : (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
7132 peter_e 4718 ECB : errmsg("invalid radius in external \"circle\" value")));
4719 :
7271 tgl 4720 UIC 0 : PG_RETURN_CIRCLE_P(circle);
4721 : }
4722 :
4723 : /*
7271 tgl 4724 ECB : * circle_send - converts circle to binary format
4725 : */
4726 : Datum
7271 tgl 4727 UIC 0 : circle_send(PG_FUNCTION_ARGS)
4728 : {
7271 tgl 4729 LBC 0 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
4730 : StringInfoData buf;
7271 tgl 4731 ECB :
7271 tgl 4732 LBC 0 : pq_begintypsend(&buf);
4733 0 : pq_sendfloat8(&buf, circle->center.x);
4734 0 : pq_sendfloat8(&buf, circle->center.y);
4735 0 : pq_sendfloat8(&buf, circle->radius);
4736 0 : PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
7271 tgl 4737 ECB : }
4738 :
9483 scrappy 4739 :
4740 : /*----------------------------------------------------------
4741 : * Relational operators for CIRCLEs.
4742 : * <, >, <=, >=, and == are based on circle area.
4743 : *---------------------------------------------------------*/
4744 :
4745 : /* circles identical?
1697 tomas.vondra 4746 EUB : *
4747 : * We consider NaNs values to be equal to each other to let those circles
4748 : * to be found.
4749 : */
4750 : Datum
8288 tgl 4751 GBC 193 : circle_same(PG_FUNCTION_ARGS)
4752 : {
4753 193 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4754 193 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
8288 tgl 4755 EUB :
209 dgustafsson 4756 GIC 193 : PG_RETURN_BOOL(((isnan(circle1->radius) && isnan(circle2->radius)) ||
4757 : FPeq(circle1->radius, circle2->radius)) &&
1715 tomas.vondra 4758 EUB : point_eq_point(&circle1->center, &circle2->center));
8288 tgl 4759 : }
4760 :
4761 : /* circle_overlap - does circle1 overlap circle2?
4762 : */
4763 : Datum
8288 tgl 4764 GIC 9609 : circle_overlap(PG_FUNCTION_ARGS)
4765 : {
4766 9609 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4767 9609 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4768 :
4769 9609 : PG_RETURN_BOOL(FPle(point_dt(&circle1->center, &circle2->center),
1697 tomas.vondra 4770 EUB : float8_pl(circle1->radius, circle2->radius)));
4771 : }
9483 scrappy 4772 :
4773 : /* circle_overleft - is the right edge of circle1 at or left of
4774 : * the right edge of circle2?
4775 : */
8288 tgl 4776 : Datum
8288 tgl 4777 GBC 192 : circle_overleft(PG_FUNCTION_ARGS)
9483 scrappy 4778 EUB : {
8288 tgl 4779 GBC 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 4780 GIC 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4781 :
1697 tomas.vondra 4782 192 : PG_RETURN_BOOL(FPle(float8_pl(circle1->center.x, circle1->radius),
4783 : float8_pl(circle2->center.x, circle2->radius)));
4784 : }
4785 :
4786 : /* circle_left - is circle1 strictly left of circle2?
4787 : */
4788 : Datum
8288 tgl 4789 192 : circle_left(PG_FUNCTION_ARGS)
4790 : {
4791 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4792 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4793 :
1697 tomas.vondra 4794 CBC 192 : PG_RETURN_BOOL(FPlt(float8_pl(circle1->center.x, circle1->radius),
4795 : float8_mi(circle2->center.x, circle2->radius)));
9483 scrappy 4796 ECB : }
4797 :
4798 : /* circle_right - is circle1 strictly right of circle2?
4799 : */
4800 : Datum
8288 tgl 4801 GIC 192 : circle_right(PG_FUNCTION_ARGS)
4802 : {
4803 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4804 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4805 :
1697 tomas.vondra 4806 192 : PG_RETURN_BOOL(FPgt(float8_mi(circle1->center.x, circle1->radius),
1697 tomas.vondra 4807 ECB : float8_pl(circle2->center.x, circle2->radius)));
4808 : }
9483 scrappy 4809 :
6498 tgl 4810 : /* circle_overright - is the left edge of circle1 at or right of
4811 : * the left edge of circle2?
9483 scrappy 4812 : */
4813 : Datum
8288 tgl 4814 GIC 192 : circle_overright(PG_FUNCTION_ARGS)
4815 : {
4816 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4817 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4818 :
1697 tomas.vondra 4819 192 : PG_RETURN_BOOL(FPge(float8_mi(circle1->center.x, circle1->radius),
1697 tomas.vondra 4820 ECB : float8_mi(circle2->center.x, circle2->radius)));
4821 : }
9483 scrappy 4822 :
9345 bruce 4823 : /* circle_contained - is circle1 contained by circle2?
4824 : */
8288 tgl 4825 : Datum
8288 tgl 4826 GIC 192 : circle_contained(PG_FUNCTION_ARGS)
4827 : {
4828 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4829 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4830 :
1715 tomas.vondra 4831 192 : PG_RETURN_BOOL(FPle(point_dt(&circle1->center, &circle2->center),
1697 tomas.vondra 4832 ECB : float8_mi(circle2->radius, circle1->radius)));
4833 : }
9483 scrappy 4834 :
9345 bruce 4835 : /* circle_contain - does circle1 contain circle2?
4836 : */
8288 tgl 4837 : Datum
8288 tgl 4838 GIC 198 : circle_contain(PG_FUNCTION_ARGS)
4839 : {
4840 198 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4841 198 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4842 :
1715 tomas.vondra 4843 198 : PG_RETURN_BOOL(FPle(point_dt(&circle1->center, &circle2->center),
1697 tomas.vondra 4844 ECB : float8_mi(circle1->radius, circle2->radius)));
4845 : }
9483 scrappy 4846 :
4847 :
4848 : /* circle_below - is circle1 strictly below circle2?
4849 : */
4850 : Datum
8288 tgl 4851 GIC 192 : circle_below(PG_FUNCTION_ARGS)
4852 : {
4853 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4854 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4855 :
1697 tomas.vondra 4856 192 : PG_RETURN_BOOL(FPlt(float8_pl(circle1->center.y, circle1->radius),
1697 tomas.vondra 4857 ECB : float8_mi(circle2->center.y, circle2->radius)));
4858 : }
9483 scrappy 4859 :
6491 tgl 4860 : /* circle_above - is circle1 strictly above circle2?
4861 : */
8288 4862 : Datum
8288 tgl 4863 GIC 192 : circle_above(PG_FUNCTION_ARGS)
4864 : {
4865 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4866 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4867 :
1697 tomas.vondra 4868 192 : PG_RETURN_BOOL(FPgt(float8_mi(circle1->center.y, circle1->radius),
1697 tomas.vondra 4869 ECB : float8_pl(circle2->center.y, circle2->radius)));
4870 : }
6491 tgl 4871 :
4872 : /* circle_overbelow - is the upper edge of circle1 at or below
4873 : * the upper edge of circle2?
4874 : */
4875 : Datum
6491 tgl 4876 GIC 192 : circle_overbelow(PG_FUNCTION_ARGS)
4877 : {
4878 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4879 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4880 :
1697 tomas.vondra 4881 CBC 192 : PG_RETURN_BOOL(FPle(float8_pl(circle1->center.y, circle1->radius),
4882 : float8_pl(circle2->center.y, circle2->radius)));
6491 tgl 4883 ECB : }
4884 :
4885 : /* circle_overabove - is the lower edge of circle1 at or above
4886 : * the lower edge of circle2?
4887 : */
4888 : Datum
6491 tgl 4889 GIC 192 : circle_overabove(PG_FUNCTION_ARGS)
4890 : {
4891 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4892 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4893 :
1697 tomas.vondra 4894 CBC 192 : PG_RETURN_BOOL(FPge(float8_mi(circle1->center.y, circle1->radius),
4895 : float8_mi(circle2->center.y, circle2->radius)));
9483 scrappy 4896 ECB : }
4897 :
4898 :
9345 bruce 4899 : /* circle_relop - is area(circle1) relop area(circle2), within
4900 : * our accuracy constraint?
4901 : */
4902 : Datum
8288 tgl 4903 GIC 192 : circle_eq(PG_FUNCTION_ARGS)
4904 : {
4905 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 4906 CBC 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4907 :
4908 192 : PG_RETURN_BOOL(FPeq(circle_ar(circle1), circle_ar(circle2)));
8288 tgl 4909 ECB : }
4910 :
4911 : Datum
8288 tgl 4912 GIC 192 : circle_ne(PG_FUNCTION_ARGS)
4913 : {
4914 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4915 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4916 :
4917 192 : PG_RETURN_BOOL(FPne(circle_ar(circle1), circle_ar(circle2)));
4918 : }
9483 scrappy 4919 ECB :
4920 : Datum
8288 tgl 4921 CBC 789 : circle_lt(PG_FUNCTION_ARGS)
9483 scrappy 4922 ECB : {
8288 tgl 4923 GIC 789 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 4924 CBC 789 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4925 :
8288 tgl 4926 GIC 789 : PG_RETURN_BOOL(FPlt(circle_ar(circle1), circle_ar(circle2)));
4927 : }
4928 :
4929 : Datum
4930 192 : circle_gt(PG_FUNCTION_ARGS)
4931 : {
8288 tgl 4932 CBC 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 4933 GIC 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
8288 tgl 4934 ECB :
8288 tgl 4935 CBC 192 : PG_RETURN_BOOL(FPgt(circle_ar(circle1), circle_ar(circle2)));
4936 : }
9483 scrappy 4937 ECB :
4938 : Datum
8288 tgl 4939 GIC 192 : circle_le(PG_FUNCTION_ARGS)
4940 : {
4941 192 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4942 192 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4943 :
4944 192 : PG_RETURN_BOOL(FPle(circle_ar(circle1), circle_ar(circle2)));
4945 : }
8288 tgl 4946 ECB :
4947 : Datum
8288 tgl 4948 CBC 243 : circle_ge(PG_FUNCTION_ARGS)
9483 scrappy 4949 ECB : {
8288 tgl 4950 GIC 243 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 4951 CBC 243 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4952 :
8288 tgl 4953 GIC 243 : PG_RETURN_BOOL(FPge(circle_ar(circle1), circle_ar(circle2)));
4954 : }
9483 scrappy 4955 ECB :
4956 :
4957 : /*----------------------------------------------------------
9345 bruce 4958 : * "Arithmetic" operators on circles.
4959 : *---------------------------------------------------------*/
9483 scrappy 4960 :
4961 : /* circle_add_pt()
4962 : * Translation operator.
4963 : */
8288 tgl 4964 : Datum
8288 tgl 4965 GIC 240 : circle_add_pt(PG_FUNCTION_ARGS)
9483 scrappy 4966 ECB : {
8288 tgl 4967 CBC 240 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
8288 tgl 4968 GIC 240 : Point *point = PG_GETARG_POINT_P(1);
9344 bruce 4969 ECB : CIRCLE *result;
4970 :
1715 tomas.vondra 4971 GIC 240 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
4972 :
1715 tomas.vondra 4973 CBC 240 : point_add_point(&result->center, &circle->center, point);
1715 tomas.vondra 4974 GIC 240 : result->radius = circle->radius;
9483 scrappy 4975 ECB :
8288 tgl 4976 CBC 240 : PG_RETURN_CIRCLE_P(result);
4977 : }
9483 scrappy 4978 ECB :
4979 : Datum
8288 tgl 4980 GIC 240 : circle_sub_pt(PG_FUNCTION_ARGS)
4981 : {
8288 tgl 4982 CBC 240 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
8288 tgl 4983 GIC 240 : Point *point = PG_GETARG_POINT_P(1);
9344 bruce 4984 ECB : CIRCLE *result;
9483 scrappy 4985 :
1715 tomas.vondra 4986 GIC 240 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
9483 scrappy 4987 ECB :
1715 tomas.vondra 4988 GIC 240 : point_sub_point(&result->center, &circle->center, point);
4989 240 : result->radius = circle->radius;
4990 :
8288 tgl 4991 CBC 240 : PG_RETURN_CIRCLE_P(result);
4992 : }
9483 scrappy 4993 ECB :
4994 :
4995 : /* circle_mul_pt()
4996 : * Rotation and scaling operators.
4997 : */
4998 : Datum
8288 tgl 4999 GIC 240 : circle_mul_pt(PG_FUNCTION_ARGS)
5000 : {
5001 240 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5002 240 : Point *point = PG_GETARG_POINT_P(1);
5003 : CIRCLE *result;
5004 :
1715 tomas.vondra 5005 240 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
5006 :
5007 240 : point_mul_point(&result->center, &circle->center, point);
1697 tomas.vondra 5008 CBC 240 : result->radius = float8_mul(circle->radius, HYPOT(point->x, point->y));
5009 :
8288 tgl 5010 240 : PG_RETURN_CIRCLE_P(result);
8288 tgl 5011 ECB : }
5012 :
5013 : Datum
8288 tgl 5014 CBC 54 : circle_div_pt(PG_FUNCTION_ARGS)
5015 : {
5016 54 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5017 54 : Point *point = PG_GETARG_POINT_P(1);
5018 : CIRCLE *result;
9483 scrappy 5019 ECB :
1715 tomas.vondra 5020 GIC 54 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
5021 :
5022 54 : point_div_point(&result->center, &circle->center, point);
1697 tomas.vondra 5023 CBC 48 : result->radius = float8_div(circle->radius, HYPOT(point->x, point->y));
5024 :
8288 tgl 5025 48 : PG_RETURN_CIRCLE_P(result);
8288 tgl 5026 ECB : }
5027 :
5028 :
9345 bruce 5029 : /* circle_area - returns the area of the circle.
5030 : */
8288 tgl 5031 : Datum
8288 tgl 5032 CBC 255 : circle_area(PG_FUNCTION_ARGS)
5033 : {
5034 255 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5035 :
8288 tgl 5036 GIC 255 : PG_RETURN_FLOAT8(circle_ar(circle));
5037 : }
5038 :
5039 :
5040 : /* circle_diameter - returns the diameter of the circle.
5041 : */
8288 tgl 5042 ECB : Datum
8288 tgl 5043 GIC 48 : circle_diameter(PG_FUNCTION_ARGS)
9483 scrappy 5044 ECB : {
8288 tgl 5045 CBC 48 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5046 :
1697 tomas.vondra 5047 GIC 48 : PG_RETURN_FLOAT8(float8_mul(circle->radius, 2.0));
9483 scrappy 5048 ECB : }
5049 :
5050 :
9345 bruce 5051 : /* circle_radius - returns the radius of the circle.
5052 : */
8288 tgl 5053 : Datum
8288 tgl 5054 GIC 9378 : circle_radius(PG_FUNCTION_ARGS)
5055 : {
5056 9378 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
9483 scrappy 5057 ECB :
8288 tgl 5058 GIC 9378 : PG_RETURN_FLOAT8(circle->radius);
9483 scrappy 5059 ECB : }
5060 :
5061 :
5062 : /* circle_distance - returns the distance between
9345 bruce 5063 : * two circles.
5064 : */
8288 tgl 5065 : Datum
8288 tgl 5066 CBC 84 : circle_distance(PG_FUNCTION_ARGS)
5067 : {
5068 84 : CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
8288 tgl 5069 GIC 84 : CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
5070 : float8 result;
5071 :
1697 tomas.vondra 5072 84 : result = float8_mi(point_dt(&circle1->center, &circle2->center),
5073 : float8_pl(circle1->radius, circle2->radius));
5074 84 : if (result < 0.0)
1697 tomas.vondra 5075 CBC 36 : result = 0.0;
5076 :
8288 tgl 5077 84 : PG_RETURN_FLOAT8(result);
5078 : }
9480 scrappy 5079 ECB :
5080 :
5081 : Datum
8288 tgl 5082 GIC 12 : circle_contain_pt(PG_FUNCTION_ARGS)
5083 : {
5084 12 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5085 12 : Point *point = PG_GETARG_POINT_P(1);
1697 tomas.vondra 5086 ECB : float8 d;
5087 :
8288 tgl 5088 CBC 12 : d = point_dt(&circle->center, point);
8288 tgl 5089 GIC 12 : PG_RETURN_BOOL(d <= circle->radius);
8288 tgl 5090 ECB : }
5091 :
5092 :
5093 : Datum
8288 tgl 5094 GIC 30 : pt_contained_circle(PG_FUNCTION_ARGS)
5095 : {
5096 30 : Point *point = PG_GETARG_POINT_P(0);
8288 tgl 5097 CBC 30 : CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
5098 : float8 d;
8288 tgl 5099 ECB :
8288 tgl 5100 GIC 30 : d = point_dt(&circle->center, point);
8288 tgl 5101 CBC 30 : PG_RETURN_BOOL(d <= circle->radius);
5102 : }
5103 :
5104 :
5105 : /* dist_pc - returns the distance between
5106 : * a point and a circle.
5107 : */
5108 : Datum
5109 423 : dist_pc(PG_FUNCTION_ARGS)
5110 : {
5111 423 : Point *point = PG_GETARG_POINT_P(0);
5112 423 : CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
5113 : float8 result;
5114 :
1697 tomas.vondra 5115 423 : result = float8_mi(point_dt(point, &circle->center),
5116 : circle->radius);
5117 423 : if (result < 0.0)
5118 57 : result = 0.0;
5119 :
8288 tgl 5120 423 : PG_RETURN_FLOAT8(result);
5121 : }
5122 :
5123 : /*
5124 : * Distance from a circle to a point
2886 heikki.linnakangas 5125 ECB : */
5126 : Datum
2886 heikki.linnakangas 5127 CBC 9363 : dist_cpoint(PG_FUNCTION_ARGS)
2886 heikki.linnakangas 5128 ECB : {
2886 heikki.linnakangas 5129 GIC 9363 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5130 9363 : Point *point = PG_GETARG_POINT_P(1);
2886 heikki.linnakangas 5131 ECB : float8 result;
5132 :
1697 tomas.vondra 5133 GIC 9363 : result = float8_mi(point_dt(point, &circle->center), circle->radius);
5134 9363 : if (result < 0.0)
1697 tomas.vondra 5135 UIC 0 : result = 0.0;
5136 :
2886 heikki.linnakangas 5137 CBC 9363 : PG_RETURN_FLOAT8(result);
5138 : }
9483 scrappy 5139 ECB :
9345 bruce 5140 : /* circle_center - returns the center point of the circle.
5141 : */
5142 : Datum
8288 tgl 5143 CBC 9453 : circle_center(PG_FUNCTION_ARGS)
9483 scrappy 5144 ECB : {
8288 tgl 5145 GIC 9453 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5146 : Point *result;
5147 :
5148 9453 : result = (Point *) palloc(sizeof(Point));
9345 bruce 5149 9453 : result->x = circle->center.x;
5150 9453 : result->y = circle->center.y;
5151 :
8288 tgl 5152 CBC 9453 : PG_RETURN_POINT_P(result);
5153 : }
9483 scrappy 5154 ECB :
5155 :
5156 : /* circle_ar - returns the area of the circle.
5157 : */
1697 tomas.vondra 5158 : static float8
9344 bruce 5159 GIC 3855 : circle_ar(CIRCLE *circle)
9483 scrappy 5160 ECB : {
1697 tomas.vondra 5161 CBC 3855 : return float8_mul(float8_mul(circle->radius, circle->radius), M_PI);
5162 : }
9483 scrappy 5163 ECB :
5164 :
5165 : /*----------------------------------------------------------
5166 : * Conversion operators.
5167 : *---------------------------------------------------------*/
5168 :
5169 : Datum
8288 tgl 5170 CBC 90079 : cr_circle(PG_FUNCTION_ARGS)
5171 : {
5172 90079 : Point *center = PG_GETARG_POINT_P(0);
5173 90079 : float8 radius = PG_GETARG_FLOAT8(1);
5174 : CIRCLE *result;
5175 :
5176 90079 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
9483 scrappy 5177 ECB :
9345 bruce 5178 GBC 90079 : result->center.x = center->x;
9345 bruce 5179 GIC 90079 : result->center.y = center->y;
8288 tgl 5180 CBC 90079 : result->radius = radius;
5181 :
8288 tgl 5182 GIC 90079 : PG_RETURN_CIRCLE_P(result);
5183 : }
5184 :
5185 : Datum
8288 tgl 5186 CBC 24 : circle_box(PG_FUNCTION_ARGS)
5187 : {
5188 24 : CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5189 : BOX *box;
5190 : float8 delta;
9385 lockhart 5191 ECB :
8288 tgl 5192 CBC 24 : box = (BOX *) palloc(sizeof(BOX));
9385 lockhart 5193 ECB :
1697 tomas.vondra 5194 GIC 24 : delta = float8_div(circle->radius, sqrt(2.0));
9385 lockhart 5195 ECB :
1697 tomas.vondra 5196 GIC 24 : box->high.x = float8_pl(circle->center.x, delta);
5197 24 : box->low.x = float8_mi(circle->center.x, delta);
5198 24 : box->high.y = float8_pl(circle->center.y, delta);
5199 24 : box->low.y = float8_mi(circle->center.y, delta);
5200 :
8288 tgl 5201 24 : PG_RETURN_BOX_P(box);
8288 tgl 5202 ECB : }
5203 :
9385 lockhart 5204 : /* box_circle()
5205 : * Convert a box to a circle.
5206 : */
5207 : Datum
8288 tgl 5208 GIC 9315 : box_circle(PG_FUNCTION_ARGS)
5209 : {
5210 9315 : BOX *box = PG_GETARG_BOX_P(0);
5211 : CIRCLE *circle;
5212 :
8288 tgl 5213 CBC 9315 : circle = (CIRCLE *) palloc(sizeof(CIRCLE));
5214 :
1697 tomas.vondra 5215 9315 : circle->center.x = float8_div(float8_pl(box->high.x, box->low.x), 2.0);
5216 9315 : circle->center.y = float8_div(float8_pl(box->high.y, box->low.y), 2.0);
5217 :
9345 bruce 5218 GIC 9315 : circle->radius = point_dt(&circle->center, &box->high);
9385 lockhart 5219 ECB :
8288 tgl 5220 GIC 9315 : PG_RETURN_CIRCLE_P(circle);
8288 tgl 5221 ECB : }
9385 lockhart 5222 :
5223 :
5224 : Datum
8335 tgl 5225 CBC 30043 : circle_poly(PG_FUNCTION_ARGS)
5226 : {
8335 tgl 5227 GIC 30043 : int32 npts = PG_GETARG_INT32(0);
5228 30043 : CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
9344 bruce 5229 ECB : POLYGON *poly;
5230 : int base_size,
7528 5231 : size;
5232 : int i;
5233 : float8 angle;
5234 : float8 anglestep;
9483 scrappy 5235 :
7196 tgl 5236 GIC 30043 : if (FPzero(circle->radius))
7196 tgl 5237 CBC 3 : ereport(ERROR,
5238 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2118 tgl 5239 ECB : errmsg("cannot convert circle with radius zero to polygon")));
7196 5240 :
7196 tgl 5241 CBC 30040 : if (npts < 2)
5242 3 : ereport(ERROR,
5243 : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
7196 tgl 5244 ECB : errmsg("must request at least 2 points")));
5245 :
7528 bruce 5246 GIC 30037 : base_size = sizeof(poly->p[0]) * npts;
2118 tgl 5247 30037 : size = offsetof(POLYGON, p) + base_size;
5248 :
5249 : /* Check for integer overflow */
7528 bruce 5250 30037 : if (base_size / npts != sizeof(poly->p[0]) || size <= base_size)
7196 tgl 5251 LBC 0 : ereport(ERROR,
5252 : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
7196 tgl 5253 ECB : errmsg("too many points requested")));
5254 :
7452 bruce 5255 GIC 30037 : poly = (POLYGON *) palloc0(size); /* zero any holes */
5885 tgl 5256 CBC 30037 : SET_VARSIZE(poly, size);
9345 bruce 5257 GIC 30037 : poly->npts = npts;
9483 scrappy 5258 ECB :
1697 tomas.vondra 5259 CBC 30037 : anglestep = float8_div(2.0 * M_PI, npts);
5260 :
9345 bruce 5261 390409 : for (i = 0; i < npts; i++)
5262 : {
1697 tomas.vondra 5263 360372 : angle = float8_mul(anglestep, i);
5264 :
1697 tomas.vondra 5265 GIC 360372 : poly->p[i].x = float8_mi(circle->center.x,
5266 : float8_mul(circle->radius, cos(angle)));
5267 360372 : poly->p[i].y = float8_pl(circle->center.y,
1697 tomas.vondra 5268 ECB : float8_mul(circle->radius, sin(angle)));
5269 : }
9483 scrappy 5270 :
9345 bruce 5271 CBC 30037 : make_bound_box(poly);
5272 :
8335 tgl 5273 GIC 30037 : PG_RETURN_POLYGON_P(poly);
5274 : }
5275 :
5276 : /*
5277 : * Convert polygon to circle
5278 : *
1715 tomas.vondra 5279 ECB : * The result must be preallocated.
9483 scrappy 5280 : *
5281 : * XXX This algorithm should use weighted means of line segments
5282 : * rather than straight average values of points - tgl 97/01/21.
5283 : */
1715 tomas.vondra 5284 : static void
1715 tomas.vondra 5285 CBC 36 : poly_to_circle(CIRCLE *result, POLYGON *poly)
5286 : {
5287 : int i;
5288 :
5289 36 : Assert(poly->npts > 0);
9483 scrappy 5290 ECB :
1715 tomas.vondra 5291 GIC 36 : result->center.x = 0;
5292 36 : result->center.y = 0;
1715 tomas.vondra 5293 CBC 36 : result->radius = 0;
9483 scrappy 5294 EUB :
9345 bruce 5295 GIC 162 : for (i = 0; i < poly->npts; i++)
1715 tomas.vondra 5296 126 : point_add_point(&result->center, &result->center, &poly->p[i]);
1697 5297 36 : result->center.x = float8_div(result->center.x, poly->npts);
1697 tomas.vondra 5298 CBC 36 : result->center.y = float8_div(result->center.y, poly->npts);
9483 scrappy 5299 ECB :
9345 bruce 5300 CBC 162 : for (i = 0; i < poly->npts; i++)
1697 tomas.vondra 5301 GIC 126 : result->radius = float8_pl(result->radius,
1697 tomas.vondra 5302 ECB : point_dt(&poly->p[i], &result->center));
1697 tomas.vondra 5303 GIC 36 : result->radius = float8_div(result->radius, poly->npts);
1715 tomas.vondra 5304 CBC 36 : }
5305 :
1715 tomas.vondra 5306 ECB : Datum
1715 tomas.vondra 5307 GIC 15 : poly_circle(PG_FUNCTION_ARGS)
1715 tomas.vondra 5308 ECB : {
1715 tomas.vondra 5309 GIC 15 : POLYGON *poly = PG_GETARG_POLYGON_P(0);
1715 tomas.vondra 5310 ECB : CIRCLE *result;
5311 :
1715 tomas.vondra 5312 GIC 15 : result = (CIRCLE *) palloc(sizeof(CIRCLE));
5313 :
1715 tomas.vondra 5314 CBC 15 : poly_to_circle(result, poly);
5315 :
5316 15 : PG_RETURN_CIRCLE_P(result);
5317 : }
5318 :
5319 :
5320 : /***********************************************************************
5321 : **
5322 : ** Private routines for multiple types.
5323 : **
5324 : ***********************************************************************/
5325 :
5326 : /*
5327 : * Test to see if the point is inside the polygon, returns 1/0, or 2 if
5879 bruce 5328 ECB : * the point is on the polygon.
5329 : * Code adapted but not copied from integer-based routines in WN: A
5330 : * Server for the HTTP
5331 : * version 1.15.1, file wn/image.c
6131 5332 : * http://hopf.math.northwestern.edu/index.html
5333 : * Description of algorithm: http://www.linuxjournal.com/article/2197
5879 5334 : * http://www.linuxjournal.com/article/2029
6131 5335 : */
5336 :
5337 : #define POINT_ON_POLYGON INT_MAX
9385 lockhart 5338 :
9364 bruce 5339 : static int
8986 bruce 5340 CBC 123325 : point_inside(Point *p, int npts, Point *plist)
9385 lockhart 5341 ECB : {
5342 : float8 x0,
9344 bruce 5343 : y0;
1697 tomas.vondra 5344 : float8 prev_x,
5345 : prev_y;
5879 bruce 5346 CBC 123325 : int i = 0;
1697 tomas.vondra 5347 ECB : float8 x,
5348 : y;
5349 : int cross,
5624 bruce 5350 CBC 123325 : total_cross = 0;
5351 :
1715 tomas.vondra 5352 123325 : Assert(npts > 0);
5353 :
5354 : /* compute first polygon point relative to single point */
1697 5355 123325 : x0 = float8_mi(plist[0].x, p->x);
1697 tomas.vondra 5356 GIC 123325 : y0 = float8_mi(plist[0].y, p->y);
9385 lockhart 5357 ECB :
5879 bruce 5358 GIC 123325 : prev_x = x0;
5879 bruce 5359 CBC 123325 : prev_y = y0;
5360 : /* loop over polygon points and aggregate total_cross */
9345 bruce 5361 GIC 568974 : for (i = 1; i < npts; i++)
5362 : {
5363 : /* compute next polygon point relative to single point */
1697 tomas.vondra 5364 445715 : x = float8_mi(plist[i].x, p->x);
5365 445715 : y = float8_mi(plist[i].y, p->y);
5366 :
5367 : /* compute previous to current point crossing */
5879 bruce 5368 445715 : if ((cross = lseg_crossing(x, y, prev_x, prev_y)) == POINT_ON_POLYGON)
9345 5369 66 : return 2;
5879 5370 445649 : total_cross += cross;
5371 :
5372 445649 : prev_x = x;
5373 445649 : prev_y = y;
5374 : }
5375 :
5376 : /* now do the first point */
5377 123259 : if ((cross = lseg_crossing(x0, y0, prev_x, prev_y)) == POINT_ON_POLYGON)
9345 5378 54 : return 2;
5879 5379 123205 : total_cross += cross;
5380 :
5381 123205 : if (total_cross != 0)
9345 5382 94597 : return 1;
9345 bruce 5383 CBC 28608 : return 0;
5384 : }
5385 :
5386 :
5387 : /* lseg_crossing()
5388 : * Returns +/-2 if line segment crosses the positive X-axis in a +/- direction.
5879 bruce 5389 ECB : * Returns +/-1 if one point is on the positive X-axis.
5390 : * Returns 0 if both points are on the positive X-axis, or there is no crossing.
5391 : * Returns POINT_ON_POLYGON if the segment contains (0,0).
5392 : * Wow, that is one confusing API, but it is used above, and when summed,
5393 : * can tell is if a point is in a polygon.
5394 : */
9385 lockhart 5395 :
5396 : static int
1697 tomas.vondra 5397 GIC 568974 : lseg_crossing(float8 x, float8 y, float8 prev_x, float8 prev_y)
9385 lockhart 5398 ECB : {
1697 tomas.vondra 5399 : float8 z;
5400 : int y_sign;
9385 lockhart 5401 :
9345 bruce 5402 CBC 568974 : if (FPzero(y))
5403 : { /* y == 0, on X axis */
5624 5404 872 : if (FPzero(x)) /* (x,y) is (0,0)? */
5879 bruce 5405 GIC 114 : return POINT_ON_POLYGON;
9345 5406 758 : else if (FPgt(x, 0))
5624 bruce 5407 ECB : { /* x > 0 */
5624 bruce 5408 CBC 505 : if (FPzero(prev_y)) /* y and prev_y are zero */
5409 : /* prev_x > 0? */
1697 tomas.vondra 5410 GIC 30 : return FPgt(prev_x, 0.0) ? 0 : POINT_ON_POLYGON;
1697 tomas.vondra 5411 CBC 475 : return FPlt(prev_y, 0.0) ? 1 : -1;
9345 bruce 5412 ECB : }
5413 : else
5414 : { /* x < 0, x not on positive X axis */
5879 bruce 5415 CBC 253 : if (FPzero(prev_y))
5879 bruce 5416 ECB : /* prev_x < 0? */
1697 tomas.vondra 5417 GIC 12 : return FPlt(prev_x, 0.0) ? 0 : POINT_ON_POLYGON;
8986 bruce 5418 241 : return 0;
5419 : }
9347 bruce 5420 ECB : }
9345 5421 : else
5624 5422 : { /* y != 0 */
5423 : /* compute y crossing direction from previous point */
1697 tomas.vondra 5424 CBC 568102 : y_sign = FPgt(y, 0.0) ? 1 : -1;
5879 bruce 5425 ECB :
5879 bruce 5426 CBC 568102 : if (FPzero(prev_y))
5427 : /* previous point was on X axis, so new point is either off or on */
1697 tomas.vondra 5428 GIC 764 : return FPlt(prev_x, 0.0) ? 0 : y_sign;
5429 567338 : else if ((y_sign < 0 && FPlt(prev_y, 0.0)) ||
5430 290029 : (y_sign > 0 && FPgt(prev_y, 0.0)))
5431 : /* both above or below X axis */
5624 bruce 5432 361250 : return 0; /* same sign */
5433 : else
5434 : { /* y and prev_y cross X-axis */
1697 tomas.vondra 5435 206088 : if (FPge(x, 0.0) && FPgt(prev_x, 0.0))
5436 : /* both non-negative so cross positive X-axis */
5879 bruce 5437 74943 : return 2 * y_sign;
1697 tomas.vondra 5438 131145 : if (FPlt(x, 0.0) && FPle(prev_x, 0.0))
5439 : /* both non-positive so do not cross positive X-axis */
5879 bruce 5440 CBC 66222 : return 0;
5441 :
5442 : /* x and y cross axes, see URL above point_inside() */
1697 tomas.vondra 5443 GIC 64923 : z = float8_mi(float8_mul(float8_mi(x, prev_x), y),
5444 : float8_mul(float8_mi(y, prev_y), x));
5879 bruce 5445 CBC 64923 : if (FPzero(z))
5879 bruce 5446 GIC 6 : return POINT_ON_POLYGON;
1697 tomas.vondra 5447 CBC 64917 : if ((y_sign < 0 && FPlt(z, 0.0)) ||
5448 37248 : (y_sign > 0 && FPgt(z, 0.0)))
5449 36342 : return 0;
1697 tomas.vondra 5450 GIC 28575 : return 2 * y_sign;
5879 bruce 5451 ECB : }
5452 : }
8288 tgl 5453 : }
9385 lockhart 5454 :
5455 :
5456 : static bool
8986 bruce 5457 GIC 3046 : plist_same(int npts, Point *p1, Point *p2)
9385 lockhart 5458 ECB : {
5459 : int i,
9344 bruce 5460 : ii,
5461 : j;
5462 :
5463 : /* find match for first point */
9345 bruce 5464 GIC 3130 : for (i = 0; i < npts; i++)
5465 : {
1715 tomas.vondra 5466 3112 : if (point_eq_point(&p2[i], &p1[0]))
9345 bruce 5467 ECB : {
5468 :
5469 : /* match found? then look forward through remaining points */
9345 bruce 5470 GIC 9092 : for (ii = 1, j = i + 1; ii < npts; ii++, j++)
9345 bruce 5471 ECB : {
9345 bruce 5472 CBC 6070 : if (j >= npts)
5473 9 : j = 0;
1715 tomas.vondra 5474 GIC 6070 : if (!point_eq_point(&p2[j], &p1[ii]))
9345 bruce 5475 CBC 18 : break;
5476 : }
9345 bruce 5477 GIC 3040 : if (ii == npts)
2062 peter_e 5478 CBC 3022 : return true;
5479 :
9345 bruce 5480 ECB : /* match not found forwards? then look backwards */
9345 bruce 5481 CBC 42 : for (ii = 1, j = i - 1; ii < npts; ii++, j--)
5482 : {
5483 36 : if (j < 0)
9345 bruce 5484 GIC 6 : j = (npts - 1);
1715 tomas.vondra 5485 36 : if (!point_eq_point(&p2[j], &p1[ii]))
9345 bruce 5486 CBC 12 : break;
5487 : }
5488 18 : if (ii == npts)
2062 peter_e 5489 6 : return true;
9345 bruce 5490 ECB : }
9347 5491 : }
9385 lockhart 5492 :
2062 peter_e 5493 CBC 18 : return false;
5494 : }
5495 :
5496 :
5497 : /*-------------------------------------------------------------------------
5498 : * Determine the hypotenuse.
5499 : *
4632 tgl 5500 ECB : * If required, x and y are swapped to make x the larger number. The
5501 : * traditional formula of x^2+y^2 is rearranged to factor x outside the
5502 : * sqrt. This allows computation of the hypotenuse for significantly
5503 : * larger values, and with a higher precision than when using the naive
5504 : * formula. In particular, this cannot overflow unless the final result
5505 : * would be out-of-range.
5506 : *
5507 : * sqrt( x^2 + y^2 ) = sqrt( x^2( 1 + y^2/x^2) )
5508 : * = x * sqrt( 1 + y^2/x^2 )
5509 : * = x * sqrt( 1 + y/x * y/x )
5510 : *
5511 : * It is expected that this routine will eventually be replaced with the
5512 : * C99 hypot() function.
5513 : *
5514 : * This implementation conforms to IEEE Std 1003.1 and GLIBC, in that the
5515 : * case of hypot(inf,nan) results in INF, and not NAN.
5516 : *-----------------------------------------------------------------------
5517 : */
1697 tomas.vondra 5518 : float8
1697 tomas.vondra 5519 GIC 7827054 : pg_hypot(float8 x, float8 y)
4632 tgl 5520 ECB : {
1697 tomas.vondra 5521 : float8 yx,
5522 : result;
5523 :
4632 tgl 5524 : /* Handle INF and NaN properly */
4632 tgl 5525 GIC 7827054 : if (isinf(x) || isinf(y))
4632 tgl 5526 CBC 3576 : return get_float8_infinity();
4632 tgl 5527 ECB :
4632 tgl 5528 CBC 7823478 : if (isnan(x) || isnan(y))
5529 10761 : return get_float8_nan();
5530 :
4632 tgl 5531 ECB : /* Else, drop any minus signs */
4632 tgl 5532 CBC 7812717 : x = fabs(x);
4632 tgl 5533 GIC 7812717 : y = fabs(y);
5534 :
5535 : /* Swap x and y if needed to make x the larger one */
4632 tgl 5536 CBC 7812717 : if (x < y)
5537 : {
1697 tomas.vondra 5538 GIC 3819882 : float8 temp = x;
5539 :
4632 tgl 5540 3819882 : x = y;
5541 3819882 : y = temp;
5542 : }
5543 :
5544 : /*
5545 : * If y is zero, the hypotenuse is x. This test saves a few cycles in
5546 : * such cases, but more importantly it also protects against
5547 : * divide-by-zero errors, since now x >= y.
5548 : */
5549 7812717 : if (y == 0.0)
5550 2000949 : return x;
5551 :
5552 : /* Determine the hypotenuse */
5553 5811768 : yx = y / x;
1697 tomas.vondra 5554 5811768 : result = x * sqrt(1.0 + (yx * yx));
5555 :
1151 tgl 5556 5811768 : if (unlikely(isinf(result)))
1151 tgl 5557 UIC 0 : float_overflow_error();
1151 tgl 5558 GIC 5811768 : if (unlikely(result == 0.0))
1151 tgl 5559 UIC 0 : float_underflow_error();
5560 :
1697 tomas.vondra 5561 GIC 5811768 : return result;
4632 tgl 5562 ECB : }
|
