geo_ops.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * geo_ops.c
 *	  2D geometric operations
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/utils/adt/geo_ops.c,v 1.41.2.1 1999/08/02 05:24:52 scrappy Exp $
 *
 *-------------------------------------------------------------------------
 */
#include <math.h>
#include <limits.h>
#include <float.h>
#include <ctype.h>

#include "postgres.h"

#include "utils/geo_decls.h"

#ifndef PI
#define PI 3.1415926536
#endif

/*
 * Internal routines
 */

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 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);


/*
 * Delimiters for input and output strings.
 * LDELIM, RDELIM, and DELIM are left, right, and separator delimiters, respectively.
 * 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		'>'

/* Maximum number of output digits printed */
#define P_MAXDIG DBL_DIG
#define P_MAXLEN (2*(P_MAXDIG+7)+1)

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.
 * 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).
 *
 * 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))
 *
 * 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.
 *
 * 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
 */

static int
single_decode(char *str, float8 *x, char **s)
{
	char	   *cp;

	if (!PointerIsValid(str))
		return FALSE;

	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);
#endif
	if (cp <= str)
		return FALSE;
	while (isspace(*cp))
		cp++;

	if (s != NULL)
		*s = cp;

	return TRUE;
}	/* single_decode() */

static int
single_encode(float8 x, char *str)
{
	sprintf(str, "%.*g", digits8, x);
	return TRUE;
}	/* single_encode() */

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;
}

static int
pair_encode(float8 x, float8 y, char *str)
{
	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++;

	}
	else if (*s == LDELIM)
	{
		cp = (s + 1);
		while (isspace(*cp))
			cp++;
		if (*cp == LDELIM)
		{
#ifdef NOT_USED
			/* nested delimiters with only one point? */
			if (npts <= 1)
				return FALSE;
#endif
			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;

		if (*s == DELIM)
			s++;
		p++;
	}

	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;
	}

	for (i = 0; i < npts; i++)
	{
		*cp++ = LDELIM;
		if (!pair_encode(pt->x, pt->y, cp))
			elog(ERROR, "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() */

/*-------------------------------------------------------------
 * pair_count - count the number of points
 * allow the following notation:
 * '((1,2),(3,4))'
 * '(1,3,2,4)'
 * require an odd number of delim characters in the string
 *-------------------------------------------------------------*/
static int
pair_count(char *s, char delim)
{
	int			ndelim = 0;

	while ((s = strchr(s, delim)) != NULL)
	{
		ndelim++;
		s++;
	}
	return (ndelim % 2) ? ((ndelim + 1) / 2) : -1;
}

/***********************************************************************
 **
 **		Routines for two-dimensional boxes.
 **
 ***********************************************************************/

/*----------------------------------------------------------
 * Formatting and conversion routines.
 *---------------------------------------------------------*/

/*		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)"
 */
BOX *
box_in(char *str)
{
	BOX		   *box = palloc(sizeof(BOX));

	int			isopen;
	char	   *s;
	double		x,
				y;

	if (!PointerIsValid(str))
		elog(ERROR, " Bad (null) box external representation", NULL);

	if ((!path_decode(FALSE, 2, str, &isopen, &s, &(box->high)))
		|| (*s != '\0'))
		elog(ERROR, "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;
	}

	return box;
}	/* box_in() */

/*		box_out -		convert a box to external form.
 */
char *
box_out(BOX *box)
{
	if (!PointerIsValid(box))
		return NULL;

	return path_encode(-1, 2, (Point *) &(box->high));
}	/* box_out() */


/*		box_construct	-		fill in a new box.
 */
static BOX *
box_construct(double x1, double x2, double y1, double y2)
{
	BOX		   *result = palloc(sizeof(BOX));

	return box_fill(result, x1, x2, y1, y2);
}


/*		box_fill		-		fill in a static box
 */
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;
}


/*		box_copy		-		copy a box
 */
static BOX *
box_copy(BOX *box)
{
	BOX		   *result = palloc(sizeof(BOX));

	memmove((char *) result, (char *) box, sizeof(BOX));

	return result;
}


/*----------------------------------------------------------
 *	Relational operators for BOXes.
 *		<, >, <=, >=, and == are based on box area.
 *---------------------------------------------------------*/

/*		box_same		-		are two boxes identical?
 */
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)));
}

/*		box_overlap		-		does box1 overlap 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))));
}

/*		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.
 */
bool
box_overleft(BOX *box1, BOX *box2)
{
	return FPle(box1->high.x, box2->high.x);
}

/*		box_left		-		is box1 strictly left of box2?
 */
bool
box_left(BOX *box1, BOX *box2)
{
	return FPlt(box1->high.x, box2->low.x);
}

/*		box_right		-		is box1 strictly right of box2?
 */
bool
box_right(BOX *box1, BOX *box2)
{
	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?
 *
 *		This is "greater than or equal" for time ranges, when time ranges
 *		are stored as rectangles.
 */
bool
box_overright(BOX *box1, BOX *box2)
{
	return box1->low.x >= box2->low.x;
}

/*		box_contained	-		is box1 contained by 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)));
}

/*		box_contain		-		does box1 contain 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)));
}


/*		box_positionop	-
 *				is box1 entirely {above,below} box2?
 */
bool
box_below(BOX *box1, BOX *box2)
{
	return FPle(box1->high.y, box2->low.y);
}

bool
box_above(BOX *box1, BOX *box2)
{
	return FPge(box1->low.y, box2->high.y);
}


/*		box_relop		-		is area(box1) relop area(box2), within
 *								our accuracy constraint?
 */
bool
box_lt(BOX *box1, BOX *box2)
{
	return FPlt(box_ar(box1), box_ar(box2));
}

bool
box_gt(BOX *box1, BOX *box2)
{
	return FPgt(box_ar(box1), box_ar(box2));
}

bool
box_eq(BOX *box1, BOX *box2)
{
	return FPeq(box_ar(box1), box_ar(box2));
}

bool
box_le(BOX *box1, BOX *box2)
{
	return FPle(box_ar(box1), box_ar(box2));
}

bool
box_ge(BOX *box1, BOX *box2)
{
	return FPge(box_ar(box1), box_ar(box2));
}


/*----------------------------------------------------------
 *	"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_area		-		returns the area of the box.
 */
double *
box_area(BOX *box)
{
	double	   *result = palloc(sizeof(double));

	*result = box_wd(box) * box_ht(box);

	return result;
}


/*		box_width		-		returns the width of the box
 *								  (horizontal magnitude).
 */
double *
box_width(BOX *box)
{
	double	   *result = palloc(sizeof(double));

	*result = box->high.x - box->low.x;

	return result;
}	/* box_width() */


/*		box_height		-		returns the height of the box
 *								  (vertical magnitude).
 */
double *
box_height(BOX *box)
{
	double	   *result = palloc(sizeof(double));

	*result = box->high.y - box->low.y;

	return result;
}