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