summaryrefslogtreecommitdiff
path: root/src/backend/utils/adt/geo_ops.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/utils/adt/geo_ops.c')
-rw-r--r--src/backend/utils/adt/geo_ops.c5111
1 files changed, 2760 insertions, 2351 deletions
diff --git a/src/backend/utils/adt/geo_ops.c b/src/backend/utils/adt/geo_ops.c
index d805ba7a220..71b478788ef 100644
--- a/src/backend/utils/adt/geo_ops.c
+++ b/src/backend/utils/adt/geo_ops.c
@@ -1,21 +1,21 @@
/*-------------------------------------------------------------------------
*
* geo_ops.c--
- * 2D geometric operations
+ * 2D geometric operations
*
* Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
- * $Header: /cvsroot/pgsql/src/backend/utils/adt/geo_ops.c,v 1.19 1997/09/05 20:20:56 momjian Exp $
+ * $Header: /cvsroot/pgsql/src/backend/utils/adt/geo_ops.c,v 1.20 1997/09/07 04:50:18 momjian Exp $
*
*-------------------------------------------------------------------------
*/
#include <math.h>
#include <limits.h>
#include <float.h>
-#include <stdio.h> /* for sprintf proto, etc. */
-#include <stdlib.h> /* for strtod, etc. */
+#include <stdio.h> /* for sprintf proto, etc. */
+#include <stdlib.h> /* for strtod, etc. */
#include <string.h>
#include <ctype.h>
@@ -28,38 +28,38 @@
#define PI 3.1415926536
#endif
-static int point_inside( Point *p, int npts, Point plist[]);
-static int lseg_crossing( double x, double y, double px, double py);
-static BOX *box_construct(double x1, double x2, double y1, double y2);
-static BOX *box_copy(BOX *box);
-static BOX *box_fill(BOX *result, double x1, double x2, double y1, double y2);
-static double box_ht(BOX *box);
-static double box_wd(BOX *box);
-static double circle_ar(CIRCLE *circle);
-static CIRCLE *circle_copy(CIRCLE *circle);
-static LINE *line_construct_pm(Point *pt, double m);
-static bool line_horizontal(LINE *line);
-static Point *line_interpt(LINE *l1, LINE *l2);
-static bool line_intersect(LINE *l1, LINE *l2);
-static bool line_parallel(LINE *l1, LINE *l2);
-static bool line_vertical(LINE *line);
-static double lseg_dt(LSEG *l1, LSEG *l2);
-static void make_bound_box(POLYGON *poly);
-static PATH *path_copy(PATH *path);
-static bool plist_same(int npts, Point p1[], Point p2[]);
-static Point *point_construct(double x, double y);
-static Point *point_copy(Point *pt);
-static int single_decode(char *str, float8 *x, char **ss);
-static int single_encode(float8 x, char *str);
-static int pair_decode(char *str, float8 *x, float8 *y, char **s);
-static int pair_encode(float8 x, float8 y, char *str);
-static int pair_count(char *s, char delim);
-static int path_decode(int opentype, int npts, char *str, int *isopen, char **ss, Point *p);
-static char *path_encode( bool closed, int npts, Point *pt);
-static void statlseg_construct(LSEG *lseg, Point *pt1, Point *pt2);
-static double box_ar(BOX *box);
-static Point *interpt_sl(LSEG *lseg, LINE *line);
-static LINE *line_construct_pp(Point *pt1, Point *pt2);
+static int point_inside(Point * p, int npts, Point plist[]);
+static int lseg_crossing(double x, double y, double px, double py);
+static BOX *box_construct(double x1, double x2, double y1, double y2);
+static BOX *box_copy(BOX * box);
+static BOX *box_fill(BOX * result, double x1, double x2, double y1, double y2);
+static double box_ht(BOX * box);
+static double box_wd(BOX * box);
+static double circle_ar(CIRCLE * circle);
+static CIRCLE *circle_copy(CIRCLE * circle);
+static LINE *line_construct_pm(Point * pt, double m);
+static bool line_horizontal(LINE * line);
+static Point *line_interpt(LINE * l1, LINE * l2);
+static bool line_intersect(LINE * l1, LINE * l2);
+static bool line_parallel(LINE * l1, LINE * l2);
+static bool line_vertical(LINE * line);
+static double lseg_dt(LSEG * l1, LSEG * l2);
+static void make_bound_box(POLYGON * poly);
+static PATH *path_copy(PATH * path);
+static bool plist_same(int npts, Point p1[], Point p2[]);
+static Point *point_construct(double x, double y);
+static Point *point_copy(Point * pt);
+static int single_decode(char *str, float8 * x, char **ss);
+static int single_encode(float8 x, char *str);
+static int pair_decode(char *str, float8 * x, float8 * y, char **s);
+static int pair_encode(float8 x, float8 y, char *str);
+static int pair_count(char *s, char delim);
+static int path_decode(int opentype, int npts, char *str, int *isopen, char **ss, Point * p);
+static char *path_encode(bool closed, int npts, Point * pt);
+static void statlseg_construct(LSEG * lseg, Point * pt1, Point * pt2);
+static double box_ar(BOX * box);
+static Point *interpt_sl(LSEG * lseg, LINE * line);
+static LINE *line_construct_pp(Point * pt1, Point * pt2);
/*
@@ -68,203 +68,248 @@ static LINE *line_construct_pp(Point *pt1, Point *pt2);
* LDELIM_EP, RDELIM_EP are left and right delimiters for paths with endpoints.
*/
-#define LDELIM '('
-#define RDELIM ')'
-#define DELIM ','
-#define LDELIM_EP '['
-#define RDELIM_EP ']'
-#define LDELIM_C '<'
-#define RDELIM_C '>'
+#define LDELIM '('
+#define RDELIM ')'
+#define DELIM ','
+#define LDELIM_EP '['
+#define RDELIM_EP ']'
+#define LDELIM_C '<'
+#define RDELIM_C '>'
/* Maximum number of output digits printed */
#define P_MAXDIG DBL_DIG
#define P_MAXLEN (2*(P_MAXDIG+7)+1)
-static int digits8 = P_MAXDIG;
+static int digits8 = P_MAXDIG;
/*
* Geometric data types are composed of points.
* This code tries to support a common format throughout the data types,
- * to allow for more predictable usage and data type conversion.
+ * to allow for more predictable usage and data type conversion.
* The fundamental unit is the point. Other units are line segments,
- * open paths, boxes, closed paths, and polygons (which should be considered
- * non-intersecting closed paths).
+ * open paths, boxes, closed paths, and polygons (which should be considered
+ * non-intersecting closed paths).
*
* Data representation is as follows:
- * point: (x,y)
- * line segment: [(x1,y1),(x2,y2)]
- * box: (x1,y1),(x2,y2)
- * open path: [(x1,y1),...,(xn,yn)]
- * closed path: ((x1,y1),...,(xn,yn))
- * polygon: ((x1,y1),...,(xn,yn))
+ * point: (x,y)
+ * line segment: [(x1,y1),(x2,y2)]
+ * box: (x1,y1),(x2,y2)
+ * open path: [(x1,y1),...,(xn,yn)]
+ * closed path: ((x1,y1),...,(xn,yn))
+ * polygon: ((x1,y1),...,(xn,yn))
*
* For boxes, the points are opposite corners with the first point at the top right.
* For closed paths and polygons, the points should be reordered to allow
- * fast and correct equality comparisons.
+ * fast and correct equality comparisons.
*
* XXX perhaps points in complex shapes should be reordered internally
- * to allow faster internal operations, but should keep track of input order
- * and restore that order for text output - tgl 97/01/16
+ * to allow faster internal operations, but should keep track of input order
+ * and restore that order for text output - tgl 97/01/16
*/
-static int single_decode(char *str, float8 *x, char **s)
+static int
+single_decode(char *str, float8 * x, char **s)
{
- char *cp;
+ char *cp;
- if (!PointerIsValid(str))
- return(FALSE);
+ if (!PointerIsValid(str))
+ return (FALSE);
- while (isspace( *str)) str++;
- *x = strtod( str, &cp);
+ while (isspace(*str))
+ str++;
+ *x = strtod(str, &cp);
#ifdef GEODEBUG
-fprintf( stderr, "single_decode- (%x) try decoding %s to %g\n", (cp-str), str, *x);
+ fprintf(stderr, "single_decode- (%x) try decoding %s to %g\n", (cp - str), str, *x);
#endif
- if (cp <= str) return(FALSE);
- while (isspace( *cp)) cp++;
-
- if (s != NULL) *s = cp;
+ if (cp <= str)
+ return (FALSE);
+ while (isspace(*cp))
+ cp++;
- return(TRUE);
-} /* single_decode() */
+ if (s != NULL)
+ *s = cp;
-static int single_encode(float8 x, char *str)
-{
- sprintf(str, "%.*g", digits8, x);
- return(TRUE);
-} /* single_encode() */
+ return (TRUE);
+} /* single_decode() */
-static int pair_decode(char *str, float8 *x, float8 *y, char **s)
+static int
+single_encode(float8 x, char *str)
{
- int has_delim;
- char *cp;
-
- if (!PointerIsValid(str))
- return(FALSE);
-
- while (isspace( *str)) str++;
- if ((has_delim = (*str == LDELIM))) str++;
+ sprintf(str, "%.*g", digits8, x);
+ return (TRUE);
+} /* single_encode() */
- while (isspace( *str)) str++;
- *x = strtod( str, &cp);
- if (cp <= str) return(FALSE);
- while (isspace( *cp)) cp++;
- if (*cp++ != DELIM) return(FALSE);
- while (isspace( *cp)) cp++;
- *y = strtod( cp, &str);
- if (str <= cp) return(FALSE);
- while (isspace( *str)) str++;
- if (has_delim) {
- if (*str != RDELIM) return(FALSE);
- str++;
- while (isspace( *str)) str++;
- }
- if (s != NULL) *s = str;
+static int
+pair_decode(char *str, float8 * x, float8 * y, char **s)
+{
+ int has_delim;
+ char *cp;
+
+ if (!PointerIsValid(str))
+ return (FALSE);
+
+ while (isspace(*str))
+ str++;
+ if ((has_delim = (*str == LDELIM)))
+ str++;
+
+ while (isspace(*str))
+ str++;
+ *x = strtod(str, &cp);
+ if (cp <= str)
+ return (FALSE);
+ while (isspace(*cp))
+ cp++;
+ if (*cp++ != DELIM)
+ return (FALSE);
+ while (isspace(*cp))
+ cp++;
+ *y = strtod(cp, &str);
+ if (str <= cp)
+ return (FALSE);
+ while (isspace(*str))
+ str++;
+ if (has_delim)
+ {
+ if (*str != RDELIM)
+ return (FALSE);
+ str++;
+ while (isspace(*str))
+ str++;
+ }
+ if (s != NULL)
+ *s = str;
- return(TRUE);
+ return (TRUE);
}
-static int pair_encode(float8 x, float8 y, char *str)
+static int
+pair_encode(float8 x, float8 y, char *str)
{
- sprintf(str, "%.*g,%.*g", digits8, x, digits8, y);
- return(TRUE);
+ sprintf(str, "%.*g,%.*g", digits8, x, digits8, y);
+ return (TRUE);
}
-static int path_decode(int opentype, int npts, char *str, int *isopen, char **ss, Point *p)
-{
- int depth = 0;
- char *s, *cp;
- int i;
-
- s = str;
- while (isspace( *s)) s++;
- if ((*isopen = (*s == LDELIM_EP))) {
- /* no open delimiter allowed? */
- if (! opentype) return(FALSE);
- depth++;
- s++;
- while (isspace( *s)) s++;
+static int
+path_decode(int opentype, int npts, char *str, int *isopen, char **ss, Point * p)
+{
+ int depth = 0;
+ char *s,
+ *cp;
+ int i;
+
+ s = str;
+ while (isspace(*s))
+ s++;
+ if ((*isopen = (*s == LDELIM_EP)))
+ {
+ /* no open delimiter allowed? */
+ if (!opentype)
+ return (FALSE);
+ depth++;
+ s++;
+ while (isspace(*s))
+ s++;
- } else if (*s == LDELIM) {
- cp = (s+1);
- while (isspace( *cp)) cp++;
- if (*cp == LDELIM) {
- /* nested delimiters with only one point? */
- if (npts <= 1) return(FALSE);
- depth++;
- s = cp;
- } else if (strrchr( s, LDELIM) == s) {
- depth++;
- s = cp;
}
- }
-
- for (i = 0; i < npts; i++) {
- if (! pair_decode( s, &(p->x), &(p->y), &s))
- return(FALSE);
+ else if (*s == LDELIM)
+ {
+ cp = (s + 1);
+ while (isspace(*cp))
+ cp++;
+ if (*cp == LDELIM)
+ {
+ /* nested delimiters with only one point? */
+ if (npts <= 1)
+ return (FALSE);
+ depth++;
+ s = cp;
+ }
+ else if (strrchr(s, LDELIM) == s)
+ {
+ depth++;
+ s = cp;
+ }
+ }
- if (*s == DELIM) s++;
- p++;
- }
+ for (i = 0; i < npts; i++)
+ {
+ if (!pair_decode(s, &(p->x), &(p->y), &s))
+ return (FALSE);
- while (depth > 0) {
- if ((*s == RDELIM)
- || ((*s == RDELIM_EP) && (*isopen) && (depth == 1))) {
- depth--;
- s++;
- while (isspace( *s)) s++;
- } else {
- return(FALSE);
+ if (*s == DELIM)
+ s++;
+ p++;
}
- }
- *ss = s;
- return(TRUE);
-} /* path_decode() */
+ while (depth > 0)
+ {
+ if ((*s == RDELIM)
+ || ((*s == RDELIM_EP) && (*isopen) && (depth == 1)))
+ {
+ depth--;
+ s++;
+ while (isspace(*s))
+ s++;
+ }
+ else
+ {
+ return (FALSE);
+ }
+ }
+ *ss = s;
+
+ return (TRUE);
+} /* path_decode() */
+
+static char *
+path_encode(bool closed, int npts, Point * pt)
+{
+ char *result = PALLOC(npts * (P_MAXLEN + 3) + 2);
+
+ char *cp;
+ int i;
+
+ cp = result;
+ switch (closed)
+ {
+ case TRUE:
+ *cp++ = LDELIM;
+ break;
+ case FALSE:
+ *cp++ = LDELIM_EP;
+ break;
+ default:
+ break;
+ }
-static char *path_encode( bool closed, int npts, Point *pt)
-{
- char *result = PALLOC(npts*(P_MAXLEN+3)+2);
+ for (i = 0; i < npts; i++)
+ {
+ *cp++ = LDELIM;
+ if (!pair_encode(pt->x, pt->y, cp))
+ elog(WARN, "Unable to format path", NULL);
+ cp += strlen(cp);
+ *cp++ = RDELIM;
+ *cp++ = DELIM;
+ pt++;
+ }
+ cp--;
+ switch (closed)
+ {
+ case TRUE:
+ *cp++ = RDELIM;
+ break;
+ case FALSE:
+ *cp++ = RDELIM_EP;
+ break;
+ default:
+ break;
+ }
+ *cp = '\0';
- char *cp;
- int i;
-
- cp = result;
- switch (closed) {
- case TRUE:
- *cp++ = LDELIM;
- break;
- case FALSE:
- *cp++ = LDELIM_EP;
- break;
- default:
- break;
- }
-
- for (i = 0; i < npts; i++) {
- *cp++ = LDELIM;
- if (! pair_encode( pt->x, pt->y, cp))
- elog (WARN, "Unable to format path", NULL);
- cp += strlen(cp);
- *cp++ = RDELIM;
- *cp++ = DELIM;
- pt++;
- }
- cp--;
- switch (closed) {
- case TRUE:
- *cp++ = RDELIM;
- break;
- case FALSE:
- *cp++ = RDELIM_EP;
- break;
- default:
- break;
- }
- *cp = '\0';
-
- return(result);
-} /* path_encode() */
+ return (result);
+} /* path_encode() */
/*-------------------------------------------------------------
* pair_count - count the number of points
@@ -273,20 +318,22 @@ static char *path_encode( bool closed, int npts, Point *pt)
* '(1,3,2,4)'
* require an odd number of delim characters in the string
*-------------------------------------------------------------*/
-static int pair_count(char *s, char delim)
+static int
+pair_count(char *s, char delim)
{
- int ndelim = 0;
+ int ndelim = 0;
- while ((s = strchr( s, delim)) != NULL) {
- ndelim++;
- s++;
- }
- return((ndelim % 2)? ((ndelim+1)/2): -1);
+ while ((s = strchr(s, delim)) != NULL)
+ {
+ ndelim++;
+ s++;
+ }
+ return ((ndelim % 2) ? ((ndelim + 1) / 2) : -1);
}
/***********************************************************************
**
- ** Routines for two-dimensional boxes.
+ ** Routines for two-dimensional boxes.
**
***********************************************************************/
@@ -294,716 +341,795 @@ static int pair_count(char *s, char delim)
* Formatting and conversion routines.
*---------------------------------------------------------*/
-/* box_in - convert a string to internal form.
+/* box_in - convert a string to internal form.
*
- * External format: (two corners of box)
- * "(f8, f8), (f8, f8)"
- * also supports the older style "(f8, f8, f8, f8)"
+ * External format: (two corners of box)
+ * "(f8, f8), (f8, f8)"
+ * also supports the older style "(f8, f8, f8, f8)"
*/
-BOX *box_in(char *str)
+BOX *
+box_in(char *str)
{
- BOX *box = PALLOCTYPE(BOX);
+ BOX *box = PALLOCTYPE(BOX);
- int isopen;
- char *s;
- double x, y;
+ int isopen;
+ char *s;
+ double x,
+ y;
- if (!PointerIsValid(str))
- elog (WARN," Bad (null) box external representation",NULL);
+ if (!PointerIsValid(str))
+ elog(WARN, " Bad (null) box external representation", NULL);
- if ((! path_decode(FALSE, 2, str, &isopen, &s, &(box->high)))
- || (*s != '\0'))
- elog (WARN, "Bad box external representation '%s'",str);
+ if ((!path_decode(FALSE, 2, str, &isopen, &s, &(box->high)))
+ || (*s != '\0'))
+ elog(WARN, "Bad box external representation '%s'", str);
- /* reorder corners if necessary... */
- if (box->high.x < box->low.x) {
- x = box->high.x;
- box->high.x = box->low.x;
- box->low.x = x;
- }
- if (box->high.y < box->low.y) {
- y = box->high.y;
- box->high.y = box->low.y;
- box->low.y = y;
- }
+ /* reorder corners if necessary... */
+ if (box->high.x < box->low.x)
+ {
+ x = box->high.x;
+ box->high.x = box->low.x;
+ box->low.x = x;
+ }
+ if (box->high.y < box->low.y)
+ {
+ y = box->high.y;
+ box->high.y = box->low.y;
+ box->low.y = y;
+ }
- return(box);
-} /* box_in() */
+ return (box);
+} /* box_in() */
-/* box_out - convert a box to external form.
+/* box_out - convert a box to external form.
*/
-char *box_out(BOX *box)
+char *
+box_out(BOX * box)
{
- if (!PointerIsValid(box))
- return(NULL);
+ if (!PointerIsValid(box))
+ return (NULL);
- return( path_encode( -1, 2, (Point *) &(box->high)));
-} /* box_out() */
+ return (path_encode(-1, 2, (Point *) & (box->high)));
+} /* box_out() */
-/* box_construct - fill in a new box.
+/* box_construct - fill in a new box.
*/
-static BOX *box_construct(double x1, double x2, double y1, double y2)
+static BOX *
+box_construct(double x1, double x2, double y1, double y2)
{
- BOX *result = PALLOCTYPE(BOX);
+ BOX *result = PALLOCTYPE(BOX);
- return( box_fill(result, x1, x2, y1, y2) );
+ return (box_fill(result, x1, x2, y1, y2));
}
-/* box_fill - fill in a static box
+/* box_fill - fill in a static box
*/
-static BOX *box_fill(BOX *result, double x1, double x2, double y1, double y2)
+static BOX *
+box_fill(BOX * result, double x1, double x2, double y1, double y2)
{
- if (x1 > x2) {
- result->high.x = x1;
- result->low.x = x2;
- } else {
- result->high.x = x2;
- result->low.x = x1;
- }
- if (y1 > y2) {
- result->high.y = y1;
- result->low.y = y2;
- } else {
- result->high.y = y2;
- result->low.y = y1;
- }
-
- return(result);
+ if (x1 > x2)
+ {
+ result->high.x = x1;
+ result->low.x = x2;
+ }
+ else
+ {
+ result->high.x = x2;
+ result->low.x = x1;
+ }
+ if (y1 > y2)
+ {
+ result->high.y = y1;
+ result->low.y = y2;
+ }
+ else
+ {
+ result->high.y = y2;
+ result->low.y = y1;
+ }
+
+ return (result);
}
-/* box_copy - copy a box
+/* box_copy - copy a box
*/
-static BOX *box_copy(BOX *box)
+static BOX *
+box_copy(BOX * box)
{
- BOX *result = PALLOCTYPE(BOX);
+ BOX *result = PALLOCTYPE(BOX);
- memmove((char *) result, (char *) box, sizeof(BOX));
-
- return(result);
+ memmove((char *) result, (char *) box, sizeof(BOX));
+
+ return (result);
}
/*----------------------------------------------------------
- * Relational operators for BOXes.
- * <, >, <=, >=, and == are based on box area.
+ * Relational operators for BOXes.
+ * <, >, <=, >=, and == are based on box area.
*---------------------------------------------------------*/
-/* box_same - are two boxes identical?
+/* box_same - are two boxes identical?
*/
-bool box_same(BOX *box1, BOX *box2)
+bool
+box_same(BOX * box1, BOX * box2)
{
- return((FPeq(box1->high.x,box2->high.x) && FPeq(box1->low.x,box2->low.x)) &&
- (FPeq(box1->high.y,box2->high.y) && FPeq(box1->low.y,box2->low.y)));
+ return ((FPeq(box1->high.x, box2->high.x) && FPeq(box1->low.x, box2->low.x)) &&
+ (FPeq(box1->high.y, box2->high.y) && FPeq(box1->low.y, box2->low.y)));
}
-/* box_overlap - does box1 overlap box2?
+/* box_overlap - does box1 overlap box2?
*/
-bool box_overlap(BOX *box1, BOX *box2)
+bool
+box_overlap(BOX * box1, BOX * box2)
{
- return(((FPge(box1->high.x,box2->high.x) && FPle(box1->low.x,box2->high.x)) ||
- (FPge(box2->high.x,box1->high.x) && FPle(box2->low.x,box1->high.x))) &&
- ((FPge(box1->high.y,box2->high.y) && FPle(box1->low.y,box2->high.y)) ||
- (FPge(box2->high.y,box1->high.y) && FPle(box2->low.y,box1->high.y))) );
+ return (((FPge(box1->high.x, box2->high.x) && FPle(box1->low.x, box2->high.x)) ||
+ (FPge(box2->high.x, box1->high.x) && FPle(box2->low.x, box1->high.x))) &&
+ ((FPge(box1->high.y, box2->high.y) && FPle(box1->low.y, box2->high.y)) ||
+ (FPge(box2->high.y, box1->high.y) && FPle(box2->low.y, box1->high.y))));
}
-/* box_overleft - is the right edge of box1 to the left of
- * the right edge of box2?
+/* box_overleft - is the right edge of box1 to the left of
+ * the right edge of box2?
*
- * This is "less than or equal" for the end of a time range,
- * when time ranges are stored as rectangles.
+ * This is "less than or equal" for the end of a time range,
+ * when time ranges are stored as rectangles.
*/
-bool box_overleft(BOX *box1, BOX *box2)
+bool
+box_overleft(BOX * box1, BOX * box2)
{
- return(FPle(box1->high.x,box2->high.x));
+ return (FPle(box1->high.x, box2->high.x));
}
-/* box_left - is box1 strictly left of box2?
+/* box_left - is box1 strictly left of box2?
*/
-bool box_left(BOX *box1, BOX *box2)
+bool
+box_left(BOX * box1, BOX * box2)
{
- return(FPlt(box1->high.x,box2->low.x));
+ return (FPlt(box1->high.x, box2->low.x));
}
-/* box_right - is box1 strictly right of box2?
+/* box_right - is box1 strictly right of box2?
*/
-bool box_right(BOX *box1, BOX *box2)
+bool
+box_right(BOX * box1, BOX * box2)
{
- return(FPgt(box1->low.x,box2->high.x));
+ return (FPgt(box1->low.x, box2->high.x));
}
-/* box_overright - is the left edge of box1 to the right of
- * the left edge of box2?
+/* box_overright - is the left edge of box1 to the right of
+ * the left edge of box2?
*
- * This is "greater than or equal" for time ranges, when time ranges
- * are stored as rectangles.
+ * This is "greater than or equal" for time ranges, when time ranges
+ * are stored as rectangles.
*/
-bool box_overright(BOX *box1, BOX *box2)
+bool
+box_overright(BOX * box1, BOX * box2)
{
- return(box1->low.x >= box2->low.x);
+ return (box1->low.x >= box2->low.x);
}
-/* box_contained - is box1 contained by box2?
+/* box_contained - is box1 contained by box2?
*/
-bool box_contained(BOX *box1, BOX *box2)
+bool
+box_contained(BOX * box1, BOX * box2)
{
- return((FPle(box1->high.x,box2->high.x) && FPge(box1->low.x,box2->low.x)) &&
- (FPle(box1->high.y,box2->high.y) && FPge(box1->low.y,box2->low.y)));
+ return ((FPle(box1->high.x, box2->high.x) && FPge(box1->low.x, box2->low.x)) &&
+ (FPle(box1->high.y, box2->high.y) && FPge(box1->low.y, box2->low.y)));
}
-/* box_contain - does box1 contain box2?
+/* box_contain - does box1 contain box2?
*/
-bool box_contain(BOX *box1, BOX *box2)
+bool
+box_contain(BOX * box1, BOX * box2)
{
- return((FPge(box1->high.x,box2->high.x) && FPle(box1->low.x,box2->low.x) &&
- FPge(box1->high.y,box2->high.y) && FPle(box1->low.y,box2->low.y)));
+ return ((FPge(box1->high.x, box2->high.x) && FPle(box1->low.x, box2->low.x) &&
+ FPge(box1->high.y, box2->high.y) && FPle(box1->low.y, box2->low.y)));
}
-/* box_positionop -
- * is box1 entirely {above,below} box2?
+/* box_positionop -
+ * is box1 entirely {above,below} box2?
*/
-bool box_below(BOX *box1, BOX *box2)
+bool
+box_below(BOX * box1, BOX * box2)
{
- return( FPle(box1->high.y,box2->low.y) );
+ return (FPle(box1->high.y, box2->low.y));
}
-bool box_above(BOX *box1, BOX *box2)
+bool
+box_above(BOX * box1, BOX * box2)
{
- return( FPge(box1->low.y,box2->high.y) );
+ return (FPge(box1->low.y, box2->high.y));
}
-/* box_relop - is area(box1) relop area(box2), within
- * our accuracy constraint?
+/* box_relop - is area(box1) relop area(box2), within
+ * our accuracy constraint?
*/
-bool box_lt(BOX *box1, BOX *box2)
+bool
+box_lt(BOX * box1, BOX * box2)
{
- return( FPlt(box_ar(box1), box_ar(box2)) );
+ return (FPlt(box_ar(box1), box_ar(box2)));
}
-bool box_gt(BOX *box1, BOX *box2)
+bool
+box_gt(BOX * box1, BOX * box2)
{
- return( FPgt(box_ar(box1), box_ar(box2)) );
+ return (FPgt(box_ar(box1), box_ar(box2)));
}
-bool box_eq(BOX *box1, BOX *box2)
+bool
+box_eq(BOX * box1, BOX * box2)
{
- return( FPeq(box_ar(box1), box_ar(box2)) );
+ return (FPeq(box_ar(box1), box_ar(box2)));
}
-bool box_le(BOX *box1, BOX *box2)
+bool
+box_le(BOX * box1, BOX * box2)
{
- return( FPle(box_ar(box1), box_ar(box2)) );
+ return (FPle(box_ar(box1), box_ar(box2)));
}
-bool box_ge(BOX *box1, BOX *box2)
+bool
+box_ge(BOX * box1, BOX * box2)
{
- return( FPge(box_ar(box1), box_ar(box2)) );
+ return (FPge(box_ar(box1), box_ar(box2)));
}
/*----------------------------------------------------------
- * "Arithmetic" operators on boxes.
- * box_foo returns foo as an object (pointer) that
+ * "Arithmetic" operators on boxes.
+ * box_foo returns foo as an object (pointer) that
can be passed between languages.
- * box_xx is an internal routine which returns the
- * actual value (and cannot be handed back to
- * LISP).
+ * box_xx is an internal routine which returns the
+ * actual value (and cannot be handed back to
+ * LISP).
*---------------------------------------------------------*/
-/* box_area - returns the area of the box.
+/* box_area - returns the area of the box.
*/
-double *box_area(BOX *box)
+double *
+box_area(BOX * box)
{
- double *result = PALLOCTYPE(double);
+ double *result = PALLOCTYPE(double);
- *result = box_wd(box) * box_ht(box);
-
- return(result);
+ *result = box_wd(box) * box_ht(box);
+
+ return (result);
}
-/* box_width - returns the width of the box
- * (horizontal magnitude).
+/* box_width - returns the width of the box
+ * (horizontal magnitude).
*/
-double *box_width(BOX *box)
+double *
+box_width(BOX * box)
{
- double *result = PALLOCTYPE(double);
+ double *result = PALLOCTYPE(double);
+
+ *result = box->high.x - box->low.x;
- *result = box->high.x - box->low.x;
-
- return(result);
-} /* box_width() */
+ return (result);
+} /* box_width() */
-/* box_height - returns the height of the box
- * (vertical magnitude).
+/* box_height - returns the height of the box
+ * (vertical magnitude).
*/
-double *box_height(BOX *box)
+double *
+box_height(BOX * box)
{
- double *result = PALLOCTYPE(double);
+ double *result = PALLOCTYPE(double);
+
+ *result = box->high.y - box->low.y;
- *result = box->high.y - box->low.y;
-
- return(result);
+ return (result);
}
-/* box_distance - returns the distance between the
- * center points of two boxes.
+/* box_distance - returns the distance between the
+ * center points of two boxes.
*/
-double *box_distance(BOX *box1, BOX *box2)
+double *
+box_distance(BOX * box1, BOX * box2)
{
- double *result = PALLOCTYPE(double);
- Point *a, *b;
-
- a = box_center(box1);
- b = box_center(box2);
- *result = HYPOT(a->x - b->x, a->y - b->y);
-
- PFREE(a);
- PFREE(b);
- return(result);
+ double *result = PALLOCTYPE(double);
+ Point *a,
+ *b;
+
+ a = box_center(box1);
+ b = box_center(box2);
+ *result = HYPOT(a->x - b->x, a->y - b->y);
+
+ PFREE(a);
+ PFREE(b);
+ return (result);
}
-/* box_center - returns the center point of the box.
+/* box_center - returns the center point of the box.
*/
-Point *box_center(BOX *box)
+Point *
+box_center(BOX * box)
{
- Point *result = PALLOCTYPE(Point);
+ Point *result = PALLOCTYPE(Point);
- result->x = (box->high.x + box->low.x) / 2.0;
- result->y = (box->high.y + box->low.y) / 2.0;
-
- return(result);
+ result->x = (box->high.x + box->low.x) / 2.0;
+ result->y = (box->high.y + box->low.y) / 2.0;
+
+ return (result);
}
-/* box_ar - returns the area of the box.
+/* box_ar - returns the area of the box.
*/
-static double box_ar(BOX *box)
+static double
+box_ar(BOX * box)
{
- return( box_wd(box) * box_ht(box) );
+ return (box_wd(box) * box_ht(box));
}
-/* box_wd - returns the width (length) of the box
- * (horizontal magnitude).
+/* box_wd - returns the width (length) of the box
+ * (horizontal magnitude).
*/
-static double box_wd(BOX *box)
+static double
+box_wd(BOX * box)
{
- return( box->high.x - box->low.x );
+ return (box->high.x - box->low.x);
}
-/* box_ht - returns the height of the box
- * (vertical magnitude).
+/* box_ht - returns the height of the box
+ * (vertical magnitude).
*/
-static double box_ht(BOX *box)
+static double
+box_ht(BOX * box)
{
- return( box->high.y - box->low.y );
+ return (box->high.y - box->low.y);
}
-/* box_dt - returns the distance between the
- * center points of two boxes.
+/* box_dt - returns the distance between the
+ * center points of two boxes.
*/
#ifdef NOT_USED
-static double box_dt(BOX *box1, BOX *box2)
-{
- double result;
- Point *a, *b;
-
- a = box_center(box1);
- b = box_center(box2);
- result = HYPOT(a->x - b->x, a->y - b->y);
-
- PFREE(a);
- PFREE(b);
- return(result);
+static double
+box_dt(BOX * box1, BOX * box2)
+{
+ double result;
+ Point *a,
+ *b;
+
+ a = box_center(box1);
+ b = box_center(box2);
+ result = HYPOT(a->x - b->x, a->y - b->y);
+
+ PFREE(a);
+ PFREE(b);
+ return (result);
}
+
#endif
/*----------------------------------------------------------
- * Funky operations.
+ * Funky operations.
*---------------------------------------------------------*/
-/* box_intersect -
- * returns the overlapping portion of two boxes,
- * or NULL if they do not intersect.
+/* box_intersect -
+ * returns the overlapping portion of two boxes,
+ * or NULL if they do not intersect.
*/
-BOX *box_intersect(BOX *box1, BOX *box2)
+BOX *
+box_intersect(BOX * box1, BOX * box2)
{
- BOX *result;
+ BOX *result;
+
+ if (!box_overlap(box1, box2))
+ return (NULL);
- if (! box_overlap(box1,box2))
- return(NULL);
+ result = PALLOCTYPE(BOX);
- result = PALLOCTYPE(BOX);
+ result->high.x = Min(box1->high.x, box2->high.x);
+ result->low.x = Max(box1->low.x, box2->low.x);
+ result->high.y = Min(box1->high.y, box2->high.y);
+ result->low.y = Max(box1->low.y, box2->low.y);
- result->high.x = Min(box1->high.x, box2->high.x);
- result->low.x = Max(box1->low.x, box2->low.x);
- result->high.y = Min(box1->high.y, box2->high.y);
- result->low.y = Max(box1->low.y, box2->low.y);
-
- return(result);
+ return (result);
}
-/* box_diagonal -
- * returns a line segment which happens to be the
- * positive-slope diagonal of "box".
- * provided, of course, we have LSEGs.
+/* box_diagonal -
+ * returns a line segment which happens to be the
+ * positive-slope diagonal of "box".
+ * provided, of course, we have LSEGs.
*/
-LSEG *box_diagonal(BOX *box)
+LSEG *
+box_diagonal(BOX * box)
{
- Point p1, p2;
-
- p1.x = box->high.x;
- p1.y = box->high.y;
- p2.x = box->low.x;
- p2.y = box->low.y;
- return( lseg_construct( &p1, &p2 ) );
-
+ Point p1,
+ p2;
+
+ p1.x = box->high.x;
+ p1.y = box->high.y;
+ p2.x = box->low.x;
+ p2.y = box->low.y;
+ return (lseg_construct(&p1, &p2));
+
}
/***********************************************************************
**
- ** Routines for 2D lines.
- ** Lines are not intended to be used as ADTs per se,
- ** but their ops are useful tools for other ADT ops. Thus,
- ** there are few relops.
+ ** Routines for 2D lines.
+ ** Lines are not intended to be used as ADTs per se,
+ ** but their ops are useful tools for other ADT ops. Thus,
+ ** there are few relops.
**
***********************************************************************/
/*----------------------------------------------------------
- * Conversion routines from one line formula to internal.
- * Internal form: Ax+By+C=0
+ * Conversion routines from one line formula to internal.
+ * Internal form: Ax+By+C=0
*---------------------------------------------------------*/
-static LINE * /* point-slope */
-line_construct_pm(Point *pt, double m)
+static LINE * /* point-slope */
+line_construct_pm(Point * pt, double m)
{
- LINE *result = PALLOCTYPE(LINE);
+ LINE *result = PALLOCTYPE(LINE);
- /* use "mx - y + yinter = 0" */
- result->A = m;
- result->B = -1.0;
- result->C = pt->y - m * pt->x;
+ /* use "mx - y + yinter = 0" */
+ result->A = m;
+ result->B = -1.0;
+ result->C = pt->y - m * pt->x;
- result->m = m;
+ result->m = m;
- return(result);
-} /* line_construct_pm() */
+ return (result);
+} /* line_construct_pm() */
-static LINE * /* two points */
-line_construct_pp(Point *pt1, Point *pt2)
+static LINE * /* two points */
+line_construct_pp(Point * pt1, Point * pt2)
{
- LINE *result = PALLOCTYPE(LINE);
+ LINE *result = PALLOCTYPE(LINE);
- if (FPeq(pt1->x, pt2->x)) { /* vertical */
- /* use "x = C" */
- result->A = -1;
- result->B = 0;
- result->C = pt1->x;
+ if (FPeq(pt1->x, pt2->x))
+ { /* vertical */
+ /* use "x = C" */
+ result->A = -1;
+ result->B = 0;
+ result->C = pt1->x;
#ifdef GEODEBUG
-printf( "line_construct_pp- line is vertical\n");
+ printf("line_construct_pp- line is vertical\n");
#endif
- result->m = DBL_MAX;
+ result->m = DBL_MAX;
- } else if (FPeq(pt1->y, pt2->y)) { /* horizontal */
- /* use "x = C" */
- result->A = 0;
- result->B = -1;
- result->C = pt1->y;
+ }
+ else if (FPeq(pt1->y, pt2->y))
+ { /* horizontal */
+ /* use "x = C" */
+ result->A = 0;
+ result->B = -1;
+ result->C = pt1->y;
#ifdef GEODEBUG
-printf( "line_construct_pp- line is horizontal\n");
+ printf("line_construct_pp- line is horizontal\n");
#endif
- result->m = 0.0;
+ result->m = 0.0;
- } else {
- /* use "mx - y + yinter = 0" */
+ }
+ else
+ {
+ /* use "mx - y + yinter = 0" */
#if FALSE
- result->A = (pt1->y - pt2->y) / (pt1->x - pt2->x);
+ result->A = (pt1->y - pt2->y) / (pt1->x - pt2->x);
#endif
- result->A = (pt2->y - pt1->y) / (pt2->x - pt1->x);
- result->B = -1.0;
- result->C = pt1->y - result->A * pt1->x;
+ result->A = (pt2->y - pt1->y) / (pt2->x - pt1->x);
+ result->B = -1.0;
+ result->C = pt1->y - result->A * pt1->x;
#ifdef GEODEBUG
-printf( "line_construct_pp- line is neither vertical nor horizontal (diffs x=%.*g, y=%.*g\n",
- digits8, (pt2->x - pt1->x), digits8, (pt2->y - pt1->y));
+ printf("line_construct_pp- line is neither vertical nor horizontal (diffs x=%.*g, y=%.*g\n",
+ digits8, (pt2->x - pt1->x), digits8, (pt2->y - pt1->y));
#endif
- result->m = result->A;
- }
- return(result);
-} /* line_construct_pp() */
+ result->m = result->A;
+ }
+ return (result);
+} /* line_construct_pp() */
/*----------------------------------------------------------
- * Relative position routines.
+ * Relative position routines.
*---------------------------------------------------------*/
-static bool line_intersect(LINE *l1, LINE *l2)
+static bool
+line_intersect(LINE * l1, LINE * l2)
{
- return( ! line_parallel(l1, l2) );
+ return (!line_parallel(l1, l2));
}
-static bool line_parallel(LINE *l1, LINE *l2)
+static bool
+line_parallel(LINE * l1, LINE * l2)
{
#if FALSE
- return( FPeq(l1->m, l2->m) );
+ return (FPeq(l1->m, l2->m));
#endif
- if (FPzero(l1->B)) {
- return(FPzero(l2->B));
- }
+ if (FPzero(l1->B))
+ {
+ return (FPzero(l2->B));
+ }
- return(FPeq(l2->A, l1->A*(l2->B / l1->B)));
-} /* line_parallel() */
+ return (FPeq(l2->A, l1->A * (l2->B / l1->B)));
+} /* line_parallel() */
#ifdef NOT_USED
-bool line_perp(LINE *l1, LINE *l2)
+bool
+line_perp(LINE * l1, LINE * l2)
{
#if FALSE
- if (l1->m)
- return( FPeq(l2->m / l1->m, -1.0) );
- else if (l2->m)
- return( FPeq(l1->m / l2->m, -1.0) );
+ if (l1->m)
+ return (FPeq(l2->m / l1->m, -1.0));
+ else if (l2->m)
+ return (FPeq(l1->m / l2->m, -1.0));
#endif
- if (FPzero(l1->A)) {
- return( FPzero(l2->B) );
- } else if (FPzero(l1->B)) {
- return( FPzero(l2->A) );
- }
-
- return( FPeq(((l1->A * l2->B) / (l1->B * l2->A)), -1.0) );
-} /* line_perp() */
+ if (FPzero(l1->A))
+ {
+ return (FPzero(l2->B));
+ }
+ else if (FPzero(l1->B))
+ {
+ return (FPzero(l2->A));
+ }
+
+ return (FPeq(((l1->A * l2->B) / (l1->B * l2->A)), -1.0));
+} /* line_perp() */
+
#endif
-static bool line_vertical(LINE *line)
+static bool
+line_vertical(LINE * line)
{
#if FALSE
- return( FPeq(line->A, -1.0) && FPzero(line->B) );
+ return (FPeq(line->A, -1.0) && FPzero(line->B));
#endif
- return( FPzero(line->B) );
-} /* line_vertical() */
+ return (FPzero(line->B));
+} /* line_vertical() */
-static bool line_horizontal(LINE *line)
+static bool
+line_horizontal(LINE * line)
{
#if FALSE
- return( FPzero(line->m) );
+ return (FPzero(line->m));
#endif
- return( FPzero(line->A) );
-} /* line_horizontal() */
+ return (FPzero(line->A));
+} /* line_horizontal() */
#ifdef NOT_USED
-bool line_eq(LINE *l1, LINE *l2)
-{
- double k;
-
- if (! FPzero(l2->A))
- k = l1->A / l2->A;
- else if (! FPzero(l2->B))
- k = l1->B / l2->B;
- else if (! FPzero(l2->C))
- k = l1->C / l2->C;
- else
- k = 1.0;
-
- return( FPeq(l1->A, k * l2->A) &&
- FPeq(l1->B, k * l2->B) &&
- FPeq(l1->C, k * l2->C) );
+bool
+line_eq(LINE * l1, LINE * l2)
+{
+ double k;
+
+ if (!FPzero(l2->A))
+ k = l1->A / l2->A;
+ else if (!FPzero(l2->B))
+ k = l1->B / l2->B;
+ else if (!FPzero(l2->C))
+ k = l1->C / l2->C;
+ else
+ k = 1.0;
+
+ return (FPeq(l1->A, k * l2->A) &&
+ FPeq(l1->B, k * l2->B) &&
+ FPeq(l1->C, k * l2->C));
}
+
#endif
/*----------------------------------------------------------
- * Line arithmetic routines.
+ * Line arithmetic routines.
*---------------------------------------------------------*/
-double * /* distance between l1, l2 */
-line_distance(LINE *l1, LINE *l2)
-{
- double *result = PALLOCTYPE(double);
- Point *tmp;
-
- if (line_intersect(l1, l2)) {
- *result = 0.0;
- return(result);
- }
- if (line_vertical(l1))
- *result = fabs(l1->C - l2->C);
- else {
- tmp = point_construct(0.0, l1->C);
- result = dist_pl(tmp, l2);
- PFREE(tmp);
- }
- return(result);
+double * /* distance between l1, l2 */
+line_distance(LINE * l1, LINE * l2)
+{
+ double *result = PALLOCTYPE(double);
+ Point *tmp;
+
+ if (line_intersect(l1, l2))
+ {
+ *result = 0.0;
+ return (result);
+ }
+ if (line_vertical(l1))
+ *result = fabs(l1->C - l2->C);
+ else
+ {
+ tmp = point_construct(0.0, l1->C);
+ result = dist_pl(tmp, l2);
+ PFREE(tmp);
+ }
+ return (result);
}
/* line_interpt()
* Point where two lines l1, l2 intersect (if any)
*/
-static Point *
-line_interpt(LINE *l1, LINE *l2)
+static Point *
+line_interpt(LINE * l1, LINE * l2)
{
- Point *result;
- double x, y;
-
- if (line_parallel(l1, l2))
- return(NULL);
+ Point *result;
+ double x,
+ y;
+
+ if (line_parallel(l1, l2))
+ return (NULL);
#if FALSE
- if (line_vertical(l1))
- result = point_construct(l2->m * l1->C + l2->C, l1->C);
- else if (line_vertical(l2))
- result = point_construct(l1->m * l2->C + l1->C, l2->C);
- else {
- x = (l1->C - l2->C) / (l2->A - l1->A);
- result = point_construct(x, l1->m * x + l1->C);
- }
+ if (line_vertical(l1))
+ result = point_construct(l2->m * l1->C + l2->C, l1->C);
+ else if (line_vertical(l2))
+ result = point_construct(l1->m * l2->C + l1->C, l2->C);
+ else
+ {
+ x = (l1->C - l2->C) / (l2->A - l1->A);
+ result = point_construct(x, l1->m * x + l1->C);
+ }
#endif
- if (line_vertical(l1)) {
+ if (line_vertical(l1))
+ {
#if FALSE
- x = l1->C;
- y = -((l2->A * x + l2->C) / l2->B);
+ x = l1->C;
+ y = -(