From c5001b20001e9fdbe30b68f95d31c6da03fc3cfd Mon Sep 17 00:00:00 2001 From: Paul Ramsey Date: Sat, 25 Jun 2011 22:36:51 +0000 Subject: [PATCH] Prototype segmentation code and move lwalgorith.h prototypes into liblwgeom.h and liblwgeom_internal.h git-svn-id: http://svn.osgeo.org/postgis/trunk@7487 b70326c6-7e19-0410-871a-916f4a2858ee --- liblwgeom/Makefile.in | 1 - liblwgeom/cunit/cu_algorithm.c | 1 - liblwgeom/g_box.c | 8 --- liblwgeom/liblwgeom.h | 33 +++++++++++ liblwgeom/liblwgeom_internal.h | 54 ++++++++++++++++++ liblwgeom/lwalgorithm.c | 11 +++- liblwgeom/lwalgorithm.h | 51 ----------------- liblwgeom/lwsegmentize.c | 88 +++++++++++++++++++++++++++-- liblwgeom/lwtree.c | 1 - postgis/lwgeom_functions_analytic.c | 1 - postgis/lwgeom_functions_basic.c | 1 - postgis/lwgeom_geos_split.c | 1 - 12 files changed, 181 insertions(+), 70 deletions(-) delete mode 100644 liblwgeom/lwalgorithm.h diff --git a/liblwgeom/Makefile.in b/liblwgeom/Makefile.in index bb10d47de..a233a8e11 100644 --- a/liblwgeom/Makefile.in +++ b/liblwgeom/Makefile.in @@ -75,7 +75,6 @@ NM_OBJS = \ SA_HEADERS = \ liblwgeom.h \ liblwgeom_internal.h \ - lwalgorithm.h \ libtgeom.h all: liblwgeom.a diff --git a/liblwgeom/cunit/cu_algorithm.c b/liblwgeom/cunit/cu_algorithm.c index e03099e3c..5aba73dd7 100644 --- a/liblwgeom/cunit/cu_algorithm.c +++ b/liblwgeom/cunit/cu_algorithm.c @@ -16,7 +16,6 @@ #include "CUnit/Basic.h" #include "liblwgeom_internal.h" -#include "lwalgorithm.h" #include "cu_tester.h" /* diff --git a/liblwgeom/g_box.c b/liblwgeom/g_box.c index 85292c246..d14a76c54 100644 --- a/liblwgeom/g_box.c +++ b/liblwgeom/g_box.c @@ -10,7 +10,6 @@ **********************************************************************/ #include "liblwgeom_internal.h" -#include "lwalgorithm.h" #include #include @@ -337,13 +336,6 @@ size_t gbox_serialized_size(uchar flags) } -static inline int signum(double n) -{ - if( n < 0 ) return -1; - if( n > 0 ) return 1; - return 0; -} - /* ******************************************************************************** ** Compute cartesian bounding GBOX boxes from LWGEOM. */ diff --git a/liblwgeom/liblwgeom.h b/liblwgeom/liblwgeom.h index cf53d3a2f..02fcc5503 100644 --- a/liblwgeom/liblwgeom.h +++ b/liblwgeom/liblwgeom.h @@ -1775,6 +1775,39 @@ extern LWLINE *lwline_segmentize2d(LWLINE *line, double dist); extern LWPOLY *lwpoly_segmentize2d(LWPOLY *line, double dist); extern LWCOLLECTION *lwcollection_segmentize2d(LWCOLLECTION *coll, double dist); +/** +* Calculate the GeoHash (http://geohash.org) string for a geometry. Caller must free. +*/ +char *lwgeom_geohash(const LWGEOM *lwgeom, int precision); + + +/** +* The return values of lwline_crossing_direction() +*/ +enum CG_LINE_CROSS_TYPE { + LINE_NO_CROSS = 0, + LINE_CROSS_LEFT = -1, + LINE_CROSS_RIGHT = 1, + LINE_MULTICROSS_END_LEFT = -2, + LINE_MULTICROSS_END_RIGHT = 2, + LINE_MULTICROSS_END_SAME_FIRST_LEFT = -3, + LINE_MULTICROSS_END_SAME_FIRST_RIGHT = 3 +}; + +/** +* Given two lines, characterize how (and if) they cross each other +*/ +int lwline_crossing_direction(LWLINE *l1, LWLINE *l2); + +/** +* Clip a line based on the from/to range of one of its ordinates. Use for m- and z- clipping +*/ +LWCOLLECTION *lwline_clip_to_ordinate_range(LWLINE *line, int ordinate, double from, double to); + +/** +* Clip a multi-line based on the from/to range of one of its ordinates. Use for m- and z- clipping +*/ +LWCOLLECTION *lwmline_clip_to_ordinate_range(LWMLINE *mline, int ordinate, double from, double to); /* * Export functions diff --git a/liblwgeom/liblwgeom_internal.h b/liblwgeom/liblwgeom_internal.h index 9243435a8..088bb9509 100644 --- a/liblwgeom/liblwgeom_internal.h +++ b/liblwgeom/liblwgeom_internal.h @@ -21,6 +21,8 @@ #include #endif +#ifndef LIBLWGEOM_INTERNAL +#define LIBLWGEOM_INTERNAL /** * PI @@ -112,6 +114,57 @@ LWLINE* lwline_simplify(const LWLINE *iline, double dist); LWPOLY* lwpoly_simplify(const LWPOLY *ipoly, double dist); LWCOLLECTION* lwcollection_simplify(const LWCOLLECTION *igeom, double dist); +/* +* Computational geometry +*/ +int signum(double n); + +/* +* The possible ways a pair of segments can interact. Returned by lw_segment_intersects +*/ +enum CG_SEGMENT_INTERSECTION_TYPE { + SEG_ERROR = -1, + SEG_NO_INTERSECTION = 0, + SEG_COLINEAR = 1, + SEG_CROSS_LEFT = 2, + SEG_CROSS_RIGHT = 3, + SEG_TOUCH_LEFT = 4, + SEG_TOUCH_RIGHT = 5 +}; + +/* +* Do the segments intersect? How? +*/ +int lw_segment_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2); + +/* +* What side of the line formed by p1 and p2 does q fall? +* Returns < 0 for left and > 0 for right and 0 for co-linearity +*/ +double lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q); + +/* +* Do the envelopes of the the segments intersect? +*/ +int lw_segment_envelope_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2); + +/* +* Get/Set an enumeratoed ordinate. (x,y,z,m) +*/ +double lwpoint_get_ordinate(const POINT4D *p, int ordinate); +void lwpoint_set_ordinate(POINT4D *p, int ordinate, double value); + +/* +* Generate an interpolated coordinate p given an interpolation value and ordinate to apply it to +*/ +int lwpoint_interpolate(const POINT4D *p1, const POINT4D *p2, POINT4D *p, int ndims, int ordinate, double interpolation_value); + +/* +* Geohash +*/ +int lwgeom_geohash_precision(GBOX bbox, GBOX *bounds); +char *geohash_point(double longitude, double latitude, int precision); + /* * Point comparisons */ @@ -158,3 +211,4 @@ void ptarray_affine(POINTARRAY *pa, const AFFINE *affine); char ptarray_isccw(const POINTARRAY *pa); +#endif /* LIBLWGEOM_INTERNAL */ \ No newline at end of file diff --git a/liblwgeom/lwalgorithm.c b/liblwgeom/lwalgorithm.c index 7ba077317..18b1c177d 100644 --- a/liblwgeom/lwalgorithm.c +++ b/liblwgeom/lwalgorithm.c @@ -11,9 +11,18 @@ **********************************************************************/ #include "liblwgeom_internal.h" -#include "lwalgorithm.h" +/** +* Returns -1 if n < 0.0 and 1 if n > 0.0 +*/ +int signum(double n) +{ + if( n < 0 ) return -1; + if( n > 0 ) return 1; + return 0; +} + /** ** lw_segment_side() ** diff --git a/liblwgeom/lwalgorithm.h b/liblwgeom/lwalgorithm.h deleted file mode 100644 index 008d1ef12..000000000 --- a/liblwgeom/lwalgorithm.h +++ /dev/null @@ -1,51 +0,0 @@ -/********************************************************************** - * $Id$ - * - * PostGIS - Spatial Types for PostgreSQL - * http://postgis.refractions.net - * Copyright 2008 Paul Ramsey - * - * This is free software; you can redistribute and/or modify it under - * the terms of the GNU General Public Licence. See the COPYING file. - * - **********************************************************************/ - -#include - -enum CG_SEGMENT_INTERSECTION_TYPE { - SEG_ERROR = -1, - SEG_NO_INTERSECTION = 0, - SEG_COLINEAR = 1, - SEG_CROSS_LEFT = 2, - SEG_CROSS_RIGHT = 3, - SEG_TOUCH_LEFT = 4, - SEG_TOUCH_RIGHT = 5 -}; - -double lw_segment_side(const POINT2D *p1, const POINT2D *p2, const POINT2D *q); -int lw_segment_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2); -int lw_segment_envelope_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2); - - -enum CG_LINE_CROSS_TYPE { - LINE_NO_CROSS = 0, - LINE_CROSS_LEFT = -1, - LINE_CROSS_RIGHT = 1, - LINE_MULTICROSS_END_LEFT = -2, - LINE_MULTICROSS_END_RIGHT = 2, - LINE_MULTICROSS_END_SAME_FIRST_LEFT = -3, - LINE_MULTICROSS_END_SAME_FIRST_RIGHT = 3 -}; - -int lwline_crossing_direction(LWLINE *l1, LWLINE *l2); - -double lwpoint_get_ordinate(const POINT4D *p, int ordinate); -void lwpoint_set_ordinate(POINT4D *p, int ordinate, double value); -int lwpoint_interpolate(const POINT4D *p1, const POINT4D *p2, POINT4D *p, int ndims, int ordinate, double interpolation_value); -LWCOLLECTION *lwline_clip_to_ordinate_range(LWLINE *line, int ordinate, double from, double to); -LWCOLLECTION *lwmline_clip_to_ordinate_range(LWMLINE *mline, int ordinate, double from, double to); - -int lwgeom_geohash_precision(GBOX bbox, GBOX *bounds); -char *lwgeom_geohash(const LWGEOM *lwgeom, int precision); -char *geohash_point(double longitude, double latitude, int precision); - diff --git a/liblwgeom/lwsegmentize.c b/liblwgeom/lwsegmentize.c index 2affdf3a3..d1621c894 100644 --- a/liblwgeom/lwsegmentize.c +++ b/liblwgeom/lwsegmentize.c @@ -158,10 +158,10 @@ lwcircle_segmentize(POINT4D *p1, POINT4D *p2, POINT4D *p3, uint32 perQuad) uchar *pt; POINT4D center; - double radius = 0.0, - sweep = 0.0, - angle = 0.0, - increment = 0.0; + double radius = 0.0; + double sweep = 0.0; + double angle = 0.0; + double increment = 0.0; double a1, a2, a3, i; LWDEBUG(2, "lwcircle_segmentize called. "); @@ -282,6 +282,86 @@ lwcircle_segmentize(POINT4D *p1, POINT4D *p2, POINT4D *p3, uint32 perQuad) return result; } +POINTARRAY * +lwcircle_segmentize2(POINT4D *p1, POINT4D *p2, POINT4D *p3, uint32 perQuad) +{ + POINT4D center; + POINT4D pt, pt_start, pt_end; + int p2_side = 0; + double radius; /* Arc radius */ + double increment; /* Angle per segment */ + double a1, a2, a3, angle; + POINTARRAY *pa; + int result; + + LWDEBUG(2, "lwcircle_calculate_gbox called."); + + radius = lwcircle_center(p1, p2, p3, ¢er); + + /* Negative radius signals straight line, p1/p2/p3 are colinear */ + if (radius < 0.0) + { + /* TODO return straight line from p1 to p3 */ + return NULL; + } + + /* Matched start/end points imply circle */ + if ( p1->x == p3->x && p1->y == p3->y ) + { + /* TODO return circle */ + return NULL; + } + + /* The side of the p1/p3 line that p2 falls on dictates the sweep + direction from p1 to p3. */ + p2_side = signum(lw_segment_side((POINT2D*)p1, (POINT2D*)p3, (POINT2D*)p2)); + increment = fabs(M_PI_2 / perQuad); + + /* Angles of each point that defines the arc section */ + a1 = atan2(p1->y - center.y, p1->x - center.x); + a2 = atan2(p2->y - center.y, p2->x - center.x); + a3 = atan2(p3->y - center.y, p3->x - center.x); + + /* p2 on left side => Clockwise sweep */ + if ( p2_side == -1 ) + { + /* Swap a1/a3 so we can use an anti-clockwise (positive) sweep */ + double tmp = a3; + a3 = a1; + a1 = tmp; + pt_start = *p3; + pt_end = *p1; + } + else + { + pt_start = *p1; + pt_end = *p3; + } + + /* Adjust a3 up so we can increment from a1 to a3 cleanly */ + if ( a3 < a1 ) + { + a3 += 2.0 * M_PI; + } + + /* Initialize point array */ + pa = ptarray_construct_empty(0, 0, 32); + /* Add in start point */ + result = ptarray_append_point(pa, &pt_start, LW_FALSE); + /* Sweep from a1 to a3 */ + for( angle = a1 + increment; angle < a3; angle += increment ) + { + pt.x = center.x + radius * cos(angle); + pt.y = center.y + radius * sin(angle); + result = ptarray_append_point(pa, &pt, LW_FALSE); + } + /* Add in the end point */ + result = ptarray_append_point(pa, &pt_end, LW_FALSE); + + return pa; +} + + LWLINE * lwcircstring_segmentize(const LWCIRCSTRING *icurve, uint32 perQuad) { diff --git a/liblwgeom/lwtree.c b/liblwgeom/lwtree.c index 8b4405b17..ffdf3091d 100644 --- a/liblwgeom/lwtree.c +++ b/liblwgeom/lwtree.c @@ -1,5 +1,4 @@ #include "liblwgeom_internal.h" -#include "lwalgorithm.h" #include "lwtree.h" diff --git a/postgis/lwgeom_functions_analytic.c b/postgis/lwgeom_functions_analytic.c index d65821f54..5c521a30c 100644 --- a/postgis/lwgeom_functions_analytic.c +++ b/postgis/lwgeom_functions_analytic.c @@ -16,7 +16,6 @@ #include "lwgeom_pg.h" #include "math.h" #include "lwgeom_rtree.h" -#include "lwalgorithm.h" #include "lwgeom_functions_analytic.h" diff --git a/postgis/lwgeom_functions_basic.c b/postgis/lwgeom_functions_basic.c index 8f2ce0b5c..796389bf8 100644 --- a/postgis/lwgeom_functions_basic.c +++ b/postgis/lwgeom_functions_basic.c @@ -18,7 +18,6 @@ #include "liblwgeom_internal.h" #include "libtgeom.h" -#include "lwalgorithm.h" #include "lwgeom_pg.h" #include "profile.h" diff --git a/postgis/lwgeom_geos_split.c b/postgis/lwgeom_geos_split.c index 0759e5df9..67a62feef 100644 --- a/postgis/lwgeom_geos_split.c +++ b/postgis/lwgeom_geos_split.c @@ -37,7 +37,6 @@ **********************************************************************/ #include "lwgeom_geos.h" -#include "lwalgorithm.h" #include "funcapi.h" #include -- 2.50.1