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