PostgreSQL Source Code  git master
geo_ops.c
Go to the documentation of this file.
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 
74 {
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
194 single_decode(char *num, float8 *x, char **endptr_p,
195  const char *type_name, const char *orig_string,
196  Node *escontext)
197 {
198  *x = float8in_internal(num, endptr_p, type_name, orig_string, escontext);
199  return (!SOFT_ERROR_OCCURRED(escontext));
200 } /* single_decode() */
201 
202 static void
204 {
205  char *xstr = float8out_internal(x);
206 
208  pfree(xstr);
209 } /* single_encode() */
210 
211 static bool
212 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 
218  while (isspace((unsigned char) *str))
219  str++;
220  if ((has_delim = (*str == LDELIM)))
221  str++;
222 
223  if (!single_decode(str, x, &str, type_name, orig_string, escontext))
224  return false;
225 
226  if (*str++ != DELIM)
227  goto fail;
228 
229  if (!single_decode(str, y, &str, type_name, orig_string, escontext))
230  return false;
231 
232  if (has_delim)
233  {
234  if (*str++ != RDELIM)
235  goto fail;
236  while (isspace((unsigned char) *str))
237  str++;
238  }
239 
240  /* report stopping point if wanted, else complain if not end of string */
241  if (endptr_p)
242  *endptr_p = str;
243  else if (*str != '\0')
244  goto fail;
245  return true;
246 
247 fail:
248  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
256 {
257  char *xstr = float8out_internal(x);
258  char *ystr = float8out_internal(y);
259 
260  appendStringInfo(str, "%s,%s", xstr, ystr);
261  pfree(xstr);
262  pfree(ystr);
263 }
264 
265 static bool
266 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 {
271  int depth = 0;
272  char *cp;
273  int i;
274 
275  while (isspace((unsigned char) *str))
276  str++;
277  if ((*isopen = (*str == LDELIM_EP)))
278  {
279  /* no open delimiter allowed? */
280  if (!opentype)
281  goto fail;
282  depth++;
283  str++;
284  }
285  else if (*str == LDELIM)
286  {
287  cp = (str + 1);
288  while (isspace((unsigned char) *cp))
289  cp++;
290  if (*cp == LDELIM)
291  {
292  depth++;
293  str = cp;
294  }
295  else if (strrchr(str, LDELIM) == str)
296  {
297  depth++;
298  str = cp;
299  }
300  }
301 
302  for (i = 0; i < npts; i++)
303  {
304  if (!pair_decode(str, &(p->x), &(p->y), &str, type_name, orig_string,
305  escontext))
306  return false;
307  if (*str == DELIM)
308  str++;
309  p++;
310  }
311 
312  while (depth > 0)
313  {
314  if (*str == RDELIM || (*str == RDELIM_EP && *isopen && depth == 1))
315  {
316  depth--;
317  str++;
318  while (isspace((unsigned char) *str))
319  str++;
320  }
321  else
322  goto fail;
323  }
324 
325  /* report stopping point if wanted, else complain if not end of string */
326  if (endptr_p)
327  *endptr_p = str;
328  else if (*str != '\0')
329  goto fail;
330  return true;
331 
332 fail:
333  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 *
341 {
343  int i;
344 
346 
347  switch (path_delim)
348  {
349  case PATH_CLOSED:
351  break;
352  case PATH_OPEN:
354  break;
355  case PATH_NONE:
356  break;
357  }
358 
359  for (i = 0; i < npts; i++)
360  {
361  if (i > 0)
364  pair_encode(pt->x, pt->y, &str);
366  pt++;
367  }
368 
369  switch (path_delim)
370  {
371  case PATH_CLOSED:
373  break;
374  case PATH_OPEN:
376  break;
377  case PATH_NONE:
378  break;
379  }
380 
381  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
392 pair_count(char *s, char delim)
393 {
394  int ndelim = 0;
395 
396  while ((s = strchr(s, delim)) != NULL)
397  {
398  ndelim++;
399  s++;
400  }
401  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
423 {
424  char *str = PG_GETARG_CSTRING(0);
425  Node *escontext = fcinfo->context;
426  BOX *box = (BOX *) palloc(sizeof(BOX));
427  bool isopen;
428  float8 x,
429  y;
430 
431  if (!path_decode(str, false, 2, &(box->high), &isopen, NULL, "box", str,
432  escontext))
433  PG_RETURN_NULL();
434 
435  /* reorder corners if necessary... */
436  if (float8_lt(box->high.x, box->low.x))
437  {
438  x = box->high.x;
439  box->high.x = box->low.x;
440  box->low.x = x;
441  }
442  if (float8_lt(box->high.y, box->low.y))
443  {
444  y = box->high.y;
445  box->high.y = box->low.y;
446  box->low.y = y;
447  }
448 
449  PG_RETURN_BOX_P(box);
450 }
451 
452 /* box_out - convert a box to external form.
453  */
454 Datum
456 {
457  BOX *box = PG_GETARG_BOX_P(0);
458 
460 }
461 
462 /*
463  * box_recv - converts external binary format to box
464  */
465 Datum
467 {
469  BOX *box;
470  float8 x,
471  y;
472 
473  box = (BOX *) palloc(sizeof(BOX));
474 
475  box->high.x = pq_getmsgfloat8(buf);
476  box->high.y = pq_getmsgfloat8(buf);
477  box->low.x = pq_getmsgfloat8(buf);
478  box->low.y = pq_getmsgfloat8(buf);
479 
480  /* reorder corners if necessary... */
481  if (float8_lt(box->high.x, box->low.x))
482  {
483  x = box->high.x;
484  box->high.x = box->low.x;
485  box->low.x = x;
486  }
487  if (float8_lt(box->high.y, box->low.y))
488  {
489  y = box->high.y;
490  box->high.y = box->low.y;
491  box->low.y = y;
492  }
493 
494  PG_RETURN_BOX_P(box);
495 }
496 
497 /*
498  * box_send - converts box to binary format
499  */
500 Datum
502 {
503  BOX *box = PG_GETARG_BOX_P(0);
505 
507  pq_sendfloat8(&buf, box->high.x);
508  pq_sendfloat8(&buf, box->high.y);
509  pq_sendfloat8(&buf, box->low.x);
510  pq_sendfloat8(&buf, box->low.y);
512 }
513 
514 
515 /* box_construct - fill in a new box.
516  */
517 static inline void
518 box_construct(BOX *result, Point *pt1, Point *pt2)
519 {
520  if (float8_gt(pt1->x, pt2->x))
521  {
522  result->high.x = pt1->x;
523  result->low.x = pt2->x;
524  }
525  else
526  {
527  result->high.x = pt2->x;
528  result->low.x = pt1->x;
529  }
530  if (float8_gt(pt1->y, pt2->y))
531  {
532  result->high.y = pt1->y;
533  result->low.y = pt2->y;
534  }
535  else
536  {
537  result->high.y = pt2->y;
538  result->low.y = pt1->y;
539  }
540 }
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
552 {
553  BOX *box1 = PG_GETARG_BOX_P(0);
554  BOX *box2 = PG_GETARG_BOX_P(1);
555 
556  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
564 {
565  BOX *box1 = PG_GETARG_BOX_P(0);
566  BOX *box2 = PG_GETARG_BOX_P(1);
567 
568  PG_RETURN_BOOL(box_ov(box1, box2));
569 }
570 
571 static bool
572 box_ov(BOX *box1, BOX *box2)
573 {
574  return (FPle(box1->low.x, box2->high.x) &&
575  FPle(box2->low.x, box1->high.x) &&
576  FPle(box1->low.y, box2->high.y) &&
577  FPle(box2->low.y, box1->high.y));
578 }
579 
580 /* box_left - is box1 strictly left of box2?
581  */
582 Datum
584 {
585  BOX *box1 = PG_GETARG_BOX_P(0);
586  BOX *box2 = PG_GETARG_BOX_P(1);
587 
588  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
599 {
600  BOX *box1 = PG_GETARG_BOX_P(0);
601  BOX *box2 = PG_GETARG_BOX_P(1);
602 
603  PG_RETURN_BOOL(FPle(box1->high.x, box2->high.x));
604 }
605 
606 /* box_right - is box1 strictly right of box2?
607  */
608 Datum
610 {
611  BOX *box1 = PG_GETARG_BOX_P(0);
612  BOX *box2 = PG_GETARG_BOX_P(1);
613 
614  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
625 {
626  BOX *box1 = PG_GETARG_BOX_P(0);
627  BOX *box2 = PG_GETARG_BOX_P(1);
628 
629  PG_RETURN_BOOL(FPge(box1->low.x, box2->low.x));
630 }
631 
632 /* box_below - is box1 strictly below box2?
633  */
634 Datum
636 {
637  BOX *box1 = PG_GETARG_BOX_P(0);
638  BOX *box2 = PG_GETARG_BOX_P(1);
639 
640  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
648 {
649  BOX *box1 = PG_GETARG_BOX_P(0);
650  BOX *box2 = PG_GETARG_BOX_P(1);
651 
652  PG_RETURN_BOOL(FPle(box1->high.y, box2->high.y));
653 }
654 
655 /* box_above - is box1 strictly above box2?
656  */
657 Datum
659 {
660  BOX *box1 = PG_GETARG_BOX_P(0);
661  BOX *box2 = PG_GETARG_BOX_P(1);
662 
663  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
671 {
672  BOX *box1 = PG_GETARG_BOX_P(0);
673  BOX *box2 = PG_GETARG_BOX_P(1);
674 
675  PG_RETURN_BOOL(FPge(box1->low.y, box2->low.y));
676 }
677 
678 /* box_contained - is box1 contained by box2?
679  */
680 Datum
682 {
683  BOX *box1 = PG_GETARG_BOX_P(0);
684  BOX *box2 = PG_GETARG_BOX_P(1);
685 
686  PG_RETURN_BOOL(box_contain_box(box2, box1));
687 }
688 
689 /* box_contain - does box1 contain box2?
690  */
691 Datum
693 {
694  BOX *box1 = PG_GETARG_BOX_P(0);
695  BOX *box2 = PG_GETARG_BOX_P(1);
696 
697  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
704 box_contain_box(BOX *contains_box, BOX *contained_box)
705 {
706  return FPge(contains_box->high.x, contained_box->high.x) &&
707  FPle(contains_box->low.x, contained_box->low.x) &&
708  FPge(contains_box->high.y, contained_box->high.y) &&
709  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
723 {
724  BOX *box1 = PG_GETARG_BOX_P(0);
725  BOX *box2 = PG_GETARG_BOX_P(1);
726 
727  PG_RETURN_BOOL(FPle(box1->high.y, box2->low.y));
728 }
729 
730 Datum
732 {
733  BOX *box1 = PG_GETARG_BOX_P(0);
734  BOX *box2 = PG_GETARG_BOX_P(1);
735 
736  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
745 {
746  BOX *box1 = PG_GETARG_BOX_P(0);
747  BOX *box2 = PG_GETARG_BOX_P(1);
748 
749  PG_RETURN_BOOL(FPlt(box_ar(box1), box_ar(box2)));
750 }
751 
752 Datum
754 {
755  BOX *box1 = PG_GETARG_BOX_P(0);
756  BOX *box2 = PG_GETARG_BOX_P(1);
757 
758  PG_RETURN_BOOL(FPgt(box_ar(box1), box_ar(box2)));
759 }
760 
761 Datum
763 {
764  BOX *box1 = PG_GETARG_BOX_P(0);
765  BOX *box2 = PG_GETARG_BOX_P(1);
766 
767  PG_RETURN_BOOL(FPeq(box_ar(box1), box_ar(box2)));
768 }
769 
770 Datum
772 {
773  BOX *box1 = PG_GETARG_BOX_P(0);
774  BOX *box2 = PG_GETARG_BOX_P(1);
775 
776  PG_RETURN_BOOL(FPle(box_ar(box1), box_ar(box2)));
777 }
778 
779 Datum
781 {
782  BOX *box1 = PG_GETARG_BOX_P(0);
783  BOX *box2 = PG_GETARG_BOX_P(1);
784 
785  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
797 {
798  BOX *box = PG_GETARG_BOX_P(0);
799 
800  PG_RETURN_FLOAT8(box_ar(box));
801 }
802 
803 
804 /* box_width - returns the width of the box
805  * (horizontal magnitude).
806  */
807 Datum
809 {
810  BOX *box = PG_GETARG_BOX_P(0);
811 
812  PG_RETURN_FLOAT8(box_wd(box));
813 }
814 
815 
816 /* box_height - returns the height of the box
817  * (vertical magnitude).
818  */
819 Datum
821 {
822  BOX *box = PG_GETARG_BOX_P(0);
823 
824  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
833 {
834  BOX *box1 = PG_GETARG_BOX_P(0);
835  BOX *box2 = PG_GETARG_BOX_P(1);
836  Point a,
837  b;
838 
839  box_cn(&a, box1);
840  box_cn(&b, box2);
841 
843 }
844 
845 
846 /* box_center - returns the center point of the box.
847  */
848 Datum
850 {
851  BOX *box = PG_GETARG_BOX_P(0);
852  Point *result = (Point *) palloc(sizeof(Point));
853 
854  box_cn(result, box);
855 
856  PG_RETURN_POINT_P(result);
857 }
858 
859 
860 /* box_ar - returns the area of the box.
861  */
862 static float8
863 box_ar(BOX *box)
864 {
865  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
872 box_cn(Point *center, BOX *box)
873 {
874  center->x = float8_div(float8_pl(box->high.x, box->low.x), 2.0);
875  center->y = float8_div(float8_pl(box->high.y, box->low.y), 2.0);
876 }
877 
878 
879 /* box_wd - returns the width (length) of the box
880  * (horizontal magnitude).
881  */
882 static float8
883 box_wd(BOX *box)
884 {
885  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
893 box_ht(BOX *box)
894 {
895  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
909 {
910  BOX *box1 = PG_GETARG_BOX_P(0);
911  BOX *box2 = PG_GETARG_BOX_P(1);
912  BOX *result;
913 
914  if (!box_ov(box1, box2))
915  PG_RETURN_NULL();
916 
917  result = (BOX *) palloc(sizeof(BOX));
918 
919  result->high.x = float8_min(box1->high.x, box2->high.x);
920  result->low.x = float8_max(box1->low.x, box2->low.x);
921  result->high.y = float8_min(box1->high.y, box2->high.y);
922  result->low.y = float8_max(box1->low.y, box2->low.y);
923 
924  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
934 {
935  BOX *box = PG_GETARG_BOX_P(0);
936  LSEG *result = (LSEG *) palloc(sizeof(LSEG));
937 
938  statlseg_construct(result, &box->high, &box->low);
939 
940  PG_RETURN_LSEG_P(result);
941 }
942 
943 /***********************************************************************
944  **
945  ** Routines for 2D lines.
946  **
947  ***********************************************************************/
948 
949 static bool
950 line_decode(char *s, const char *str, LINE *line, Node *escontext)
951 {
952  /* s was already advanced over leading '{' */
953  if (!single_decode(s, &line->A, &s, "line", str, escontext))
954  return false;
955  if (*s++ != DELIM)
956  goto fail;
957  if (!single_decode(s, &line->B, &s, "line", str, escontext))
958  return false;
959  if (*s++ != DELIM)
960  goto fail;
961  if (!single_decode(s, &line->C, &s, "line", str, escontext))
962  return false;
963  if (*s++ != RDELIM_L)
964  goto fail;
965  while (isspace((unsigned char) *s))
966  s++;
967  if (*s != '\0')
968  goto fail;
969  return true;
970 
971 fail:
972  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
980 {
981  char *str = PG_GETARG_CSTRING(0);
982  Node *escontext = fcinfo->context;
983  LINE *line = (LINE *) palloc(sizeof(LINE));
984  LSEG lseg;
985  bool isopen;
986  char *s;
987 
988  s = str;
989  while (isspace((unsigned char) *s))
990  s++;
991  if (*s == LDELIM_L)
992  {
993  if (!line_decode(s + 1, str, line, escontext))
994  PG_RETURN_NULL();
995  if (FPzero(line->A) && FPzero(line->B))
996  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  if (!path_decode(s, true, 2, &lseg.p[0], &isopen, NULL, "line", str,
1003  escontext))
1004  PG_RETURN_NULL();
1005  if (point_eq_point(&lseg.p[0], &lseg.p[1]))
1006  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  */
1015  line_construct(line, &lseg.p[0], lseg_sl(&lseg));
1016  }
1017 
1018  PG_RETURN_LINE_P(line);
1019 }
1020 
1021 
1022 Datum
1024 {
1025  LINE *line = PG_GETARG_LINE_P(0);
1026  char *astr = float8out_internal(line->A);
1027  char *bstr = float8out_internal(line->B);
1028  char *cstr = float8out_internal(line->C);
1029 
1030  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
1039 {
1041  LINE *line;
1042 
1043  line = (LINE *) palloc(sizeof(LINE));
1044 
1045  line->A = pq_getmsgfloat8(buf);
1046  line->B = pq_getmsgfloat8(buf);
1047  line->C = pq_getmsgfloat8(buf);
1048 
1049  if (FPzero(line->A) && FPzero(line->B))
1050  ereport(ERROR,
1051  (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
1052  errmsg("invalid line specification: A and B cannot both be zero")));
1053 
1054  PG_RETURN_LINE_P(line);
1055 }
1056 
1057 /*
1058  * line_send - converts line to binary format
1059  */
1060 Datum
1062 {
1063  LINE *line = PG_GETARG_LINE_P(0);
1065 
1066  pq_begintypsend(&buf);
1067  pq_sendfloat8(&buf, line->A);
1068  pq_sendfloat8(&buf, line->B);
1069  pq_sendfloat8(&buf, line->C);
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
1084 {
1085  if (isinf(m))
1086  {
1087  /* vertical - use "x = C" */
1088  result->A = -1.0;
1089  result->B = 0.0;
1090  result->C = pt->x;
1091  }
1092  else if (m == 0)
1093  {
1094  /* horizontal - use "y = C" */
1095  result->A = 0.0;
1096  result->B = -1.0;
1097  result->C = pt->y;
1098  }
1099  else
1100  {
1101  /* use "mx - y + yinter = 0" */
1102  result->A = m;
1103  result->B = -1.0;
1104  result->C = float8_mi(pt->y, float8_mul(m, pt->x));
1105  /* on some platforms, the preceding expression tends to produce -0 */
1106  if (result->C == 0.0)
1107  result->C = 0.0;
1108  }
1109 }
1110 
1111 /* line_construct_pp()
1112  * two points
1113  */
1114 Datum
1116 {
1117  Point *pt1 = PG_GETARG_POINT_P(0);
1118  Point *pt2 = PG_GETARG_POINT_P(1);
1119  LINE *result = (LINE *) palloc(sizeof(LINE));
1120 
1121  if (point_eq_point(pt1, pt2))
1122  ereport(ERROR,
1123  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
1124  errmsg("invalid line specification: must be two distinct points")));
1125 
1126  line_construct(result, pt1, point_sl(pt1, pt2));
1127 
1128  PG_RETURN_LINE_P(result);
1129 }
1130 
1131 
1132 /*----------------------------------------------------------
1133  * Relative position routines.
1134  *---------------------------------------------------------*/
1135 
1136 Datum
1138 {
1139  LINE *l1 = PG_GETARG_LINE_P(0);
1140  LINE *l2 = PG_GETARG_LINE_P(1);
1141 
1142  PG_RETURN_BOOL(line_interpt_line(NULL, l1, l2));
1143 }
1144 
1145 Datum
1147 {
1148  LINE *l1 = PG_GETARG_LINE_P(0);
1149  LINE *l2 = PG_GETARG_LINE_P(1);
1150 
1151  PG_RETURN_BOOL(!line_interpt_line(NULL, l1, l2));
1152 }
1153 
1154 Datum
1156 {
1157  LINE *l1 = PG_GETARG_LINE_P(0);
1158  LINE *l2 = PG_GETARG_LINE_P(1);
1159 
1160  if (FPzero(l1->A))
1161  PG_RETURN_BOOL(FPzero(l2->B));
1162  if (FPzero(l2->A))
1163  PG_RETURN_BOOL(FPzero(l1->B));
1164  if (FPzero(l1->B))
1165  PG_RETURN_BOOL(FPzero(l2->A));
1166  if (FPzero(l2->B))
1167  PG_RETURN_BOOL(FPzero(l1->A));
1168 
1170  float8_mul(l1->B, l2->B)), -1.0));
1171 }
1172 
1173 Datum
1175 {
1176  LINE *line = PG_GETARG_LINE_P(0);
1177 
1178  PG_RETURN_BOOL(FPzero(line->B));
1179 }
1180 
1181 Datum
1183 {
1184  LINE *line = PG_GETARG_LINE_P(0);
1185 
1186  PG_RETURN_BOOL(FPzero(line->A));
1187 }
1188 
1189 
1190 /*
1191  * Check whether the two lines are the same
1192  */
1193 Datum
1195 {
1196  LINE *l1 = PG_GETARG_LINE_P(0);
1197  LINE *l2 = PG_GETARG_LINE_P(1);
1198  float8 ratio;
1199 
1200  /* If any NaNs are involved, insist on exact equality */
1201  if (unlikely(isnan(l1->A) || isnan(l1->B) || isnan(l1->C) ||
1202  isnan(l2->A) || isnan(l2->B) || isnan(l2->C)))
1203  {
1204  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  if (!FPzero(l2->A))
1211  ratio = float8_div(l1->A, l2->A);
1212  else if (!FPzero(l2->B))
1213  ratio = float8_div(l1->B, l2->B);
1214  else if (!FPzero(l2->C))
1215  ratio = float8_div(l1->C, l2->C);
1216  else
1217  ratio = 1.0;
1218 
1219  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
1234 {
1235  if (FPzero(line->A))
1236  return 0.0;
1237  if (FPzero(line->B))
1238  return get_float8_infinity();
1239  return float8_div(line->A, -line->B);
1240 }
1241 
1242 
1243 /*
1244  * Return inverse slope of the line
1245  */
1246 static inline float8
1248 {
1249  if (FPzero(line->A))
1250  return get_float8_infinity();
1251  if (FPzero(line->B))
1252  return 0.0;
1253  return float8_div(line->B, line->A);
1254 }
1255 
1256 
1257 /* line_distance()
1258  * Distance between two lines.
1259  */
1260 Datum
1262 {
1263  LINE *l1 = PG_GETARG_LINE_P(0);
1264  LINE *l2 = PG_GETARG_LINE_P(1);
1265  float8 ratio;
1266 
1267  if (line_interpt_line(NULL, l1, l2)) /* intersecting? */
1268  PG_RETURN_FLOAT8(0.0);
1269 
1270  if (!FPzero(l1->A) && !isnan(l1->A) && !FPzero(l2->A) && !isnan(l2->A))
1271  ratio = float8_div(l1->A, l2->A);
1272  else if (!FPzero(l1->B) && !isnan(l1->B) && !FPzero(l2->B) && !isnan(l2->B))
1273  ratio = float8_div(l1->B, l2->B);
1274  else
1275  ratio = 1.0;
1276 
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
1287 {
1288  LINE *l1 = PG_GETARG_LINE_P(0);
1289  LINE *l2 = PG_GETARG_LINE_P(1);
1290  Point *result;
1291 
1292  result = (Point *) palloc(sizeof(Point));
1293 
1294  if (!line_interpt_line(result, l1, l2))
1295  PG_RETURN_NULL();
1296  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
1314 line_interpt_line(Point *result, LINE *l1, LINE *l2)
1315 {
1316  float8 x,
1317  y;
1318 
1319  if (!FPzero(l1->B))
1320  {
1321  if (FPeq(l2->A, float8_mul(l1->A, float8_div(l2->B, l1->B))))
1322  return false;
1323 
1324  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  y = float8_div(-float8_pl(float8_mul(l1->A, x), l1->C), l1->B);
1329  }
1330  else if (!FPzero(l2->B))
1331  {
1332  if (FPeq(l1->A, float8_mul(l2->A, float8_div(l1->B, l2->B))))
1333  return false;
1334 
1335  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  y = float8_div(-float8_pl(float8_mul(l2->A, x), l2->C), l2->B);
1340  }
1341  else
1342  return false;
1343 
1344  /* On some platforms, the preceding expressions tend to produce -0. */
1345  if (x == 0.0)
1346  x = 0.0;
1347  if (y == 0.0)
1348  y = 0.0;
1349 
1350  if (result != NULL)
1351  point_construct(result, x, y);
1352 
1353  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
1381 {
1382  PATH *path = PG_GETARG_PATH_P(0);
1383  float8 area = 0.0;
1384  int i,
1385  j;
1386 
1387  if (!path->closed)
1388  PG_RETURN_NULL();
1389 
1390  for (i = 0; i < path->npts; i++)
1391  {
1392  j = (i + 1) % path->npts;
1393  area = float8_pl(area, float8_mul(path->p[i].x, path->p[j].y));
1394  area = float8_mi(area, float8_mul(path->p[i].y, path->p[j].x));
1395  }
1396 
1397  PG_RETURN_FLOAT8(float8_div(fabs(area), 2.0));
1398 }
1399 
1400 
1401 Datum
1403 {
1404  char *str = PG_GETARG_CSTRING(0);
1405  Node *escontext = fcinfo->context;
1406  PATH *path;
1407  bool isopen;
1408  char *s;
1409  int npts;
1410  int size;
1411  int base_size;
1412  int depth = 0;
1413 
1414  if ((npts = pair_count(str, ',')) <= 0)
1415  ereturn(escontext, (Datum) 0,
1416  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1417  errmsg("invalid input syntax for type %s: \"%s\"",
1418  "path", str)));
1419 
1420  s = str;
1421  while (isspace((unsigned char) *s))
1422  s++;
1423 
1424  /* skip single leading paren */
1425  if ((*s == LDELIM) && (strrchr(s, LDELIM) == s))
1426  {
1427  s++;
1428  depth++;
1429  }
1430 
1431  base_size = sizeof(path->p[0]) * npts;
1432  size = offsetof(PATH, p) + base_size;
1433 
1434  /* Check for integer overflow */
1435  if (base_size / npts != sizeof(path->p[0]) || size <= base_size)
1436  ereturn(escontext, (Datum) 0,
1437  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1438  errmsg("too many points requested")));
1439 
1440  path = (PATH *) palloc(size);
1441 
1442  SET_VARSIZE(path, size);
1443  path->npts = npts;
1444 
1445  if (!path_decode(s, true, npts, &(path->p[0]), &isopen, &s, "path", str,
1446  escontext))
1447  PG_RETURN_NULL();
1448 
1449  if (depth >= 1)
1450  {
1451  if (*s++ != RDELIM)
1452  ereturn(escontext, (Datum) 0,
1453  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1454  errmsg("invalid input syntax for type %s: \"%s\"",
1455  "path", str)));
1456  while (isspace((unsigned char) *s))
1457  s++;
1458  }
1459  if (*s != '\0')
1460  ereturn(escontext, (Datum) 0,
1461  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
1462  errmsg("invalid input syntax for type %s: \"%s\"",
1463  "path", str)));
1464 
1465  path->closed = (!isopen);
1466  /* prevent instability in unused pad bytes */
1467  path->dummy = 0;
1468 
1469  PG_RETURN_PATH_P(path);
1470 }
1471 
1472 
1473 Datum
1475 {
1476  PATH *path = PG_GETARG_PATH_P(0);
1477 
1478  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
1489 {
1491  PATH *path;
1492  int closed;
1493  int32 npts;
1494  int32 i;
1495  int size;
1496 
1497  closed = pq_getmsgbyte(buf);
1498  npts = pq_getmsgint(buf, sizeof(int32));
1499  if (npts <= 0 || npts >= (int32) ((INT_MAX - offsetof(PATH, p)) / sizeof(Point)))
1500  ereport(ERROR,
1501  (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
1502  errmsg("invalid number of points in external \"path\" value")));
1503 
1504  size = offsetof(PATH, p) + sizeof(path->p[0]) * npts;
1505  path = (PATH *) palloc(size);
1506 
1507  SET_VARSIZE(path, size);
1508  path->npts = npts;
1509  path->closed = (closed ? 1 : 0);
1510  /* prevent instability in unused pad bytes */
1511  path->dummy = 0;
1512 
1513  for (i = 0; i < npts; i++)
1514  {
1515  path->p[i].x = pq_getmsgfloat8(buf);
1516  path->p[i].y = pq_getmsgfloat8(buf);
1517  }
1518 
1519  PG_RETURN_PATH_P(path);
1520 }
1521 
1522 /*
1523  * path_send - converts path to binary format
1524  */
1525 Datum
1527 {
1528  PATH *path = PG_GETARG_PATH_P(0);
1530  int32 i;
1531 
1532  pq_begintypsend(&buf);
1533  pq_sendbyte(&buf, path->closed ? 1 : 0);
1534  pq_sendint32(&buf, path->npts);
1535  for (i = 0; i < path->npts; i++)
1536  {
1537  pq_sendfloat8(&buf, path->p[i].x);
1538  pq_sendfloat8(&buf, path->p[i].y);
1539  }
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
1554 {
1555  PATH *p1 = PG_GETARG_PATH_P(0);
1556  PATH *p2 = PG_GETARG_PATH_P(1);
1557 
1558  PG_RETURN_BOOL(p1->npts < p2->npts);
1559 }
1560 
1561 Datum
1563 {
1564  PATH *p1 = PG_GETARG_PATH_P(0);
1565  PATH *p2 = PG_GETARG_PATH_P(1);
1566 
1567  PG_RETURN_BOOL(p1->npts > p2->npts);
1568 }
1569 
1570 Datum
1572 {
1573  PATH *p1 = PG_GETARG_PATH_P(0);
1574  PATH *p2 = PG_GETARG_PATH_P(1);
1575 
1576  PG_RETURN_BOOL(p1->npts == p2->npts);
1577 }
1578 
1579 Datum
1581 {
1582  PATH *p1 = PG_GETARG_PATH_P(0);
1583  PATH *p2 = PG_GETARG_PATH_P(1);
1584 
1585  PG_RETURN_BOOL(p1->npts <= p2->npts);
1586 }
1587 
1588 Datum
1590 {
1591  PATH *p1 = PG_GETARG_PATH_P(0);
1592  PATH *p2 = PG_GETARG_PATH_P(1);
1593 
1594  PG_RETURN_BOOL(p1->npts >= p2->npts);
1595 }
1596 
1597 /*----------------------------------------------------------
1598  * Conversion operators.
1599  *---------------------------------------------------------*/
1600 
1601 Datum
1603 {
1604  PATH *path = PG_GETARG_PATH_P(0);
1605 
1606  PG_RETURN_BOOL(path->closed);
1607 }
1608 
1609 Datum
1611 {
1612  PATH *path = PG_GETARG_PATH_P(0);
1613 
1614  PG_RETURN_BOOL(!path->closed);
1615 }
1616 
1617 Datum
1619 {
1620  PATH *path = PG_GETARG_PATH_P(0);
1621 
1622  PG_RETURN_INT32(path->npts);
1623 }
1624 
1625 
1626 Datum
1628 {
1629  PATH *path = PG_GETARG_PATH_P_COPY(0);
1630 
1631  path->closed = true;
1632 
1633  PG_RETURN_PATH_P(path);
1634 }
1635 
1636 Datum
1638 {
1639  PATH *path = PG_GETARG_PATH_P_COPY(0);
1640 
1641  path->closed = false;
1642 
1643  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
1654 {
1655  PATH *p1 = PG_GETARG_PATH_P(0);
1656  PATH *p2 = PG_GETARG_PATH_P(1);
1657  BOX b1,
1658  b2;
1659  int i,
1660  j;
1661  LSEG seg1,
1662  seg2;
1663 
1664  Assert(p1->npts > 0 && p2->npts > 0);
1665 
1666  b1.high.x = b1.low.x = p1->p[0].x;
1667  b1.high.y = b1.low.y = p1->p[0].y;
1668  for (i = 1; i < p1->npts; i++)
1669  {
1670  b1.high.x = float8_max(p1->p[i].x, b1.high.x);
1671  b1.high.y = float8_max(p1->p[i].y, b1.high.y);
1672  b1.low.x = float8_min(p1->p[i].x, b1.low.x);
1673  b1.low.y = float8_min(p1->p[i].y, b1.low.y);
1674  }
1675  b2.high.x = b2.low.x = p2->p[0].x;
1676  b2.high.y = b2.low.y = p2->p[0].y;
1677  for (i = 1; i < p2->npts; i++)
1678  {
1679  b2.high.x = float8_max(p2->p[i].x, b2.high.x);
1680  b2.high.y = float8_max(p2->p[i].y, b2.high.y);
1681  b2.low.x = float8_min(p2->p[i].x, b2.low.x);
1682  b2.low.y = float8_min(p2->p[i].y, b2.low.y);
1683  }
1684  if (!box_ov(&b1, &b2))
1685  PG_RETURN_BOOL(false);
1686 
1687  /* pairwise check lseg intersections */
1688  for (i = 0; i < p1->npts; i++)
1689  {
1690  int iprev;
1691 
1692  if (i > 0)
1693  iprev = i - 1;
1694  else
1695  {
1696  if (!p1->closed)
1697  continue;
1698  iprev = p1->npts - 1; /* include the closure segment */
1699  }
1700 
1701  for (j = 0; j < p2->npts; j++)
1702  {
1703  int jprev;
1704 
1705  if (j > 0)
1706  jprev = j - 1;
1707  else
1708  {
1709  if (!p2->closed)
1710  continue;
1711  jprev = p2->npts - 1; /* include the closure segment */
1712  }
1713 
1714  statlseg_construct(&seg1, &p1->p[iprev], &p1->p[i]);
1715  statlseg_construct(&seg2, &p2->p[jprev], &p2->p[j]);
1716  if (lseg_interpt_lseg(NULL, &seg1, &seg2))
1717  PG_RETURN_BOOL(true);
1718  }
1719  }
1720 
1721  /* if we dropped through, no two segs intersected */
1722  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
1731 {
1732  PATH *p1 = PG_GETARG_PATH_P(0);
1733  PATH *p2 = PG_GETARG_PATH_P(1);
1734  float8 min = 0.0; /* initialize to keep compiler quiet */
1735  bool have_min = false;
1736  float8 tmp;
1737  int i,
1738  j;
1739  LSEG seg1,
1740  seg2;
1741 
1742  for (i = 0; i < p1->npts; i++)
1743  {
1744  int iprev;
1745 
1746  if (i > 0)
1747  iprev = i - 1;
1748  else
1749  {
1750  if (!p1->closed)
1751  continue;
1752  iprev = p1->npts - 1; /* include the closure segment */
1753  }
1754 
1755  for (j = 0; j < p2->npts; j++)
1756  {
1757  int jprev;
1758 
1759  if (j > 0)
1760  jprev = j - 1;
1761  else
1762  {
1763  if (!p2->closed)
1764  continue;
1765  jprev = p2->npts - 1; /* include the closure segment */
1766  }
1767 
1768  statlseg_construct(&seg1, &p1->p[iprev], &p1->p[i]);
1769  statlseg_construct(&seg2, &p2->p[jprev], &p2->p[j]);
1770 
1771  tmp = lseg_closept_lseg(NULL, &seg1, &seg2);
1772  if (!have_min || float8_lt(tmp, min))
1773  {
1774  min = tmp;
1775  have_min = true;
1776  }
1777  }
1778  }
1779 
1780  if (!have_min)
1781  PG_RETURN_NULL();
1782 
1783  PG_RETURN_FLOAT8(min);
1784 }
1785 
1786 
1787 /*----------------------------------------------------------
1788  * "Arithmetic" operations.
1789  *---------------------------------------------------------*/
1790 
1791 Datum
1793 {
1794  PATH *path = PG_GETARG_PATH_P(0);
1795  float8 result = 0.0;
1796  int i;
1797 
1798  for (i = 0; i < path->npts; i++)
1799  {
1800  int iprev;
1801 
1802  if (i > 0)
1803  iprev = i - 1;
1804  else
1805  {
1806  if (!path->closed)
1807  continue;
1808  iprev = path->npts - 1; /* include the closure segment */
1809  }
1810 
1811  result = float8_pl(result, point_dt(&path->p[iprev], &path->p[i]));
1812  }
1813 
1814  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
1832 {
1833  char *str = PG_GETARG_CSTRING(0);
1834  Point *point = (Point *) palloc(sizeof(Point));
1835 
1836  /* Ignore failure from pair_decode, since our return value won't matter */
1837  pair_decode(str, &point->x, &point->y, NULL, "point", str, fcinfo->context);
1838  PG_RETURN_POINT_P(point);
1839 }
1840 
1841 Datum
1843 {
1844  Point *pt = PG_GETARG_POINT_P(0);
1845 
1847 }
1848 
1849 /*
1850  * point_recv - converts external binary format to point
1851  */
1852 Datum
1854 {
1856  Point *point;
1857 
1858  point = (Point *) palloc(sizeof(Point));
1859  point->x = pq_getmsgfloat8(buf);
1860  point->y = pq_getmsgfloat8(buf);
1861  PG_RETURN_POINT_P(point);
1862 }
1863 
1864 /*
1865  * point_send - converts point to binary format
1866  */
1867 Datum
1869 {
1870  Point *pt = PG_GETARG_POINT_P(0);
1872 
1873  pq_begintypsend(&buf);
1874  pq_sendfloat8(&buf, pt->x);
1875  pq_sendfloat8(&buf, pt->y);
1877 }
1878 
1879 
1880 /*
1881  * Initialize a point
1882  */
1883 static inline void
1885 {
1886  result->x = x;
1887  result->y = y;
1888 }
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
1902 {
1903  Point *pt1 = PG_GETARG_POINT_P(0);
1904  Point *pt2 = PG_GETARG_POINT_P(1);
1905 
1906  PG_RETURN_BOOL(FPlt(pt1->x, pt2->x));
1907 }
1908 
1909 Datum
1911 {
1912  Point *pt1 = PG_GETARG_POINT_P(0);
1913  Point *pt2 = PG_GETARG_POINT_P(1);
1914 
1915  PG_RETURN_BOOL(FPgt(pt1->x, pt2->x));
1916 }
1917 
1918 Datum
1920 {
1921  Point *pt1 = PG_GETARG_POINT_P(0);
1922  Point *pt2 = PG_GETARG_POINT_P(1);
1923 
1924  PG_RETURN_BOOL(FPgt(pt1->y, pt2->y));
1925 }
1926 
1927 Datum
1929 {
1930  Point *pt1 = PG_GETARG_POINT_P(0);
1931  Point *pt2 = PG_GETARG_POINT_P(1);
1932 
1933  PG_RETURN_BOOL(FPlt(pt1->y, pt2->y));
1934 }
1935 
1936 Datum
1938 {
1939  Point *pt1 = PG_GETARG_POINT_P(0);
1940  Point *pt2 = PG_GETARG_POINT_P(1);
1941 
1942  PG_RETURN_BOOL(FPeq(pt1->x, pt2->x));
1943 }
1944 
1945 Datum
1947 {
1948  Point *pt1 = PG_GETARG_POINT_P(0);
1949  Point *pt2 = PG_GETARG_POINT_P(1);
1950 
1951  PG_RETURN_BOOL(FPeq(pt1->y, pt2->y));
1952 }
1953 
1954 Datum
1956 {
1957  Point *pt1 = PG_GETARG_POINT_P(0);
1958  Point *pt2 = PG_GETARG_POINT_P(1);
1959 
1960  PG_RETURN_BOOL(point_eq_point(pt1, pt2));
1961 }
1962 
1963 Datum
1965 {
1966  Point *pt1 = PG_GETARG_POINT_P(0);
1967  Point *pt2 = PG_GETARG_POINT_P(1);
1968 
1969  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
1978 {
1979  /* If any NaNs are involved, insist on exact equality */
1980  if (unlikely(isnan(pt1->x) || isnan(pt1->y) ||
1981  isnan(pt2->x) || isnan(pt2->y)))
1982  return (float8_eq(pt1->x, pt2->x) && float8_eq(pt1->y, pt2->y));
1983 
1984  return (FPeq(pt1->x, pt2->x) && FPeq(pt1->y, pt2->y));
1985 }
1986 
1987 
1988 /*----------------------------------------------------------
1989  * "Arithmetic" operators on points.
1990  *---------------------------------------------------------*/
1991 
1992 Datum
1994 {
1995  Point *pt1 = PG_GETARG_POINT_P(0);
1996  Point *pt2 = PG_GETARG_POINT_P(1);
1997 
1998  PG_RETURN_FLOAT8(point_dt(pt1, pt2));
1999 }
2000 
2001 static inline float8
2002 point_dt(Point *pt1, Point *pt2)
2003 {
2004  return HYPOT(float8_mi(pt1->x, pt2->x), float8_mi(pt1->y, pt2->y));
2005 }
2006 
2007 Datum
2009 {
2010  Point *pt1 = PG_GETARG_POINT_P(0);
2011  Point *pt2 = PG_GETARG_POINT_P(1);
2012 
2013  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
2023 point_sl(Point *pt1, Point *pt2)
2024 {
2025  if (FPeq(pt1->x, pt2->x))
2026  return get_float8_infinity();
2027  if (FPeq(pt1->y, pt2->y))
2028  return 0.0;
2029  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
2040 {
2041  if (FPeq(pt1->x, pt2->x))
2042  return 0.0;
2043  if (FPeq(pt1->y, pt2->y))
2044  return get_float8_infinity();
2045  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
2066 {
2067  char *str = PG_GETARG_CSTRING(0);
2068  Node *escontext = fcinfo->context;
2069  LSEG *lseg = (LSEG *) palloc(sizeof(LSEG));
2070  bool isopen;
2071 
2072  if (!path_decode(str, true, 2, &lseg->p[0], &isopen, NULL, "lseg", str,
2073  escontext))
2074  PG_RETURN_NULL();
2075 
2076  PG_RETURN_LSEG_P(lseg);
2077 }
2078 
2079 
2080 Datum
2082 {
2083  LSEG *ls = PG_GETARG_LSEG_P(0);
2084 
2085  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
2093 {
2095  LSEG *lseg;
2096 
2097  lseg = (LSEG *) palloc(sizeof(LSEG));
2098 
2099  lseg->p[0].x = pq_getmsgfloat8(buf);
2100  lseg->p[0].y = pq_getmsgfloat8(buf);
2101  lseg->p[1].x = pq_getmsgfloat8(buf);
2102  lseg->p[1].y = pq_getmsgfloat8(buf);
2103 
2104  PG_RETURN_LSEG_P(lseg);
2105 }
2106 
2107 /*
2108  * lseg_send - converts lseg to binary format
2109  */
2110 Datum
2112 {
2113  LSEG *ls = PG_GETARG_LSEG_P(0);
2115 
2116  pq_begintypsend(&buf);
2117  pq_sendfloat8(&buf, ls->p[0].x);
2118  pq_sendfloat8(&buf, ls->p[0].y);
2119  pq_sendfloat8(&buf, ls->p[1].x);
2120  pq_sendfloat8(&buf, ls->p[1].y);
2122 }
2123 
2124 
2125 /* lseg_construct -
2126  * form a LSEG from two Points.
2127  */
2128 Datum
2130 {
2131  Point *pt1 = PG_GETARG_POINT_P(0);
2132  Point *pt2 = PG_GETARG_POINT_P(1);
2133  LSEG *result = (LSEG *) palloc(sizeof(LSEG));
2134 
2135  statlseg_construct(result, pt1, pt2);
2136 
2137  PG_RETURN_LSEG_P(result);
2138 }
2139 
2140 /* like lseg_construct, but assume space already allocated */
2141 static inline void
2143 {
2144  lseg->p[0].x = pt1->x;
2145  lseg->p[0].y = pt1->y;
2146  lseg->p[1].x = pt2->x;
2147  lseg->p[1].y = pt2->y;
2148 }
2149 
2150 
2151 /*
2152  * Return slope of the line segment
2153  */
2154 static inline float8
2156 {
2157  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
2166 {
2167  return point_invsl(&lseg->p[0], &lseg->p[1]);
2168 }
2169 
2170 
2171 Datum
2173 {
2174  LSEG *lseg = PG_GETARG_LSEG_P(0);
2175 
2176  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
2189 {
2190  LSEG *l1 = PG_GETARG_LSEG_P(0);
2191  LSEG *l2 = PG_GETARG_LSEG_P(1);
2192 
2193  PG_RETURN_BOOL(lseg_interpt_lseg(NULL, l1, l2));
2194 }
2195 
2196 
2197 Datum
2199 {
2200  LSEG *l1 = PG_GETARG_LSEG_P(0);
2201  LSEG *l2 = PG_GETARG_LSEG_P(1);
2202 
2203  PG_RETURN_BOOL(FPeq(lseg_sl(l1), lseg_sl(l2)));
2204 }
2205 
2206 /*
2207  * Determine if two line segments are perpendicular.
2208  */
2209 Datum
2211 {
2212  LSEG *l1 = PG_GETARG_LSEG_P(0);
2213  LSEG *l2 = PG_GETARG_LSEG_P(1);
2214 
2216 }
2217 
2218 Datum
2220 {
2221  LSEG *lseg = PG_GETARG_LSEG_P(0);
2222 
2223  PG_RETURN_BOOL(FPeq(lseg->p[0].x, lseg->p[1].x));
2224 }
2225 
2226 Datum
2228 {
2229  LSEG *lseg = PG_GETARG_LSEG_P(0);
2230 
2231  PG_RETURN_BOOL(FPeq(lseg->p[0].y, lseg->p[1].y));
2232 }
2233 
2234 
2235 Datum
2237 {
2238  LSEG *l1 = PG_GETARG_LSEG_P(0);
2239  LSEG *l2 = PG_GETARG_LSEG_P(1);
2240 
2241  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
2247 {
2248  LSEG *l1 = PG_GETARG_LSEG_P(0);
2249  LSEG *l2 = PG_GETARG_LSEG_P(1);
2250 
2251  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
2257 {
2258  LSEG *l1 = PG_GETARG_LSEG_P(0);
2259  LSEG *l2 = PG_GETARG_LSEG_P(1);
2260 
2261  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
2267 {
2268  LSEG *l1 = PG_GETARG_LSEG_P(0);
2269  LSEG *l2 = PG_GETARG_LSEG_P(1);
2270 
2271  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
2277 {
2278  LSEG *l1 = PG_GETARG_LSEG_P(0);
2279  LSEG *l2 = PG_GETARG_LSEG_P(1);
2280 
2281  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
2287 {
2288  LSEG *l1 = PG_GETARG_LSEG_P(0);
2289  LSEG *l2 = PG_GETARG_LSEG_P(1);
2290 
2291  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
2307 {
2308  LSEG *l1 = PG_GETARG_LSEG_P(0);
2309  LSEG *l2 = PG_GETARG_LSEG_P(1);
2310 
2311  PG_RETURN_FLOAT8(lseg_closept_lseg(NULL, l1, l2));
2312 }
2313 
2314 
2315 Datum
2317 {
2318  LSEG *lseg = PG_GETARG_LSEG_P(0);
2319  Point *result;
2320 
2321  result = (Point *) palloc(sizeof(Point));
2322 
2323  result->x = float8_div(float8_pl(lseg->p[0].x, lseg->p[1].x), 2.0);
2324  result->y = float8_div(float8_pl(lseg->p[0].y, lseg->p[1].y), 2.0);
2325 
2326  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
2338 lseg_interpt_lseg(Point *result, LSEG *l1, LSEG *l2)
2339 {
2340  Point interpt;
2341  LINE tmp;
2342 
2343  line_construct(&tmp, &l2->p[0], lseg_sl(l2));
2344  if (!lseg_interpt_line(&interpt, l1, &tmp))
2345  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  if (!lseg_contain_point(l2, &interpt))
2352  return false;
2353 
2354  if (result != NULL)
2355  *result = interpt;
2356 
2357  return true;
2358 }
2359 
2360 Datum
2362 {
2363  LSEG *l1 = PG_GETARG_LSEG_P(0);
2364  LSEG *l2 = PG_GETARG_LSEG_P(1);
2365  Point *result;
2366 
2367  result = (Point *) palloc(sizeof(Point));
2368 
2369  if (!lseg_interpt_lseg(result, l1, l2))
2370  PG_RETURN_NULL();
2371  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
2391 {
2392  Point *pt = PG_GETARG_POINT_P(0);
2393  LINE *line = PG_GETARG_LINE_P(1);
2394 
2395  PG_RETURN_FLOAT8(line_closept_point(NULL, line, pt));
2396 }
2397 
2398 /*
2399  * Distance from a line to a point
2400  */
2401 Datum
2403 {
2404  LINE *line = PG_GETARG_LINE_P(0);
2405  Point *pt = PG_GETARG_POINT_P(1);
2406 
2407  PG_RETURN_FLOAT8(line_closept_point(NULL, line, pt));
2408 }
2409 
2410 /*
2411  * Distance from a point to a lseg
2412  */
2413 Datum
2415 {
2416  Point *pt = PG_GETARG_POINT_P(0);
2417  LSEG *lseg = PG_GETARG_LSEG_P(1);
2418 
2419  PG_RETURN_FLOAT8(lseg_closept_point(NULL, lseg, pt));
2420 }
2421 
2422 /*
2423  * Distance from a lseg to a point
2424  */
2425 Datum
2427 {
2428  LSEG *lseg = PG_GETARG_LSEG_P(0);
2429  Point *pt = PG_GETARG_POINT_P(1);
2430 
2431  PG_RETURN_FLOAT8(lseg_closept_point(NULL, lseg, pt));
2432 }
2433 
2434 static float8
2436 {
2437  float8 result = 0.0; /* keep compiler quiet */
2438  bool have_min = false;
2439  float8 tmp;
2440  int i;
2441  LSEG lseg;
2442 
2443  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  for (i = 0; i < path->npts; i++)
2450  {
2451  int iprev;
2452 
2453  if (i > 0)
2454  iprev = i - 1;
2455  else
2456  {
2457  if (!path->closed)
2458  continue;
2459  iprev = path->npts - 1; /* Include the closure segment */
2460  }
2461 
2462  statlseg_construct(&lseg, &path->p[iprev], &path->p[i]);
2463  tmp = lseg_closept_point(NULL, &lseg, pt);
2464  if (!have_min || float8_lt(tmp, result))
2465  {
2466  result = tmp;
2467  have_min = true;
2468  }
2469  }
2470 
2471  return result;
2472 }
2473 
2474 /*
2475  * Distance from a point to a path
2476  */
2477 Datum
2479 {
2480  Point *pt = PG_GETARG_POINT_P(0);
2481  PATH *path = PG_GETARG_PATH_P(1);
2482 
2484 }
2485 
2486 /*
2487  * Distance from a path to a point
2488  */
2489 Datum
2491 {
2492  PATH *path = PG_GETARG_PATH_P(0);
2493  Point *pt = PG_GETARG_POINT_P(1);
2494 
2496 }
2497 
2498 /*
2499  * Distance from a point to a box
2500  */
2501 Datum
2503 {
2504  Point *pt = PG_GETARG_POINT_P(0);
2505  BOX *box = PG_GETARG_BOX_P(1);
2506 
2507  PG_RETURN_FLOAT8(box_closept_point(NULL, box, pt));
2508 }
2509 
2510 /*
2511  * Distance from a box to a point
2512  */
2513 Datum
2515 {
2516  BOX *box = PG_GETARG_BOX_P(0);
2517  Point *pt = PG_GETARG_POINT_P(1);
2518 
2519  PG_RETURN_FLOAT8(box_closept_point(NULL, box, pt));
2520 }
2521 
2522 /*
2523  * Distance from a lseg to a line
2524  */
2525 Datum
2527 {
2528  LSEG *lseg = PG_GETARG_LSEG_P(0);
2529  LINE *line = PG_GETARG_LINE_P(1);
2530 
2531  PG_RETURN_FLOAT8(lseg_closept_line(NULL, lseg, line));
2532 }
2533 
2534 /*
2535  * Distance from a line to a lseg
2536  */
2537 Datum
2539 {
2540  LINE *line = PG_GETARG_LINE_P(0);
2541  LSEG *lseg = PG_GETARG_LSEG_P(1);
2542 
2543  PG_RETURN_FLOAT8(lseg_closept_line(NULL, lseg, line));
2544 }
2545 
2546 /*
2547  * Distance from a lseg to a box
2548  */
2549 Datum
2551 {
2552  LSEG *lseg = PG_GETARG_LSEG_P(0);
2553  BOX *box = PG_GETARG_BOX_P(1);
2554 
2555  PG_RETURN_FLOAT8(box_closept_lseg(NULL, box, lseg));
2556 }
2557 
2558 /*
2559  * Distance from a box to a lseg
2560  */
2561 Datum
2563 {
2564  BOX *box = PG_GETARG_BOX_P(0);
2565  LSEG *lseg = PG_GETARG_LSEG_P(1);
2566 
2567  PG_RETURN_FLOAT8(box_closept_lseg(NULL, box, lseg));
2568 }
2569 
2570 static float8
2572 {
2573  float8 result;
2574 
2575  /* calculate distance to center, and subtract radius */
2576  result = float8_mi(dist_ppoly_internal(&circle->center, poly),
2577  circle->radius);
2578  if (result < 0.0)
2579  result = 0.0;
2580 
2581  return result;
2582 }
2583 
2584 /*
2585  * Distance from a circle to a polygon
2586  */
2587 Datum
2589 {
2590  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
2591  POLYGON *poly = PG_GETARG_POLYGON_P(1);
2592 
2593  PG_RETURN_FLOAT8(dist_cpoly_internal(circle, poly));
2594 }
2595 
2596 /*
2597  * Distance from a polygon to a circle
2598  */
2599 Datum
2601 {
2602  POLYGON *poly = PG_GETARG_POLYGON_P(0);
2603  CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
2604 
2605  PG_RETURN_FLOAT8(dist_cpoly_internal(circle, poly));
2606 }
2607 
2608 /*
2609  * Distance from a point to a polygon
2610  */
2611 Datum
2613 {
2614  Point *point = PG_GETARG_POINT_P(0);
2615  POLYGON *poly = PG_GETARG_POLYGON_P(1);
2616 
2617  PG_RETURN_FLOAT8(dist_ppoly_internal(point, poly));
2618 }
2619 
2620 Datum
2622 {
2623  POLYGON *poly = PG_GETARG_POLYGON_P(0);
2624  Point *point = PG_GETARG_POINT_P(1);
2625 
2626  PG_RETURN_FLOAT8(dist_ppoly_internal(point, poly));
2627 }
2628 
2629 static float8
2631 {
2632  float8 result;
2633  float8 d;
2634  int i;
2635  LSEG seg;
2636 
2637  if (point_inside(pt, poly->npts, poly->p) != 0)
2638  return 0.0;
2639 
2640  /* initialize distance with segment between first and last points */
2641  seg.p[0].x = poly->p[0].x;
2642  seg.p[0].y = poly->p[0].y;
2643  seg.p[1].x = poly->p[poly->npts - 1].x;
2644  seg.p[1].y = poly->p[poly->npts - 1].y;
2645  result = lseg_closept_point(NULL, &seg, pt);
2646 
2647  /* check distances for other segments */
2648  for (i = 0; i < poly->npts - 1; i++)
2649  {
2650  seg.p[0].x = poly->p[i].x;
2651  seg.p[0].y = poly->p[i].y;
2652  seg.p[1].x = poly->p[i + 1].x;
2653  seg.p[1].y = poly->p[i + 1].y;
2654  d = lseg_closept_point(NULL, &seg, pt);
2655  if (float8_lt(d, result))
2656  result = d;
2657  }
2658 
2659  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
2675 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  line_construct(&tmp, &lseg->p[0], lseg_sl(lseg));
2686  if (!line_interpt_line(&interpt, &tmp, line))
2687  return false;
2688 
2689  /*
2690  * Then, we check whether the intersection point is actually on the line
2691  * segment.
2692  */
2693  if (!lseg_contain_point(lseg, &interpt))
2694  return false;
2695  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  if (point_eq_point(&lseg->p[0], &interpt))
2703  *result = lseg->p[0];
2704  else if (point_eq_point(&lseg->p[1], &interpt))
2705  *result = lseg->p[1];
2706  else
2707  *result = interpt;
2708  }
2709 
2710  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 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  line_construct(&tmp, point, line_invsl(line));
2735  if (!line_interpt_line(&closept, &tmp, line))
2736  {
2737  if (result != NULL)
2738  *result = *point;
2739 
2740  return get_float8_nan();
2741  }
2742 
2743  if (result != NULL)
2744  *result = closept;
2745 
2746  return point_dt(&closept, point);
2747 }
2748 
2749 Datum
2751 {
2752  Point *pt = PG_GETARG_POINT_P(0);
2753  LINE *line = PG_GETARG_LINE_P(1);
2754  Point *result;
2755 
2756  result = (Point *) palloc(sizeof(Point));
2757 
2758  if (isnan(line_closept_point(result, line, pt)))
2759  PG_RETURN_NULL();
2760 
2761  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
2772 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  line_construct(&tmp, pt, point_invsl(&lseg->p[0], &lseg->p[1]));
2782  lseg_closept_line(&closept, lseg, &tmp);
2783 
2784  if (result != NULL)
2785  *result = closept;
2786 
2787  return point_dt(&closept, pt);
2788 }
2789 
2790 Datum
2792 {
2793  Point *pt = PG_GETARG_POINT_P(0);
2794  LSEG *lseg = PG_GETARG_LSEG_P(1);
2795  Point *result;
2796 
2797  result = (Point *) palloc(sizeof(Point));
2798 
2799  if (isnan(lseg_closept_point(result, lseg, pt)))
2800  PG_RETURN_NULL();
2801 
2802  PG_RETURN_POINT_P(result);
2803 }
2804 
2805 
2806 /*
2807  * Closest point on line segment to line segment
2808  */
2809 static float8
2810 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  if (lseg_interpt_lseg(result, on_lseg, to_lseg))
2818  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  */
2824  dist = lseg_closept_point(result, on_lseg, &to_lseg->p[0]);
2825  d = lseg_closept_point(&point, on_lseg, &to_lseg->p[1]);
2826  if (float8_lt(d, dist))
2827  {
2828  dist = d;
2829  if (result != NULL)
2830  *result = point;
2831  }
2832 
2833  /* The closest point can still be one of the endpoints, so we test them. */
2834  d = lseg_closept_point(NULL, to_lseg, &on_lseg->p[0]);
2835  if (float8_lt(d, dist))
2836  {
2837  dist = d;
2838  if (result != NULL)
2839  *result = on_lseg->p[0];
2840  }
2841  d = lseg_closept_point(NULL, to_lseg, &on_lseg->p[1]);
2842  if (float8_lt(d, dist))
2843  {
2844  dist = d;
2845  if (result != NULL)
2846  *result = on_lseg->p[1];
2847  }
2848 
2849  return dist;
2850 }
2851 
2852 Datum
2854 {
2855  LSEG *l1 = PG_GETARG_LSEG_P(0);
2856  LSEG *l2 = PG_GETARG_LSEG_P(1);
2857  Point *result;
2858 
2859  if (lseg_sl(l1) == lseg_sl(l2))
2860  PG_RETURN_NULL();
2861 
2862  result = (Point *) palloc(sizeof(Point));
2863 
2864  if (isnan(lseg_closept_lseg(result, l2, l1)))
2865  PG_RETURN_NULL();
2866 
2867  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
2878 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  if (box_contain_point(box, pt))
2887  {
2888  if (result != NULL)
2889  *result = *pt;
2890 
2891  return 0.0;
2892  }
2893 
2894  /* pairwise check lseg distances */
2895  point.x = box->low.x;
2896  point.y = box->high.y;
2897  statlseg_construct(&lseg, &box->low, &point);
2898  dist = lseg_closept_point(result, &lseg, pt);
2899 
2900  statlseg_construct(&lseg, &box->high, &point);
2901  d = lseg_closept_point(&closept, &lseg, pt);
2902  if (float8_lt(d, dist))
2903  {
2904  dist = d;
2905  if (result != NULL)
2906  *result = closept;
2907  }
2908 
2909  point.x = box->high.x;
2910  point.y = box->low.y;
2911  statlseg_construct(&lseg, &box->low, &point);
2912  d = lseg_closept_point(&closept, &lseg, pt);
2913  if (float8_lt(d, dist))
2914  {
2915  dist = d;
2916  if (result != NULL)
2917  *result = closept;
2918  }
2919 
2920  statlseg_construct(&lseg, &box->high, &point);
2921  d = lseg_closept_point(&closept, &lseg, pt);
2922  if (float8_lt(d, dist))
2923  {
2924  dist = d;
2925  if (result != NULL)
2926  *result = closept;
2927  }
2928 
2929  return dist;
2930 }
2931 
2932 Datum
2934 {
2935  Point *pt = PG_GETARG_POINT_P(0);
2936  BOX *box = PG_GETARG_BOX_P(1);
2937  Point *result;
2938 
2939  result = (Point *) palloc(sizeof(Point));
2940 
2941  if (isnan(box_closept_point(result, box, pt)))
2942  PG_RETURN_NULL();
2943 
2944  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 lseg_closept_line(Point *result, LSEG *lseg, LINE *line)
2961 {
2962  float8 dist1,
2963  dist2;
2964 
2965  if (lseg_interpt_line(result, lseg, line))
2966  return 0.0;
2967 
2968  dist1 = line_closept_point(NULL, line, &lseg->p[0]);
2969  dist2 = line_closept_point(NULL, line, &lseg->p[1]);
2970 
2971  if (dist1 < dist2)
2972  {
2973  if (result != NULL)
2974  *result = lseg->p[0];
2975 
2976  return dist1;
2977  }
2978  else
2979  {
2980  if (result != NULL)
2981  *result = lseg->p[1];
2982 
2983  return dist2;
2984  }
2985 }
2986 
2987 Datum
2989 {
2990  LINE *line = PG_GETARG_LINE_P(0);
2991  LSEG *lseg = PG_GETARG_LSEG_P(1);
2992  Point *result;
2993 
2994  if (lseg_sl(lseg) == line_sl(line))
2995  PG_RETURN_NULL();
2996 
2997  result = (Point *) palloc(sizeof(Point));
2998 
2999  if (isnan(lseg_closept_line(result, lseg, line)))
3000  PG_RETURN_NULL();
3001 
3002  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
3013 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  if (box_interpt_lseg(result, box, lseg))
3022  return 0.0;
3023 
3024  /* pairwise check lseg distances */
3025  point.x = box->low.x;
3026  point.y = box->high.y;
3027  statlseg_construct(&bseg, &box->low, &point);
3028  dist = lseg_closept_lseg(result, &bseg, lseg);
3029 
3030  statlseg_construct(&bseg, &box->high, &point);
3031  d = lseg_closept_lseg(&closept, &bseg, lseg);
3032  if (float8_lt(d, dist))
3033  {
3034  dist = d;
3035  if (result != NULL)
3036  *result = closept;
3037  }
3038 
3039  point.x = box->high.x;
3040  point.y = box->low.y;
3041  statlseg_construct(&bseg, &box->low, &point);
3042  d = lseg_closept_lseg(&closept, &bseg, lseg);
3043  if (float8_lt(d, dist))
3044  {
3045  dist = d;
3046  if (result != NULL)
3047  *result = closept;
3048  }
3049 
3050  statlseg_construct(&bseg, &box->high, &point);
3051  d = lseg_closept_lseg(&closept, &bseg, lseg);
3052  if (float8_lt(d, dist))
3053  {
3054  dist = d;
3055  if (result != NULL)
3056  *result = closept;
3057  }
3058 
3059  return dist;
3060 }
3061 
3062 Datum
3064 {
3065  LSEG *lseg = PG_GETARG_LSEG_P(0);
3066  BOX *box = PG_GETARG_BOX_P(1);
3067  Point *result;
3068 
3069  result = (Point *) palloc(sizeof(Point));
3070 
3071  if (isnan(box_closept_lseg(result, box, lseg)))
3072  PG_RETURN_NULL();
3073 
3074  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
3088 {
3089  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
3096 {
3097  Point *pt = PG_GETARG_POINT_P(0);
3098  LINE *line = PG_GETARG_LINE_P(1);
3099 
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
3110 {
3111  return FPeq(point_dt(pt, &lseg->p[0]) +
3112  point_dt(pt, &lseg->p[1]),
3113  point_dt(&lseg->p[0], &lseg->p[1]));
3114 }
3115 
3116 Datum
3118 {
3119  Point *pt = PG_GETARG_POINT_P(0);
3120  LSEG *lseg = PG_GETARG_LSEG_P(1);
3121 
3123 }
3124 
3125 
3126 /*
3127  * Check whether the point is in the box or on its border
3128  */
3129 static bool
3131 {
3132  return box->high.x >= point->x && box->low.x <= point->x &&
3133  box->high.y >= point->y && box->low.y <= point->y;
3134 }
3135 
3136 Datum
3138 {
3139  Point *pt = PG_GETARG_POINT_P(0);
3140  BOX *box = PG_GETARG_BOX_P(1);
3141 
3143 }
3144 
3145 Datum
3147 {
3148  BOX *box = PG_GETARG_BOX_P(0);
3149  Point *pt = PG_GETARG_POINT_P(1);
3150 
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
3167 {
3168  Point *pt = PG_GETARG_POINT_P(0);
3169  PATH *path = PG_GETARG_PATH_P(1);
3170  int i,
3171  n;
3172  float8 a,
3173  b;
3174 
3175  /*-- OPEN --*/
3176  if (!path->closed)
3177  {
3178  n = path->npts - 1;
3179  a = point_dt(pt, &path->p[0]);
3180  for (i = 0; i < n; i++)
3181  {
3182  b = point_dt(pt, &path->p[i + 1]);
3183  if (FPeq(float8_pl(a, b), point_dt(&path->p[i], &path->p[i + 1])))
3184  PG_RETURN_BOOL(true);
3185  a = b;
3186  }
3187  PG_RETURN_BOOL(false);
3188  }
3189 
3190  /*-- CLOSED --*/
3191  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
3202 {
3203  LSEG *lseg = PG_GETARG_LSEG_P(0);
3204  LINE *line = PG_GETARG_LINE_P(1);
3205 
3206  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
3218 {
3219  return box_contain_point(box, &lseg->p[0]) &&
3220  box_contain_point(box, &lseg->p[1]);
3221 }
3222 
3223 Datum
3225 {
3226  LSEG *lseg = PG_GETARG_LSEG_P(0);
3227  BOX *box = PG_GETARG_BOX_P(1);
3228 
3229  PG_RETURN_BOOL(box_contain_lseg(box, lseg));
3230 }
3231 
3232 /*---------------------------------------------------------------------
3233  * inter_
3234  * Whether one object intersects another.
3235  *-------------------------------------------------------------------*/
3236 
3237 Datum
3239 {
3240  LSEG *lseg = PG_GETARG_LSEG_P(0);
3241  LINE *line = PG_GETARG_LINE_P(1);
3242 
3243  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 box_interpt_lseg(Point *result, BOX *box, LSEG *lseg)
3264 {
3265  BOX lbox;
3266  LSEG bseg;
3267  Point point;
3268 
3269  lbox.low.x = float8_min(lseg->p[0].x, lseg->p[1].x);
3270  lbox.low.y = float8_min(lseg->p[0].y, lseg->p[1].y);
3271  lbox.high.x = float8_max(lseg->p[0].x, lseg->p[1].x);
3272  lbox.high.y = float8_max(lseg->p[0].y, lseg->p[1].y);
3273 
3274  /* nothing close to overlap? then not going to intersect */
3275  if (!box_ov(&lbox, box))
3276  return false;
3277 
3278  if (result != NULL)
3279  {
3280  box_cn(&point, box);
3281  lseg_closept_point(result, lseg, &point);
3282  }
3283 
3284  /* an endpoint of segment is inside box? then clearly intersects */
3285  if (box_contain_point(box, &lseg->p[0]) ||
3286  box_contain_point(box, &lseg->p[1]))
3287  return true;
3288 
3289  /* pairwise check lseg intersections */
3290  point.x = box->low.x;
3291  point.y = box->high.y;
3292  statlseg_construct(&bseg, &box->low, &point);
3293  if (lseg_interpt_lseg(NULL, &bseg, lseg))
3294  return true;
3295 
3296  statlseg_construct(&bseg, &box->high, &point);
3297  if (lseg_interpt_lseg(NULL, &bseg, lseg))
3298  return true;
3299 
3300  point.x = box->high.x;
3301  point.y = box->low.y;
3302  statlseg_construct(&bseg, &box->low, &point);
3303  if (lseg_interpt_lseg(NULL, &bseg, lseg))
3304  return true;
3305 
3306  statlseg_construct(&bseg, &box->high, &point);
3307  if (lseg_interpt_lseg(NULL, &bseg, lseg))
3308  return true;
3309 
3310  /* if we dropped through, no two segs intersected */
3311  return false;
3312 }
3313 
3314 Datum
3316 {
3317  LSEG *lseg = PG_GETARG_LSEG_P(0);
3318  BOX *box = PG_GETARG_BOX_P(1);
3319 
3320  PG_RETURN_BOOL(box_interpt_lseg(NULL, box, lseg));
3321 }
3322 
3323 
3324 /* inter_lb()
3325  * Do line and box intersect?
3326  */
3327 Datum
3329 {
3330  LINE *line = PG_GETARG_LINE_P(0);
3331  BOX *box = PG_GETARG_BOX_P(1);
3332  LSEG bseg;
3333  Point p1,
3334  p2;
3335 
3336  /* pairwise check lseg intersections */
3337  p1.x = box->low.x;
3338  p1.y = box->low.y;
3339  p2.x = box->low.x;
3340  p2.y = box->high.y;
3341  statlseg_construct(&bseg, &p1, &p2);
3342  if (lseg_interpt_line(NULL, &bseg, line))
3343  PG_RETURN_BOOL(true);
3344  p1.x = box->high.x;
3345  p1.y = box->high.y;
3346  statlseg_construct(&bseg, &p1, &p2);
3347  if (lseg_interpt_line(NULL, &bseg, line))
3348  PG_RETURN_BOOL(true);
3349  p2.x = box->high.x;
3350  p2.y = box->low.y;
3351  statlseg_construct(&bseg, &p1, &p2);
3352  if (lseg_interpt_line(NULL, &bseg, line))
3353  PG_RETURN_BOOL(true);
3354  p1.x = box->low.x;
3355  p1.y = box->low.y;
3356  statlseg_construct(&bseg, &p1, &p2);
3357  if (lseg_interpt_line(NULL, &bseg, line))
3358  PG_RETURN_BOOL(true);
3359 
3360  /* if we dropped through, no intersection */
3361  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
3377 {
3378  int i;
3379  float8 x1,
3380  y1,
3381  x2,
3382  y2;
3383 
3384  Assert(poly->npts > 0);
3385 
3386  x1 = x2 = poly->p[0].x;
3387  y2 = y1 = poly->p[0].y;
3388  for (i = 1; i < poly->npts; i++)
3389  {
3390  if (float8_lt(poly->p[i].x, x1))
3391  x1 = poly->p[i].x;
3392  if (float8_gt(poly->p[i].x, x2))
3393  x2 = poly->p[i].x;
3394  if (float8_lt(poly->p[i].y, y1))
3395  y1 = poly->p[i].y;
3396  if (float8_gt(poly->p[i].y, y2))
3397  y2 = poly->p[i].y;
3398  }
3399 
3400  poly->boundbox.low.x = x1;
3401  poly->boundbox.high.x = x2;
3402  poly->boundbox.low.y = y1;
3403  poly->boundbox.high.y = y2;
3404 }
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
3416 {
3417  char *str = PG_GETARG_CSTRING(0);
3418  Node *escontext = fcinfo->context;
3419  POLYGON *poly;
3420  int npts;
3421  int size;
3422  int base_size;
3423  bool isopen;
3424 
3425  if ((npts = pair_count(str, ',')) <= 0)
3426  ereturn(escontext, (Datum) 0,
3427  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
3428  errmsg("invalid input syntax for type %s: \"%s\"",
3429  "polygon", str)));
3430 
3431  base_size = sizeof(poly->p[0]) * npts;
3432  size = offsetof(POLYGON, p) + base_size;
3433 
3434  /* Check for integer overflow */
3435  if (base_size / npts != sizeof(poly->p[0]) || size <= base_size)
3436  ereturn(escontext, (Datum) 0,
3437  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
3438  errmsg("too many points requested")));
3439 
3440  poly = (POLYGON *) palloc0(size); /* zero any holes */
3441 
3442  SET_VARSIZE(poly, size);
3443  poly->npts = npts;
3444 
3445  if (!path_decode(str, false, npts, &(poly->p[0]), &isopen, NULL, "polygon",
3446  str, escontext))
3447  PG_RETURN_NULL();
3448 
3449  make_bound_box(poly);
3450 
3451  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
3460 {
3461  POLYGON *poly = PG_GETARG_POLYGON_P(0);
3462 
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
3476 {
3478  POLYGON *poly;
3479  int32 npts;
3480  int32 i;
3481  int size;
3482 
3483  npts = pq_getmsgint(buf, sizeof(int32));
3484  if (npts <= 0 || npts >= (int32) ((INT_MAX - offsetof(POLYGON, p)) / sizeof(Point)))
3485  ereport(ERROR,
3486  (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
3487  errmsg("invalid number of points in external \"polygon\" value")));
3488 
3489  size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * npts;
3490  poly = (POLYGON *) palloc0(size); /* zero any holes */
3491 
3492  SET_VARSIZE(poly, size);
3493  poly->npts = npts;
3494 
3495  for (i = 0; i < npts; i++)
3496  {
3497  poly->p[i].x = pq_getmsgfloat8(buf);
3498  poly->p[i].y = pq_getmsgfloat8(buf);
3499  }
3500 
3501  make_bound_box(poly);
3502 
3503  PG_RETURN_POLYGON_P(poly);
3504 }
3505 
3506 /*
3507  * poly_send - converts polygon to binary format
3508  */
3509 Datum
3511 {
3512  POLYGON *poly = PG_GETARG_POLYGON_P(0);
3514  int32 i;
3515 
3516  pq_begintypsend(&buf);
3517  pq_sendint32(&buf, poly->npts);
3518  for (i = 0; i < poly->npts; i++)
3519  {
3520  pq_sendfloat8(&buf, poly->p[i].x);
3521  pq_sendfloat8(&buf, poly->p[i].y);
3522  }
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
3534 {
3535  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3536  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3537  bool result;
3538 
3539  result = polya->boundbox.high.x < polyb->boundbox.low.x;
3540 
3541  /*
3542  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3543  */
3544  PG_FREE_IF_COPY(polya, 0);
3545  PG_FREE_IF_COPY(polyb, 1);
3546 
3547  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
3557 {
3558  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3559  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3560  bool result;
3561 
3562  result = polya->boundbox.high.x <= polyb->boundbox.high.x;
3563 
3564  /*
3565  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3566  */
3567  PG_FREE_IF_COPY(polya, 0);
3568  PG_FREE_IF_COPY(polyb, 1);
3569 
3570  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
3580 {
3581  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3582  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3583  bool result;
3584 
3585  result = polya->boundbox.low.x > polyb->boundbox.high.x;
3586 
3587  /*
3588  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3589  */
3590  PG_FREE_IF_COPY(polya, 0);
3591  PG_FREE_IF_COPY(polyb, 1);
3592 
3593  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
3603 {
3604  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3605  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3606  bool result;
3607 
3608  result = polya->boundbox.low.x >= polyb->boundbox.low.x;
3609 
3610  /*
3611  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3612  */
3613  PG_FREE_IF_COPY(polya, 0);
3614  PG_FREE_IF_COPY(polyb, 1);
3615 
3616  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
3626 {
3627  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3628  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3629  bool result;
3630 
3631  result = polya->boundbox.high.y < polyb->boundbox.low.y;
3632 
3633  /*
3634  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3635  */
3636  PG_FREE_IF_COPY(polya, 0);
3637  PG_FREE_IF_COPY(polyb, 1);
3638 
3639  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
3649 {
3650  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3651  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3652  bool result;
3653 
3654  result = polya->boundbox.high.y <= polyb->boundbox.high.y;
3655 
3656  /*
3657  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3658  */
3659  PG_FREE_IF_COPY(polya, 0);
3660  PG_FREE_IF_COPY(polyb, 1);
3661 
3662  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
3672 {
3673  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3674  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3675  bool result;
3676 
3677  result = polya->boundbox.low.y > polyb->boundbox.high.y;
3678 
3679  /*
3680  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3681  */
3682  PG_FREE_IF_COPY(polya, 0);
3683  PG_FREE_IF_COPY(polyb, 1);
3684 
3685  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
3695 {
3696  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3697  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3698  bool result;
3699 
3700  result = polya->boundbox.low.y >= polyb->boundbox.low.y;
3701 
3702  /*
3703  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3704  */
3705  PG_FREE_IF_COPY(polya, 0);
3706  PG_FREE_IF_COPY(polyb, 1);
3707 
3708  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
3721 {
3722  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3723  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3724  bool result;
3725 
3726  if (polya->npts != polyb->npts)
3727  result = false;
3728  else
3729  result = plist_same(polya->npts, polya->p, polyb->p);
3730 
3731  /*
3732  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3733  */
3734  PG_FREE_IF_COPY(polya, 0);
3735  PG_FREE_IF_COPY(polyb, 1);
3736 
3737  PG_RETURN_BOOL(result);
3738 }
3739 
3740 /*-----------------------------------------------------------------
3741  * Determine if polygon A overlaps polygon B
3742  *-----------------------------------------------------------------*/
3743 static bool
3745 {
3746  bool result;
3747 
3748  Assert(polya->npts > 0 && polyb->npts > 0);
3749 
3750  /* Quick check by bounding box */
3751  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  */
3758  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  sa.p[0] = polya->p[polya->npts - 1];
3767  result = false;
3768 
3769  for (ia = 0; ia < polya->npts && !result; ia++)
3770  {
3771  /* Second point of polya's edge is a current one */
3772  sa.p[1] = polya->p[ia];
3773 
3774  /* Init first of polyb's edge with last point */
3775  sb.p[0] = polyb->p[polyb->npts - 1];
3776 
3777  for (ib = 0; ib < polyb->npts && !result; ib++)
3778  {
3779  sb.p[1] = polyb->p[ib];
3780  result = lseg_interpt_lseg(NULL, &sa, &sb);
3781  sb.p[0] = sb.p[1];
3782  }
3783 
3784  /*
3785  * move current endpoint to the first point of next edge
3786  */
3787  sa.p[0] = sa.p[1];
3788  }
3789 
3790  if (!result)
3791  {
3792  result = (point_inside(polya->p, polyb->npts, polyb->p) ||
3793  point_inside(polyb->p, polya->npts, polya->p));
3794  }
3795  }
3796 
3797  return result;
3798 }
3799 
3800 Datum
3802 {
3803  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3804  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3805  bool result;
3806 
3807  result = poly_overlap_internal(polya, polyb);
3808 
3809  /*
3810  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3811  */
3812  PG_FREE_IF_COPY(polya, 0);
3813  PG_FREE_IF_COPY(polyb, 1);
3814 
3815  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
3831 {
3832  /* point a is on s, b is not */
3833  LSEG t;
3834 
3835  t.p[0] = *a;
3836  t.p[1] = *b;
3837 
3838  if (point_eq_point(a, s->p))
3839  {
3840  if (lseg_contain_point(&t, s->p + 1))
3841  return lseg_inside_poly(b, s->p + 1, poly, start);
3842  }
3843  else if (point_eq_point(a, s->p + 1))
3844  {
3845  if (lseg_contain_point(&t, s->p))
3846  return lseg_inside_poly(b, s->p, poly, start);
3847  }
3848  else if (lseg_contain_point(&t, s->p))
3849  {
3850  return lseg_inside_poly(b, s->p, poly, start);
3851  }
3852  else if (lseg_contain_point(&t, s->p + 1))
3853  {
3854  return lseg_inside_poly(b, s->p + 1, poly, start);
3855  }
3856 
3857  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
3866 lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
3867 {
3868  LSEG s,
3869  t;
3870  int i;
3871  bool res = true,
3872  intersection = false;
3873 
3874  /* since this function recurses, it could be driven to stack overflow */
3876 
3877  t.p[0] = *a;
3878  t.p[1] = *b;
3879  s.p[0] = poly->p[(start == 0) ? (poly->npts - 1) : (start - 1)];
3880 
3881  for (i = start; i < poly->npts && res; i++)
3882  {
3883  Point interpt;
3884 
3886 
3887  s.p[1] = poly->p[i];
3888 
3889  if (lseg_contain_point(&s, t.p))
3890  {
3891  if (lseg_contain_point(&s, t.p + 1))
3892  return true; /* t is contained by s */
3893 
3894  /* Y-cross */
3895  res = touched_lseg_inside_poly(t.p, t.p + 1, &s, poly, i + 1);
3896  }
3897  else if (lseg_contain_point(&s, t.p + 1))
3898  {
3899  /* Y-cross */
3900  res = touched_lseg_inside_poly(t.p + 1, t.p, &s, poly, i + 1);
3901  }
3902  else if (lseg_interpt_lseg(&interpt, &t, &s))
3903  {
3904  /*
3905  * segments are X-crossing, go to check each subsegment
3906  */
3907 
3908  intersection = true;
3909  res = lseg_inside_poly(t.p, &interpt, poly, i + 1);
3910  if (res)
3911  res = lseg_inside_poly(t.p + 1, &interpt, poly, i + 1);
3912  }
3913 
3914  s.p[0] = s.p[1];
3915  }
3916 
3917  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  */
3925  p.x = float8_div(float8_pl(t.p[0].x, t.p[1].x), 2.0);
3926  p.y = float8_div(float8_pl(t.p[0].y, t.p[1].y), 2.0);
3927 
3928  res = point_inside(&p, poly->npts, poly->p);
3929  }
3930 
3931  return res;
3932 }
3933 
3934 /*
3935  * Check whether the first polygon contains the second
3936  */
3937 static bool
3938 poly_contain_poly(POLYGON *contains_poly, POLYGON *contained_poly)
3939 {
3940  int i;
3941  LSEG s;
3942 
3943  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  if (!box_contain_box(&contains_poly->boundbox, &contained_poly->boundbox))
3950  return false;
3951 
3952  s.p[0] = contained_poly->p[contained_poly->npts - 1];
3953 
3954  for (i = 0; i < contained_poly->npts; i++)
3955  {
3956  s.p[1] = contained_poly->p[i];
3957  if (!lseg_inside_poly(s.p, s.p + 1, contains_poly, 0))
3958  return false;
3959  s.p[0] = s.p[1];
3960  }
3961 
3962  return true;
3963 }
3964 
3965 Datum
3967 {
3968  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3969  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3970  bool result;
3971 
3972  result = poly_contain_poly(polya, polyb);
3973 
3974  /*
3975  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3976  */
3977  PG_FREE_IF_COPY(polya, 0);
3978  PG_FREE_IF_COPY(polyb, 1);
3979 
3980  PG_RETURN_BOOL(result);
3981 }
3982 
3983 
3984 /*-----------------------------------------------------------------
3985  * Determine if polygon A is contained by polygon B
3986  *-----------------------------------------------------------------*/
3987 Datum
3989 {
3990  POLYGON *polya = PG_GETARG_POLYGON_P(0);
3991  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
3992  bool result;
3993 
3994  /* Just switch the arguments and pass it off to poly_contain */
3995  result = poly_contain_poly(polyb, polya);
3996 
3997  /*
3998  * Avoid leaking memory for toasted inputs ... needed for rtree indexes
3999  */
4000  PG_FREE_IF_COPY(polya, 0);
4001  PG_FREE_IF_COPY(polyb, 1);
4002 
4003  PG_RETURN_BOOL(result);
4004 }
4005 
4006 
4007 Datum
4009 {
4010  POLYGON *poly = PG_GETARG_POLYGON_P(0);
4011  Point *p = PG_GETARG_POINT_P(1);
4012 
4013  PG_RETURN_BOOL(point_inside(p, poly->npts, poly->p) != 0);
4014 }
4015 
4016 Datum
4018 {
4019  Point *p = PG_GETARG_POINT_P(0);
4020  POLYGON *poly = PG_GETARG_POLYGON_P(1);
4021 
4022  PG_RETURN_BOOL(point_inside(p, poly->npts, poly->p) != 0);
4023 }
4024 
4025 
4026 Datum
4028 {
4029  POLYGON *polya = PG_GETARG_POLYGON_P(0);
4030  POLYGON *polyb = PG_GETARG_POLYGON_P(1);
4031  float8 min = 0.0; /* initialize to keep compiler quiet */
4032  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  if (poly_overlap_internal(polya, polyb))
4045  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  for (i = 0; i < polya->npts; i++)
4053  {
4054  int iprev;
4055 
4056  if (i > 0)
4057  iprev = i - 1;
4058  else
4059  iprev = polya->npts - 1;
4060 
4061  for (j = 0; j < polyb->npts; j++)
4062  {
4063  int jprev;
4064 
4065  if (j > 0)
4066  jprev = j - 1;
4067  else
4068  jprev = polyb->npts - 1;
4069 
4070  statlseg_construct(&seg1, &polya->p[iprev], &polya->p[i]);
4071  statlseg_construct(&seg2, &polyb->p[jprev], &polyb->p[j]);
4072 
4073  tmp = lseg_closept_lseg(NULL, &seg1, &seg2);
4074  if (!have_min || float8_lt(tmp, min))
4075  {
4076  min = tmp;
4077  have_min = true;
4078  }
4079  }
4080  }
4081 
4082  if (!have_min)
4083  PG_RETURN_NULL();
4084 
4085  PG_RETURN_FLOAT8(min);
4086 }
4087 
4088 
4089 /***********************************************************************
4090  **
4091  ** Routines for 2D points.
4092  **
4093  ***********************************************************************/
4094 
4095 Datum
4097 {
4098  float8 x = PG_GETARG_FLOAT8(0);
4099  float8 y = PG_GETARG_FLOAT8(1);
4100  Point *result;
4101 
4102  result = (Point *) palloc(sizeof(Point));
4103 
4104  point_construct(result, x, y);
4105 
4106  PG_RETURN_POINT_P(result);
4107 }
4108 
4109 
4110 static inline void
4111 point_add_point(Point *result, Point *pt1, Point *pt2)
4112 {
4113  point_construct(result,
4114  float8_pl(pt1->x, pt2->x),
4115  float8_pl(pt1->y, pt2->y));
4116 }
4117 
4118 Datum
4120 {
4121  Point *p1 = PG_GETARG_POINT_P(0);
4122  Point *p2 = PG_GETARG_POINT_P(1);
4123  Point *result;
4124 
4125  result = (Point *) palloc(sizeof(Point));
4126 
4127  point_add_point(result, p1, p2);
4128 
4129  PG_RETURN_POINT_P(result);
4130 }
4131 
4132 
4133 static inline void
4134 point_sub_point(Point *result, Point *pt1, Point *pt2)
4135 {
4136  point_construct(result,
4137  float8_mi(pt1->x, pt2->x),
4138  float8_mi(pt1->y, pt2->y));
4139 }
4140 
4141 Datum
4143 {
4144  Point *p1 = PG_GETARG_POINT_P(0);
4145  Point *p2 = PG_GETARG_POINT_P(1);
4146  Point *result;
4147 
4148  result = (Point *) palloc(sizeof(Point));
4149 
4150  point_sub_point(result, p1, p2);
4151 
4152  PG_RETURN_POINT_P(result);
4153 }
4154 
4155 
4156 static inline void
4157 point_mul_point(Point *result, Point *pt1, Point *pt2)
4158 {
4159  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 }
4165 
4166 Datum
4168 {
4169  Point *p1 = PG_GETARG_POINT_P(0);
4170  Point *p2 = PG_GETARG_POINT_P(1);
4171  Point *result;
4172 
4173  result = (Point *) palloc(sizeof(Point));
4174 
4175  point_mul_point(result, p1, p2);
4176 
4177  PG_RETURN_POINT_P(result);
4178 }
4179 
4180 
4181 static inline void
4182 point_div_point(Point *result, Point *pt1, Point *pt2)
4183 {
4184  float8 div;
4185 
4186  div = float8_pl(float8_mul(pt2->x, pt2->x), float8_mul(pt2->y, pt2->y));
4187 
4188  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 }
4194 
4195 Datum
4197 {
4198  Point *p1 = PG_GETARG_POINT_P(0);
4199  Point *p2 = PG_GETARG_POINT_P(1);
4200  Point *result;
4201 
4202  result = (Point *) palloc(sizeof(Point));
4203 
4204  point_div_point(result, p1, p2);
4205 
4206  PG_RETURN_POINT_P(result);
4207 }
4208 
4209 
4210 /***********************************************************************
4211  **
4212  ** Routines for 2D boxes.
4213  **
4214  ***********************************************************************/
4215 
4216 Datum
4218 {
4219  Point *p1 = PG_GETARG_POINT_P(0);
4220  Point *p2 = PG_GETARG_POINT_P(1);
4221  BOX *result;
4222 
4223  result = (BOX *) palloc(sizeof(BOX));
4224 
4225  box_construct(result, p1, p2);
4226 
4227  PG_RETURN_BOX_P(result);
4228 }
4229 
4230 Datum
4232 {
4233  BOX *box = PG_GETARG_BOX_P(0);
4234  Point *p = PG_GETARG_POINT_P(1);
4235  BOX *result;
4236 
4237  result = (BOX *) palloc(sizeof(BOX));
4238 
4239  point_add_point(&result->high, &box->high, p);
4240  point_add_point(&result->low, &box->low, p);
4241 
4242  PG_RETURN_BOX_P(result);
4243 }
4244 
4245 Datum
4247 {
4248  BOX *box = PG_GETARG_BOX_P(0);
4249  Point *p = PG_GETARG_POINT_P(1);
4250  BOX *result;
4251 
4252  result = (BOX *) palloc(sizeof(BOX));
4253 
4254  point_sub_point(&result->high, &box->high, p);
4255  point_sub_point(&result->low, &box->low, p);
4256 
4257  PG_RETURN_BOX_P(result);
4258 }
4259 
4260 Datum
4262 {
4263  BOX *box = PG_GETARG_BOX_P(0);
4264  Point *p = PG_GETARG_POINT_P(1);
4265  BOX *result;
4266  Point high,
4267  low;
4268 
4269  result = (BOX *) palloc(sizeof(BOX));
4270 
4271  point_mul_point(&high, &box->high, p);
4272  point_mul_point(&low, &box->low, p);
4273 
4274  box_construct(result, &high, &low);
4275 
4276  PG_RETURN_BOX_P(result);
4277 }
4278 
4279 Datum
4281 {
4282  BOX *box = PG_GETARG_BOX_P(0);
4283  Point *p = PG_GETARG_POINT_P(1);
4284  BOX *result;
4285  Point high,
4286  low;
4287 
4288  result = (BOX *) palloc(sizeof(BOX));
4289 
4290  point_div_point(&high, &box->high, p);
4291  point_div_point(&low, &box->low, p);
4292 
4293  box_construct(result, &high, &low);
4294 
4295  PG_RETURN_BOX_P(result);
4296 }
4297 
4298 /*
4299  * Convert point to empty box
4300  */
4301 Datum
4303 {
4304  Point *pt = PG_GETARG_POINT_P(0);
4305  BOX *box;
4306 
4307  box = (BOX *) palloc(sizeof(BOX));
4308 
4309  box->high.x = pt->x;
4310  box->low.x = pt->x;
4311  box->high.y = pt->y;
4312  box->low.y = pt->y;
4313 
4314  PG_RETURN_BOX_P(box);
4315 }
4316 
4317 /*
4318  * Smallest bounding box that includes both of the given boxes
4319  */
4320 Datum
4322 {
4323  BOX *box1 = PG_GETARG_BOX_P(0),
4324  *box2 = PG_GETARG_BOX_P(1),
4325  *container;
4326 
4327  container = (BOX *) palloc(sizeof(BOX));
4328 
4329  container->high.x = float8_max(box1->high.x, box2->high.x);
4330  container->low.x = float8_min(box1->low.x, box2->low.x);
4331  container->high.y = float8_max(box1->high.y, box2->high.y);
4332  container->low.y = float8_min(box1->low.y, box2->low.y);
4333 
4334  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
4349 {
4350  PATH *p1 = PG_GETARG_PATH_P(0);
4351  PATH *p2 = PG_GETARG_PATH_P(1);
4352  PATH *result;
4353  int size,
4354  base_size;
4355  int i;
4356 
4357  if (p1->closed || p2->closed)
4358  PG_RETURN_NULL();
4359 
4360  base_size = sizeof(p1->p[0]) * (p1->npts + p2->npts);
4361  size = offsetof(PATH, p) + base_size;
4362 
4363  /* Check for integer overflow */
4364  if (base_size / sizeof(p1->p[0]) != (p1->npts + p2->npts) ||
4365  size <= base_size)
4366  ereport(ERROR,
4367  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
4368  errmsg("too many points requested")));
4369 
4370  result = (PATH *) palloc(size);
4371 
4372  SET_VARSIZE(result, size);
4373  result->npts = (p1->npts + p2->npts);
4374  result->closed = p1->closed;
4375  /* prevent instability in unused pad bytes */
4376  result->dummy = 0;
4377 
4378  for (i = 0; i < p1->npts; i++)
4379  {
4380  result->p[i].x = p1->p[i].x;
4381  result->p[i].y = p1->p[i].y;
4382  }
4383  for (i = 0; i < p2->npts; i++)
4384  {
4385  result->p[i + p1->npts].x = p2->p[i].x;
4386  result->p[i + p1->npts].y = p2->p[i].y;
4387  }
4388 
4389  PG_RETURN_PATH_P(result);
4390 }
4391 
4392 /* path_add_pt()
4393  * Translation operators.
4394  */
4395 Datum
4397 {
4398  PATH *path = PG_GETARG_PATH_P_COPY(0);
4399  Point *point = PG_GETARG_POINT_P(1);
4400  int i;
4401 
4402  for (i = 0; i < path->npts; i++)
4403  point_add_point(&path->p[i], &path->p[i], point);
4404 
4405  PG_RETURN_PATH_P(path);
4406 }
4407 
4408 Datum
4410 {
4411  PATH *path = PG_GETARG_PATH_P_COPY(0);
4412  Point *point = PG_GETARG_POINT_P(1);
4413  int i;
4414 
4415  for (i = 0; i < path->npts; i++)
4416  point_sub_point(&path->p[i], &path->p[i], point);
4417 
4418  PG_RETURN_PATH_P(path);
4419 }
4420 
4421 /* path_mul_pt()
4422  * Rotation and scaling operators.
4423  */
4424 Datum
4426 {
4427  PATH *path = PG_GETARG_PATH_P_COPY(0);
4428  Point *point = PG_GETARG_POINT_P(1);
4429  int i;
4430 
4431  for (i = 0; i < path->npts; i++)
4432  point_mul_point(&path->p[i], &path->p[i], point);
4433 
4434  PG_RETURN_PATH_P(path);
4435 }
4436 
4437 Datum
4439 {
4440  PATH *path = PG_GETARG_PATH_P_COPY(0);
4441  Point *point = PG_GETARG_POINT_P(1);
4442  int i;
4443 
4444  for (i = 0; i < path->npts; i++)
4445  point_div_point(&path->p[i], &path->p[i], point);
4446 
4447  PG_RETURN_PATH_P(path);
4448 }
4449 
4450 
4451 Datum
4453 {
4454  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 ... */
4460  if (!path->closed)
4461  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  */
4469  size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * path->npts;
4470  poly = (POLYGON *) palloc(size);
4471 
4472  SET_VARSIZE(poly, size);
4473  poly->npts = path->npts;
4474 
4475  for (i = 0; i < path->npts; i++)
4476  {
4477  poly->p[i].x = path->p[i].x;
4478  poly->p[i].y = path->p[i].y;
4479  }
4480 
4481  make_bound_box(poly);
4482 
4483  PG_RETURN_POLYGON_P(poly);
4484 }
4485 
4486 
4487 /***********************************************************************
4488  **
4489  ** Routines for 2D polygons.
4490  **
4491  ***********************************************************************/
4492 
4493 Datum
4495 {
4496  POLYGON *poly = PG_GETARG_POLYGON_P(0);
4497 
4498  PG_RETURN_INT32(poly->npts);
4499 }
4500 
4501 
4502 Datum
4504 {
4505  POLYGON *poly = PG_GETARG_POLYGON_P(0);
4506  Point *result;
4507  CIRCLE circle;
4508 
4509  result = (Point *) palloc(sizeof(Point));
4510 
4511  poly_to_circle(&circle, poly);
4512  *result = circle.center;
4513 
4514  PG_RETURN_POINT_P(result);
4515 }
4516 
4517 
4518 Datum
4520 {
4521  POLYGON *poly = PG_GETARG_POLYGON_P(0);
4522  BOX *box;
4523 
4524  box = (BOX *) palloc(sizeof(BOX));
4525  *box = poly->boundbox;
4526 
4527  PG_RETURN_BOX_P(box);
4528 }
4529 
4530 
4531 /* box_poly()
4532  * Convert a box to a polygon.
4533  */
4534 Datum
4536 {
4537  BOX *box = PG_GETARG_BOX_P(0);
4538  POLYGON *poly;
4539  int size;
4540 
4541  /* map four corners of the box to a polygon */
4542  size = offsetof(POLYGON, p) + sizeof(poly->p[0]) * 4;
4543  poly = (POLYGON *) palloc(size);
4544 
4545  SET_VARSIZE(poly, size);
4546  poly->npts = 4;
4547 
4548  poly->p[0].x = box->low.x;
4549  poly->p[0].y = box->low.y;
4550  poly->p[1].x = box->low.x;
4551  poly->p[1].y = box->high.y;
4552  poly->p[2].x = box->high.x;
4553  poly->p[2].y = box->high.y;
4554  poly->p[3].x = box->high.x;
4555  poly->p[3].y = box->low.y;
4556 
4557  box_construct(&poly->boundbox, &box->high, &box->low);
4558 
4559  PG_RETURN_POLYGON_P(poly);
4560 }
4561 
4562 
4563 Datum
4565 {
4566  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  */
4575  size = offsetof(PATH, p) + sizeof(path->p[0]) * poly->npts;
4576  path = (PATH *) palloc(size);
4577 
4578  SET_VARSIZE(path, size);
4579  path->npts = poly->npts;
4580  path->closed = true;
4581  /* prevent instability in unused pad bytes */
4582  path->dummy = 0;
4583 
4584  for (i = 0; i < poly->npts; i++)
4585  {
4586  path->p[i].x = poly->p[i].x;
4587  path->p[i].y = poly->p[i].y;
4588  }
4589 
4590  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
4612 {
4613  char *str = PG_GETARG_CSTRING(0);
4614  Node *escontext = fcinfo->context;
4615  CIRCLE *circle = (CIRCLE *) palloc(sizeof(CIRCLE));
4616  char *s,
4617  *cp;
4618  int depth = 0;
4619 
4620  s = str;
4621  while (isspace((unsigned char) *s))
4622  s++;
4623  if (*s == LDELIM_C)
4624  depth++, s++;
4625  else if (*s == LDELIM)
4626  {
4627  /* If there are two left parens, consume the first one */
4628  cp = (s + 1);
4629  while (isspace((unsigned char) *cp))
4630  cp++;
4631  if (*cp == LDELIM)
4632  depth++, s = cp;
4633  }
4634 
4635  /* pair_decode will consume parens around the pair, if any */
4636  if (!pair_decode(s, &circle->center.x, &circle->center.y, &s, "circle", str,
4637  escontext))
4638  PG_RETURN_NULL();
4639 
4640  if (*s == DELIM)
4641  s++;
4642 
4643  if (!single_decode(s, &circle->radius, &s, "circle", str, escontext))
4644  PG_RETURN_NULL();
4645 
4646  /* We have to accept NaN. */
4647  if (circle->radius < 0.0)
4648  ereturn(escontext, (Datum) 0,
4649  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
4650  errmsg("invalid input syntax for type %s: \"%s\"",
4651  "circle", str)));
4652 
4653  while (depth > 0)
4654  {
4655  if ((*s == RDELIM) || ((*s == RDELIM_C) && (depth == 1)))
4656  {
4657  depth--;
4658  s++;
4659  while (isspace((unsigned char) *s))
4660  s++;
4661  }
4662  else
4663  ereturn(escontext, (Datum) 0,
4664  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
4665  errmsg("invalid input syntax for type %s: \"%s\"",
4666  "circle", str)));
4667  }
4668 
4669  if (*s != '\0')
4670  ereturn(escontext, (Datum) 0,
4671  (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
4672  errmsg("invalid input syntax for type %s: \"%s\"",
4673  "circle", str)));
4674 
4675  PG_RETURN_CIRCLE_P(circle);
4676 }
4677 
4678 /* circle_out - convert a circle to external form.
4679  */
4680 Datum
4682 {
4683  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
4685 
4686  initStringInfo(&str);
4687 
4690  pair_encode(circle->center.x, circle->center.y, &str);
4693  single_encode(circle->radius, &str);
4695 
4696  PG_RETURN_CSTRING(str.data);
4697 }
4698 
4699 /*
4700  * circle_recv - converts external binary format to circle
4701  */
4702 Datum
4704 {
4706  CIRCLE *circle;
4707 
4708  circle = (CIRCLE *) palloc(sizeof(CIRCLE));
4709 
4710  circle->center.x = pq_getmsgfloat8(buf);
4711  circle->center.y = pq_getmsgfloat8(buf);
4712  circle->radius = pq_getmsgfloat8(buf);
4713 
4714  /* We have to accept NaN. */
4715  if (circle->radius < 0.0)
4716  ereport(ERROR,
4717  (errcode(ERRCODE_INVALID_BINARY_REPRESENTATION),
4718  errmsg("invalid radius in external \"circle\" value")));
4719 
4720  PG_RETURN_CIRCLE_P(circle);
4721 }
4722 
4723 /*
4724  * circle_send - converts circle to binary format
4725  */
4726 Datum
4728 {
4729  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
4731 
4732  pq_begintypsend(&buf);
4733  pq_sendfloat8(&buf, circle->center.x);
4734  pq_sendfloat8(&buf, circle->center.y);
4735  pq_sendfloat8(&buf, circle->radius);
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
4752 {
4753  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4754  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4755 
4756  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
4765 {
4766  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4767  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4768 
4769  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
4778 {
4779  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4780  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4781 
4782  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
4790 {
4791  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4792  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4793 
4794  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
4802 {
4803  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4804  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4805 
4806  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
4815 {
4816  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4817  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4818 
4819  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
4827 {
4828  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4829  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4830 
4831  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
4839 {
4840  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4841  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4842 
4843  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
4852 {
4853  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4854  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4855 
4856  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
4864 {
4865  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4866  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4867 
4868  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
4877 {
4878  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4879  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4880 
4881  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
4890 {
4891  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4892  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4893 
4894  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
4904 {
4905  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4906  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4907 
4908  PG_RETURN_BOOL(FPeq(circle_ar(circle1), circle_ar(circle2)));
4909 }
4910 
4911 Datum
4913 {
4914  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4915  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4916 
4917  PG_RETURN_BOOL(FPne(circle_ar(circle1), circle_ar(circle2)));
4918 }
4919 
4920 Datum
4922 {
4923  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4924  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4925 
4926  PG_RETURN_BOOL(FPlt(circle_ar(circle1), circle_ar(circle2)));
4927 }
4928 
4929 Datum
4931 {
4932  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4933  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4934 
4935  PG_RETURN_BOOL(FPgt(circle_ar(circle1), circle_ar(circle2)));
4936 }
4937 
4938 Datum
4940 {
4941  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4942  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4943 
4944  PG_RETURN_BOOL(FPle(circle_ar(circle1), circle_ar(circle2)));
4945 }
4946 
4947 Datum
4949 {
4950  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
4951  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
4952 
4953  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
4966 {
4967  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
4968  Point *point = PG_GETARG_POINT_P(1);
4969  CIRCLE *result;
4970 
4971  result = (CIRCLE *) palloc(sizeof(CIRCLE));
4972 
4973  point_add_point(&result->center, &circle->center, point);
4974  result->radius = circle->radius;
4975 
4976  PG_RETURN_CIRCLE_P(result);
4977 }
4978 
4979 Datum
4981 {
4982  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
4983  Point *point = PG_GETARG_POINT_P(1);
4984  CIRCLE *result;
4985 
4986  result = (CIRCLE *) palloc(sizeof(CIRCLE));
4987 
4988  point_sub_point(&result->center, &circle->center, point);
4989  result->radius = circle->radius;
4990 
4991  PG_RETURN_CIRCLE_P(result);
4992 }
4993 
4994 
4995 /* circle_mul_pt()
4996  * Rotation and scaling operators.
4997  */
4998 Datum
5000 {
5001  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5002  Point *point = PG_GETARG_POINT_P(1);
5003  CIRCLE *result;
5004 
5005  result = (CIRCLE *) palloc(sizeof(CIRCLE));
5006 
5007  point_mul_point(&result->center, &circle->center, point);
5008  result->radius = float8_mul(circle->radius, HYPOT(point->x, point->y));
5009 
5010  PG_RETURN_CIRCLE_P(result);
5011 }
5012 
5013 Datum
5015 {
5016  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5017  Point *point = PG_GETARG_POINT_P(1);
5018  CIRCLE *result;
5019 
5020  result = (CIRCLE *) palloc(sizeof(CIRCLE));
5021 
5022  point_div_point(&result->center, &circle->center, point);
5023  result->radius = float8_div(circle->radius, HYPOT(point->x, point->y));
5024 
5025  PG_RETURN_CIRCLE_P(result);
5026 }
5027 
5028 
5029 /* circle_area - returns the area of the circle.
5030  */
5031 Datum
5033 {
5034  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5035 
5036  PG_RETURN_FLOAT8(circle_ar(circle));
5037 }
5038 
5039 
5040 /* circle_diameter - returns the diameter of the circle.
5041  */
5042 Datum
5044 {
5045  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5046 
5047  PG_RETURN_FLOAT8(float8_mul(circle->radius, 2.0));
5048 }
5049 
5050 
5051 /* circle_radius - returns the radius of the circle.
5052  */
5053 Datum
5055 {
5056  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5057 
5058  PG_RETURN_FLOAT8(circle->radius);
5059 }
5060 
5061 
5062 /* circle_distance - returns the distance between
5063  * two circles.
5064  */
5065 Datum
5067 {
5068  CIRCLE *circle1 = PG_GETARG_CIRCLE_P(0);
5069  CIRCLE *circle2 = PG_GETARG_CIRCLE_P(1);
5070  float8 result;
5071 
5072  result = float8_mi(point_dt(&circle1->center, &circle2->center),
5073  float8_pl(circle1->radius, circle2->radius));
5074  if (result < 0.0)
5075  result = 0.0;
5076 
5077  PG_RETURN_FLOAT8(result);
5078 }
5079 
5080 
5081 Datum
5083 {
5084  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5085  Point *point = PG_GETARG_POINT_P(1);
5086  float8 d;
5087 
5088  d = point_dt(&circle->center, point);
5089  PG_RETURN_BOOL(d <= circle->radius);
5090 }
5091 
5092 
5093 Datum
5095 {
5096  Point *point = PG_GETARG_POINT_P(0);
5097  CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
5098  float8 d;
5099 
5100  d = point_dt(&circle->center, point);
5101  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
5110 {
5111  Point *point = PG_GETARG_POINT_P(0);
5112  CIRCLE *circle = PG_GETARG_CIRCLE_P(1);
5113  float8 result;
5114 
5115  result = float8_mi(point_dt(point, &circle->center),
5116  circle->radius);
5117  if (result < 0.0)
5118  result = 0.0;
5119 
5120  PG_RETURN_FLOAT8(result);
5121 }
5122 
5123 /*
5124  * Distance from a circle to a point
5125  */
5126 Datum
5128 {
5129  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5130  Point *point = PG_GETARG_POINT_P(1);
5131  float8 result;
5132 
5133  result = float8_mi(point_dt(point, &circle->center), circle->radius);
5134  if (result < 0.0)
5135  result = 0.0;
5136 
5137  PG_RETURN_FLOAT8(result);
5138 }
5139 
5140 /* circle_center - returns the center point of the circle.
5141  */
5142 Datum
5144 {
5145  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5146  Point *result;
5147 
5148  result = (Point *) palloc(sizeof(Point));
5149  result->x = circle->center.x;
5150  result->y = circle->center.y;
5151 
5152  PG_RETURN_POINT_P(result);
5153 }
5154 
5155 
5156 /* circle_ar - returns the area of the circle.
5157  */
5158 static float8
5160 {
5161  return float8_mul(float8_mul(circle->radius, circle->radius), M_PI);
5162 }
5163 
5164 
5165 /*----------------------------------------------------------
5166  * Conversion operators.
5167  *---------------------------------------------------------*/
5168 
5169 Datum
5171 {
5172  Point *center = PG_GETARG_POINT_P(0);
5173  float8 radius = PG_GETARG_FLOAT8(1);
5174  CIRCLE *result;
5175 
5176  result = (CIRCLE *) palloc(sizeof(CIRCLE));
5177 
5178  result->center.x = center->x;
5179  result->center.y = center->y;
5180  result->radius = radius;
5181 
5182  PG_RETURN_CIRCLE_P(result);
5183 }
5184 
5185 Datum
5187 {
5188  CIRCLE *circle = PG_GETARG_CIRCLE_P(0);
5189  BOX *box;
5190  float8 delta;
5191 
5192  box = (BOX *) palloc(sizeof(BOX));
5193 
5194  delta = float8_div(circle->radius, sqrt(2.0));
5195 
5196  box->high.x = float8_pl(circle->center.x, delta);
5197  box->low.x = float8_mi(circle->center.x, delta);
5198  box->high.y = float8_pl(circle->center.y, delta);
5199  box->low.y = float8_mi(circle->center.y, delta);
5200 
5201  PG_RETURN_BOX_P(box);
5202 }
5203 
5204 /* box_circle()
5205  * Convert a box to a circle.
5206  */
5207 Datum
5209 {
5210  BOX *box = PG_GETARG_BOX_P(0);
5211  CIRCLE *circle;
5212 
5213  circle = (CIRCLE *) palloc(sizeof(CIRCLE));
5214 
5215  circle->center.x = float8_div(float8_pl(box->high.x, box->low.x), 2.0);
5216  circle->center.y = float8_div(float8_pl(box->high.y, box->low.y), 2.0);
5217 
5218  circle->radius = point_dt(&circle->center, &box->high);
5219 
5220  PG_RETURN_CIRCLE_P(circle);
5221 }
5222 
5223 
5224 Datum
5226 {
5227  int32 npts = PG_GETARG_INT32(0);
5228  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 
5236  if (FPzero(circle->radius))
5237  ereport(ERROR,
5238  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
5239  errmsg("cannot convert circle with radius zero to polygon")));
5240 
5241  if (npts < 2)
5242  ereport(ERROR,
5243  (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
5244  errmsg("must request at least 2 points")));
5245 
5246  base_size = sizeof(poly->p[0]) * npts;
5247  size = offsetof(POLYGON, p) + base_size;
5248 
5249  /* Check for integer overflow */
5250  if (base_size / npts != sizeof(poly->p[0]) || size <= base_size)
5251  ereport(ERROR,
5252  (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
5253  errmsg("too many points requested")));
5254 
5255  poly = (POLYGON *) palloc0(size); /* zero any holes */
5256  SET_VARSIZE(poly, size);
5257  poly->npts = npts;
5258 
5259  anglestep = float8_div(2.0 * M_PI, npts);
5260 
5261  for (i = 0; i < npts; i++)
5262  {
5263  angle = float8_mul(anglestep, i);
5264 
5265  poly->p[i].x = float8_mi(circle->center.x,
5266  float8_mul(circle->radius, cos(angle)));
5267  poly->p[i].y = float8_pl(circle->center.y,
5268  float8_mul(circle->radius, sin(angle)));
5269  }
5270 
5271  make_bound_box(poly);
5272 
5273  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
5286 {
5287  int i;
5288 
5289  Assert(poly->npts > 0);
5290 
5291  result->center.x = 0;
5292  result->center.y = 0;
5293  result->radius = 0;
5294 
5295  for (i = 0; i < poly->npts; i++)
5296  point_add_point(&result->center, &result->center, &poly->p[i]);
5297  result->center.x = float8_div(result->center.x, poly->npts);
5298  result->center.y = float8_div(result->center.y, poly->npts);
5299 
5300  for (i = 0; i < poly->npts; i++)
5301  result->radius = float8_pl(result->radius,
5302  point_dt(&poly->p[i], &result->center));
5303  result->radius = float8_div(result->radius, poly->npts);
5304 }
5305 
5306 Datum
5308 {
5309  POLYGON *poly = PG_GETARG_POLYGON_P(0);
5310  CIRCLE *result;
5311 
5312  result = (CIRCLE *) palloc(sizeof(CIRCLE));
5313 
5314  poly_to_circle(result, poly);
5315 
5316  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
5340 point_inside(Point *p, int npts, Point *plist)
5341 {
5342  float8 x0,
5343  y0;
5344  float8 prev_x,
5345  prev_y;
5346  int i = 0;
5347  float8 x,
5348  y;
5349  int cross,
5350  total_cross = 0;
5351 
5352  Assert(npts > 0);
5353 
5354  /* compute first polygon point relative to single point */
5355  x0 = float8_mi(plist[0].x, p->x);
5356  y0 = float8_mi(plist[0].y, p->y);
5357 
5358  prev_x = x0;
5359  prev_y = y0;
5360  /* loop over polygon points and aggregate total_cross */
5361  for (i = 1; i < npts; i++)
5362  {
5363  /* compute next polygon point relative to single point */
5364  x = float8_mi(plist[i].x, p->x);
5365  y = float8_mi(plist[i].y, p->y);
5366 
5367  /* compute previous to current point crossing */
5368  if ((cross = lseg_crossing(x, y, prev_x, prev_y)) == POINT_ON_POLYGON)
5369  return 2;
5370  total_cross += cross;
5371 
5372  prev_x = x;
5373  prev_y = y;
5374  }
5375 
5376  /* now do the first point */
5377  if ((cross = lseg_crossing(x0, y0, prev_x, prev_y)) == POINT_ON_POLYGON)
5378  return 2;
5379  total_cross += cross;
5380 
5381  if (total_cross != 0)
5382  return 1;
5383  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
5398 {
5399  float8 z;
5400  int y_sign;
5401 
5402  if (FPzero(y))
5403  { /* y == 0, on X axis */
5404  if (FPzero(x)) /* (x,y) is (0,0)? */
5405  return POINT_ON_POLYGON;
5406  else if (FPgt(x, 0))
5407  { /* x > 0 */
5408  if (FPzero(prev_y)) /* y and prev_y are zero */
5409  /* prev_x > 0? */
5410  return FPgt(prev_x, 0.0) ? 0 : POINT_ON_POLYGON;
5411  return FPlt(prev_y, 0.0) ? 1 : -1;
5412  }
5413  else
5414  { /* x < 0, x not on positive X axis */
5415  if (FPzero(prev_y))
5416  /* prev_x < 0? */
5417  return FPlt(prev_x, 0.0) ? 0 : POINT_ON_POLYGON;
5418  return 0;
5419  }
5420  }
5421  else
5422  { /* y != 0 */
5423  /* compute y crossing direction from previous point */
5424  y_sign = FPgt(y, 0.0) ? 1 : -1;
5425 
5426  if (FPzero(prev_y))
5427  /* previous point was on X axis, so new point is either off or on */
5428  return FPlt(prev_x, 0.0) ? 0 : y_sign;
5429  else if ((y_sign < 0 && FPlt(prev_y, 0.0)) ||
5430  (y_sign > 0 && FPgt(prev_y, 0.0)))
5431  /* both above or below X axis */
5432  return 0; /* same sign */
5433  else
5434  { /* y and prev_y cross X-axis */
5435  if (FPge(x, 0.0) && FPgt(prev_x, 0.0))
5436  /* both non-negative so cross positive X-axis */
5437  return 2 * y_sign;
5438  if (FPlt(x, 0.0) && FPle(prev_x, 0.0))
5439  /* both non-positive so do not cross positive X-axis */
5440  return 0;
5441 
5442  /* x and y cross axes, see URL above point_inside() */
5443  z = float8_mi(float8_mul(float8_mi(x, prev_x), y),
5444  float8_mul(float8_mi(y, prev_y), x));
5445  if (FPzero(z))
5446  return POINT_ON_POLYGON;
5447  if ((y_sign < 0 && FPlt(z, 0.0)) ||
5448  (y_sign > 0 && FPgt(z, 0.0)))
5449  return 0;
5450  return 2 * y_sign;
5451  }
5452  }
5453 }
5454 
5455 
5456 static bool
5457 plist_same(int npts, Point *p1, Point *p2)
5458 {
5459  int i,
5460  ii,
5461  j;
5462 
5463  /* find match for first point */
5464  for (i = 0; i < npts; i++)
5465  {
5466  if (point_eq_point(&p2[i], &p1[0]))
5467  {
5468 
5469  /* match found? then look forward through remaining points */
5470  for (ii = 1, j = i + 1; ii < npts; ii++, j++)
5471  {
5472  if (j >= npts)
5473  j = 0;
5474  if (!point_eq_point(&p2[j], &p1[ii]))
5475  break;
5476  }
5477  if (ii == npts)
5478  return true;
5479 
5480  /* match not found forwards? then look backwards */
5481  for (ii = 1, j = i - 1; ii < npts; ii++, j--)
5482  {
5483  if (j < 0)
5484  j = (npts - 1);
5485  if (!point_eq_point(&p2[j], &p1[ii]))
5486  break;
5487  }
5488  if (ii == npts)
5489  return true;
5490  }
5491  }
5492 
5493  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
5520 {
5521  float8 yx,
5522  result;
5523 
5524  /* Handle INF and NaN properly */
5525  if (isinf(x) || isinf(y))
5526  return get_float8_infinity();
5527 
5528  if (isnan(x) || isnan(y))
5529  return get_float8_nan();
5530 
5531  /* Else, drop any minus signs */
5532  x = fabs(x);
5533  y = fabs(y);
5534 
5535  /* Swap x and y if needed to make x the larger one */
5536  if (x < y)
5537  {
5538  float8 temp = x;
5539 
5540  x = y;
5541  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  if (y == 0.0)
5550  return x;
5551 
5552  /* Determine the hypotenuse */
5553  yx = y / x;
5554  result = x * sqrt(1.0 + (yx * yx));
5555 
5556  if (unlikely(isinf(result)))
5558  if (unlikely(result == 0.0))
5560 
5561  return result;
5562 }
signed int int32
Definition: c.h:481
double float8
Definition: c.h:617
#define unlikely(x)
Definition: c.h:298
#define M_PI
Definition: earthdistance.c:11
int errcode(int sqlerrcode)
Definition: elog.c:859
int errmsg(const char *fmt,...)
Definition: elog.c:1072
#define ereturn(context, dummy_value,...)
Definition: elog.h:276
#define ERROR
Definition: elog.h:39
#define ereport(elevel,...)
Definition: elog.h:149
float8 float8in_internal(char *num, char **endptr_p, const char *type_name, const char *orig_string, struct Node *escontext)
Definition: float.c:394
pg_noinline void float_overflow_error(void)
Definition: float.c:85
pg_noinline void float_underflow_error(void)
Definition: float.c:93
char * float8out_internal(double num)
Definition: float.c:536
static float8 float8_min(const float8 val1, const float8 val2)
Definition: float.h:340
static float8 float8_mul(const float8 val1, const float8 val2)
Definition: float.h:208
static float8 float8_pl(const float8 val1, const float8 val2)
Definition: float.h:158
static float8 float8_mi(const float8 val1, const float8 val2)
Definition: float.h:182
static float8 get_float8_infinity(void)
Definition: float.h:94
static float8 float8_max(const float8 val1, const float8 val2)
Definition: float.h:352
static bool float8_eq(const float8 val1, const float8 val2)
Definition: float.h:268
static float8 get_float8_nan(void)
Definition: float.h:123
static float8 float8_div(const float8 val1, const float8 val2)
Definition: float.h:238
static bool float8_lt(const float8 val1, const float8 val2)
Definition: float.h:292
static bool float8_gt(const float8 val1, const float8 val2)
Definition: float.h:316
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:260
#define PG_RETURN_BYTEA_P(x)
Definition: fmgr.h:371
#define PG_GETARG_FLOAT8(n)
Definition: fmgr.h:282
#define PG_RETURN_FLOAT8(x)
Definition: fmgr.h:367
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define PG_GETARG_CSTRING(n)
Definition: fmgr.h:277
#define PG_RETURN_NULL()
Definition: fmgr.h:345
#define PG_RETURN_INT32(x)
Definition: fmgr.h:354
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
static bool FPlt(double A, double B)
Definition: geo_decls.h:59
#define FPzero(A)
Definition: geo_decls.h:44
#define HYPOT(A, B)
Definition: geo_decls.h:91
#define PG_GETARG_POINT_P(n)
Definition: geo_decls.h:185
#define PG_RETURN_CIRCLE_P(x)
Definition: geo_decls.h:276
static bool FPge(double A, double B)
Definition: geo_decls.h:77
#define PG_RETURN_BOX_P(x)
Definition: geo_decls.h:244
#define PG_RETURN_LSEG_P(x)
Definition: geo_decls.h:199
#define PG_RETURN_POINT_P(x)
Definition: geo_decls.h:186
#define PG_GETARG_LINE_P(n)
Definition: geo_decls.h:230
static bool FPne(double A, double B)
Definition: geo_decls.h:53
#define PG_RETURN_POLYGON_P(x)
Definition: geo_decls.h:263
#define PG_GETARG_BOX_P(n)
Definition: geo_decls.h:243
#define PG_GETARG_POLYGON_P(n)
Definition: geo_decls.h:261
#define PG_GETARG_PATH_P_COPY(n)
Definition: geo_decls.h:217
#define PG_GETARG_CIRCLE_P(n)
Definition: geo_decls.h:275
static bool FPgt(double A, double B)
Definition: geo_decls.h:71
static bool FPle(double A, double B)
Definition: geo_decls.h:65
#define PG_GETARG_LSEG_P(n)
Definition: geo_decls.h:198
#define PG_RETURN_LINE_P(x)
Definition: geo_decls.h:231
#define PG_GETARG_PATH_P(n)
Definition: geo_decls.h:216
static bool FPeq(double A, double B)
Definition: geo_decls.h:47
#define PG_RETURN_PATH_P(x)
Definition: geo_decls.h:218
static void poly_to_circle(CIRCLE *result, POLYGON *poly)
Definition: geo_ops.c:5285
Datum circle_div_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5014
static bool pair_decode(char *str, float8 *x, float8 *y, char **endptr_p, const char *type_name, const char *orig_string, Node *escontext)
Definition: geo_ops.c:212
Datum circle_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4826
Datum close_ls(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2988
static bool box_ov(BOX *box1, BOX *box2)
Definition: geo_ops.c:572
static float8 box_closept_point(Point *result, BOX *box, Point *pt)
Definition: geo_ops.c:2878
Datum box_width(PG_FUNCTION_ARGS)
Definition: geo_ops.c:808
Datum path_n_le(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1580
Datum lseg_center(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2316
Datum path_close(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1627
Datum circle_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4611
Datum point_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1993
static int lseg_crossing(float8 x, float8 y, float8 prev_x, float8 prev_y)
Definition: geo_ops.c:5397
Datum circle_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4903
Datum path_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1730
static bool box_interpt_lseg(Point *result, BOX *box, LSEG *lseg)
Definition: geo_ops.c:3263
static bool lseg_inside_poly(Point *a, Point *b, POLYGON *poly, int start)
Definition: geo_ops.c:3866
static bool lseg_contain_point(LSEG *lseg, Point *pt)
Definition: geo_ops.c:3109
#define DELIM
Definition: geo_ops.c:159
Datum lseg_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2111
Datum box_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:583
static bool single_decode(char *num, float8 *x, char **endptr_p, const char *type_name, const char *orig_string, Node *escontext)
Definition: geo_ops.c:194
Datum point_ne(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1964
Datum path_n_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1571
Datum point_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1842
Datum circle_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4814
Datum circle_radius(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5054
Datum cr_circle(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5170
Datum point_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1868
Datum circle_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5066
#define POINT_ON_POLYGON
Definition: geo_ops.c:5337
Datum circle_center(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5143
Datum box_gt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:753
Datum circle_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4801
Datum circle_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4777
Datum path_mul_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4425
Datum box_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:609
static float8 box_ht(BOX *box)
Definition: geo_ops.c:893
Datum dist_pathp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2490
Datum circle_diameter(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5043
static bool poly_contain_poly(POLYGON *contains_poly, POLYGON *contained_poly)
Definition: geo_ops.c:3938
Datum lseg_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2081
Datum path_n_ge(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1589
Datum box_ge(PG_FUNCTION_ARGS)
Definition: geo_ops.c:780
Datum poly_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3415
Datum dist_pc(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5109
Datum point_sub(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4142
Datum poly_npoints(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4494
Datum dist_ps(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2414
Datum poly_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3694
static void statlseg_construct(LSEG *lseg, Point *pt1, Point *pt2)
Definition: geo_ops.c:2142
Datum on_pl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3095
Datum path_isopen(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1610
Datum path_sub_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4409
Datum circle_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4751
Datum point_div(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4196
Datum line_vertical(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1174
Datum box_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:551
Datum line_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:979
Datum circle_box(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5186
static void point_construct(Point *result, float8 x, float8 y)
Definition: geo_ops.c:1884
Datum circle_ge(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4948
Datum poly_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4008
Datum dist_ppoly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2612
Datum poly_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3459
Datum poly_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4027
Datum line_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1261
Datum circle_mul_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4999
Datum point_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1955
static bool box_contain_box(BOX *contains_box, BOX *contained_box)
Definition: geo_ops.c:704
Datum dist_ppath(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2478
Datum point_box(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4302
static void line_construct(LINE *result, Point *pt, float8 m)
Definition: geo_ops.c:1083
#define LDELIM_L
Definition: geo_ops.c:164
Datum box_sub(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4246
Datum circle_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4889
Datum poly_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3602
Datum point_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1919
Datum dist_cpoly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2588
Datum line_perp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1155
Datum path_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1402
Datum dist_pl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2390
static void point_add_point(Point *result, Point *pt1, Point *pt2)
Definition: geo_ops.c:4111
Datum lseg_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2236
Datum poly_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3988
Datum poly_circle(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5307
Datum box_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:832
Datum close_lseg(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2853
Datum path_area(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1380
Datum points_box(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4217
Datum box_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:635
static void make_bound_box(POLYGON *poly)
Definition: geo_ops.c:3376
Datum poly_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3556
static bool line_decode(char *s, const char *str, LINE *line, Node *escontext)
Definition: geo_ops.c:950
Datum poly_path(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4564
static float8 box_closept_lseg(Point *result, BOX *box, LSEG *lseg)
Definition: geo_ops.c:3013
static void point_mul_point(Point *result, Point *pt1, Point *pt2)
Definition: geo_ops.c:4157
Datum circle_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4863
Datum dist_sp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2426
Datum poly_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3801
Datum lseg_ge(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2286
Datum poly_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3533
Datum line_construct_pp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1115
static bool poly_overlap_internal(POLYGON *polya, POLYGON *polyb)
Definition: geo_ops.c:3744
static float8 circle_ar(CIRCLE *circle)
Definition: geo_ops.c:5159
Datum path_open(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1637
Datum box_add(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4231
Datum box_diagonal(PG_FUNCTION_ARGS)
Definition: geo_ops.c:933
Datum line_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1194
Datum box_below_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:722
static void box_cn(Point *center, BOX *box)
Definition: geo_ops.c:872
Datum path_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1526
Datum poly_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3966
Datum circle_add_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4965
static void point_div_point(Point *result, Point *pt1, Point *pt2)
Definition: geo_ops.c:4182
static float8 box_ar(BOX *box)
Definition: geo_ops.c:863
Datum poly_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3475
Datum inter_lb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3328
Datum box_area(PG_FUNCTION_ARGS)
Definition: geo_ops.c:796
static char * path_encode(enum path_delim path_delim, int npts, Point *pt)
Datum path_length(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1792
Datum boxes_bound_box(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4321
Datum box_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:455
Datum circle_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4851
#define LDELIM_C
Definition: geo_ops.c:162
Datum lseg_gt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2276
#define LDELIM_EP
Definition: geo_ops.c:160
static float8 lseg_closept_point(Point *result, LSEG *lseg, Point *pt)
Definition: geo_ops.c:2772
Datum path_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1474
Datum box_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:422
Datum box_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:466
static float8 lseg_closept_line(Point *result, LSEG *lseg, LINE *line)
Definition: geo_ops.c:2960
Datum on_ppath(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3166
Datum pt_contained_circle(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5094
Datum lseg_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2092
Datum line_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1061
Datum lseg_horizontal(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2227
Datum close_pl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2750
static float8 line_closept_point(Point *result, LINE *line, Point *point)
Definition: geo_ops.c:2724
Datum box_above_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:731
Datum on_ps(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3117
#define RDELIM
Definition: geo_ops.c:158
Datum box_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3146
Datum dist_sl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2526
Datum path_poly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4452
Datum point_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1928
Datum box_le(PG_FUNCTION_ARGS)
Definition: geo_ops.c:771
Datum line_parallel(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1146
Datum lseg_length(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2172
float8 pg_hypot(float8 x, float8 y)
Definition: geo_ops.c:5519
Datum line_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1023
Datum line_interpt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1286
Datum close_sb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3063
Datum lseg_le(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2266
Datum on_pb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3137
static int point_inside(Point *p, int npts, Point *plist)
Definition: geo_ops.c:5340
Datum lseg_ne(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2246
Datum path_inter(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1653
Datum dist_lp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2402
Datum box_poly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4535
Datum inter_sb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3315
Datum poly_below(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3625
Datum poly_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3648
Datum pt_contained_poly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4017
Datum circle_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4838
static bool line_interpt_line(Point *result, LINE *l1, LINE *l2)
Definition: geo_ops.c:1314
static void box_construct(BOX *result, Point *pt1, Point *pt2)
Definition: geo_ops.c:518
Datum lseg_lt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2256
Datum circle_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4727
static bool box_contain_lseg(BOX *box, LSEG *lseg)
Definition: geo_ops.c:3217
Datum circle_lt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4921
Datum lseg_vertical(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2219
Datum lseg_construct(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2129
Datum lseg_intersect(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2188
Datum dist_bp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2514
Datum box_div(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4280
Datum path_n_lt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1553
Datum box_overright(PG_FUNCTION_ARGS)
Definition: geo_ops.c:624
Datum path_npoints(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1618
static float8 point_dt(Point *pt1, Point *pt2)
Definition: geo_ops.c:2002
Datum on_sl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3201
Datum point_horiz(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1946
path_delim
Definition: geo_ops.c:74
@ PATH_NONE
Definition: geo_ops.c:75
@ PATH_CLOSED
Definition: geo_ops.c:75
@ PATH_OPEN
Definition: geo_ops.c:75
Datum circle_out(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4681
Datum inter_sl(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3238
static bool path_decode(char *str, bool opentype, int npts, Point *p, bool *isopen, char **endptr_p, const char *type_name, const char *orig_string, Node *escontext)
Definition: geo_ops.c:266
Datum lseg_parallel(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2198
static bool plist_same(int npts, Point *p1, Point *p2)
Definition: geo_ops.c:5457
static bool touched_lseg_inside_poly(Point *a, Point *b, LSEG *s, POLYGON *poly, int start)
Definition: geo_ops.c:3830
Datum box_overabove(PG_FUNCTION_ARGS)
Definition: geo_ops.c:670
Datum poly_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3671
Datum line_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1038
Datum lseg_interpt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2361
Datum point_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1853
Datum box_circle(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5208
Datum path_isclosed(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1602
Datum circle_sub_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4980
Datum line_horizontal(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1182
Datum box_mul(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4261
Datum box_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:563
Datum box_center(PG_FUNCTION_ARGS)
Definition: geo_ops.c:849
Datum circle_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4876
static float8 dist_ppoly_internal(Point *pt, POLYGON *poly)
Definition: geo_ops.c:2630
#define RDELIM_L
Definition: geo_ops.c:165
Datum box_contain(PG_FUNCTION_ARGS)
Definition: geo_ops.c:692
Datum box_height(PG_FUNCTION_ARGS)
Definition: geo_ops.c:820
Datum circle_contain_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5082
Datum dist_bs(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2562
Datum path_add_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4396
static float8 box_wd(BOX *box)
Definition: geo_ops.c:883
static bool box_contain_point(BOX *box, Point *point)
Definition: geo_ops.c:3130
Datum circle_ne(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4912
Datum circle_le(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4939
Datum box_intersect(PG_FUNCTION_ARGS)
Definition: geo_ops.c:908
Datum close_pb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2933
Datum circle_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4789
static float8 point_sl(Point *pt1, Point *pt2)
Definition: geo_ops.c:2023
static float8 lseg_invsl(LSEG *lseg)
Definition: geo_ops.c:2165
Datum point_left(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1901
Datum path_add(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4348
static bool line_contain_point(LINE *line, Point *point)
Definition: geo_ops.c:3087
Datum circle_overlap(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4764
Datum lseg_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2065
Datum circle_area(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5032
#define RDELIM_C
Definition: geo_ops.c:163
Datum on_sb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3224
Datum dist_pb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2502
Datum point_add(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4119
static float8 lseg_sl(LSEG *lseg)
Definition: geo_ops.c:2155
Datum circle_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4703
Datum poly_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3579
Datum box_lt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:744
Datum path_recv(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1488
static float8 dist_cpoly_internal(CIRCLE *circle, POLYGON *poly)
Definition: geo_ops.c:2571
static float8 line_sl(LINE *line)
Definition: geo_ops.c:1233
#define RDELIM_EP
Definition: geo_ops.c:161
Datum line_intersect(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1137
Datum box_eq(PG_FUNCTION_ARGS)
Definition: geo_ops.c:762
Datum path_n_gt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1562
Datum poly_box(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4519
Datum point_slope(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2008
Datum circle_poly(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5225
static int pair_count(char *s, char delim)
Definition: geo_ops.c:392
static bool lseg_interpt_lseg(Point *result, LSEG *l1, LSEG *l2)
Definition: geo_ops.c:2338
Datum point_right(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1910
Datum box_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:501
static float8 point_invsl(Point *pt1, Point *pt2)
Definition: geo_ops.c:2039
Datum point_mul(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4167
static float8 dist_ppath_internal(Point *pt, PATH *path)
Definition: geo_ops.c:2435
static void pair_encode(float8 x, float8 y, StringInfo str)
Definition: geo_ops.c:255
Datum dist_polyc(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2600
Datum dist_sb(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2550
static float8 line_invsl(LINE *line)
Definition: geo_ops.c:1247
static void point_sub_point(Point *result, Point *pt1, Point *pt2)
Definition: geo_ops.c:4134
Datum circle_gt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4930
Datum box_overbelow(PG_FUNCTION_ARGS)
Definition: geo_ops.c:647
static float8 lseg_closept_lseg(Point *result, LSEG *on_lseg, LSEG *to_lseg)
Definition: geo_ops.c:2810
Datum dist_cpoint(PG_FUNCTION_ARGS)
Definition: geo_ops.c:5127
Datum lseg_distance(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2306
Datum dist_ls(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2538
Datum construct_point(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4096
Datum poly_center(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4503
Datum lseg_perp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2210
Datum box_contained(PG_FUNCTION_ARGS)
Definition: geo_ops.c:681
Datum path_div_pt(PG_FUNCTION_ARGS)
Definition: geo_ops.c:4438
static bool lseg_interpt_line(Point *result, LSEG *lseg, LINE *line)
Definition: geo_ops.c:2675
Datum point_in(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1831
Datum box_overleft(PG_FUNCTION_ARGS)
Definition: geo_ops.c:598
static bool point_eq_point(Point *pt1, Point *pt2)
Definition: geo_ops.c:1977
#define LDELIM
Definition: geo_ops.c:157
Datum close_ps(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2791
Datum dist_polyp(PG_FUNCTION_ARGS)
Definition: geo_ops.c:2621
Datum box_above(PG_FUNCTION_ARGS)
Definition: geo_ops.c:658
Datum poly_same(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3720
static void single_encode(float8 x, StringInfo str)
Definition: geo_ops.c:203
Datum point_vert(PG_FUNCTION_ARGS)
Definition: geo_ops.c:1937
Datum poly_send(PG_FUNCTION_ARGS)
Definition: geo_ops.c:3510
int y
Definition: isn.c:72
int b
Definition: isn.c:70
int x
Definition: isn.c:71
int a
Definition: isn.c:69
int j
Definition: isn.c:74
int i
Definition: isn.c:73
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
Definition: mcxt.c:1508
void * palloc0(Size size)
Definition: mcxt.c:1334
void * palloc(Size size)
Definition: mcxt.c:1304
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
#define SOFT_ERROR_OCCURRED(escontext)
Definition: miscnodes.h:52
static char * buf
Definition: pg_test_fsync.c:73
void check_stack_depth(void)
Definition: postgres.c:3531
uintptr_t Datum
Definition: postgres.h:64
unsigned int pq_getmsgint(StringInfo msg, int b)
Definition: pqformat.c:415
float8 pq_getmsgfloat8(StringInfo msg)
Definition: pqformat.c:488
void pq_begintypsend(StringInfo buf)
Definition: pqformat.c:326
int pq_getmsgbyte(StringInfo msg)
Definition: pqformat.c:399
bytea * pq_endtypsend(StringInfo buf)
Definition: pqformat.c:346
void pq_sendfloat8(StringInfo buf, float8 f)
Definition: pqformat.c:276
static void pq_sendint32(StringInfo buf, uint32 i)
Definition: pqformat.h:144
static void pq_sendbyte(StringInfo buf, uint8 byt)
Definition: pqformat.h:160
char * psprintf(const char *fmt,...)
Definition: psprintf.c:46
static pg_noinline void Size size
Definition: slab.c:607
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:97
void appendStringInfoString(StringInfo str, const char *s)
Definition: stringinfo.c:182
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:194
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
StringInfoData * StringInfo
Definition: stringinfo.h:54
Definition: geo_decls.h:141
Point low
Definition: geo_decls.h:143
Point high
Definition: geo_decls.h:142
float8 radius
Definition: geo_decls.h:165
Point center
Definition: geo_decls.h:164
float8 A
Definition: geo_decls.h:130
float8 B
Definition: geo_decls.h:131
float8 C
Definition: geo_decls.h:132
Point p[2]
Definition: geo_decls.h:108
Definition: nodes.h:129
Point p[FLEXIBLE_ARRAY_MEMBER]
Definition: geo_decls.h:121
int32 npts
Definition: geo_decls.h:118
int32 closed
Definition: geo_decls.h:119
int32 dummy
Definition: geo_decls.h:120
Point p[FLEXIBLE_ARRAY_MEMBER]
Definition: geo_decls.h:156
int32 npts
Definition: geo_decls.h:154
BOX boundbox
Definition: geo_decls.h:155
float8 y
Definition: geo_decls.h:99
float8 x
Definition: geo_decls.h:98
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305