PostGIS  2.2.7dev-r@@SVN_REVISION@@
lwgeom_geos_node.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * Copyright (C) 2011 Sandro Santilli <strk@keybit.net>
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU General Public Licence. See the COPYING file.
10  *
11  **********************************************************************
12  *
13  * Node a set of linestrings
14  *
15  **********************************************************************/
16 
17 #include "lwgeom_geos.h"
18 #include "liblwgeom_internal.h"
19 
20 #include <string.h>
21 #include <assert.h>
22 
23 static int
25 {
27  if ( c ) return c->ngeoms;
28  else return 1;
29 }
30 
31 static const LWGEOM*
32 lwgeom_subgeom(const LWGEOM* g, int n)
33 {
35  if ( c ) return lwcollection_getsubgeom((LWCOLLECTION*)c, n);
36  else return g;
37 }
38 
39 
40 static void
42 {
43  int i, n;
44  LWLINE* l;
45 
46  switch (lwg->type)
47  {
48  case MULTILINETYPE:
49  for ( i = 0,
50  n = lwgeom_ngeoms(lwg);
51  i < n; ++i )
52  {
54  lwgeom_subgeom(lwg, i),
55  col);
56  }
57  break;
58  case LINETYPE:
59  l = (LWLINE*)lwg;
60  col = lwmpoint_add_lwpoint(col,
61  lwline_get_lwpoint(l, 0));
62  col = lwmpoint_add_lwpoint(col,
64  break;
65  default:
66  lwerror("lwgeom_collect_endpoints: invalid type %s",
67  lwtype_name(lwg->type));
68  break;
69  }
70 }
71 
72 static LWMPOINT*
74 {
76  FLAGS_GET_Z(lwg->flags),
77  FLAGS_GET_M(lwg->flags));
78  lwgeom_collect_endpoints(lwg, col);
79 
80  return col;
81 }
82 
83 /* Assumes initGEOS was called already */
84 /* May return LWPOINT or LWMPOINT */
85 static LWGEOM*
87 {
88 #if POSTGIS_GEOS_VERSION < 33
89  lwerror("The GEOS version this postgis binary "
90  "was compiled against (%d) doesn't support "
91  "'GEOSUnaryUnion' function (3.3.0+ required)",
93  return NULL;
94 #else /* POSTGIS_GEOS_VERSION >= 33 */
95  LWGEOM* ret;
96  GEOSGeometry *gepu;
97  LWMPOINT *epall = lwgeom_extract_endpoints(lwg);
98  GEOSGeometry *gepall = LWGEOM2GEOS((LWGEOM*)epall, 1);
99  lwmpoint_free(epall);
100  if ( ! gepall ) {
101  lwerror("LWGEOM2GEOS: %s", lwgeom_geos_errmsg);
102  return NULL;
103  }
104 
105  /* UnaryUnion to remove duplicates */
106  /* TODO: do it all within pgis using indices */
107  gepu = GEOSUnaryUnion(gepall);
108  if ( ! gepu ) {
109  GEOSGeom_destroy(gepall);
110  lwerror("GEOSUnaryUnion: %s", lwgeom_geos_errmsg);
111  return NULL;
112  }
113  GEOSGeom_destroy(gepall);
114 
115  ret = GEOS2LWGEOM(gepu, FLAGS_GET_Z(lwg->flags));
116  GEOSGeom_destroy(gepu);
117  if ( ! ret ) {
118  lwerror("Error during GEOS2LWGEOM");
119  return NULL;
120  }
121 
122  return ret;
123 #endif /* POSTGIS_GEOS_VERSION >= 33 */
124 }
125 
126 /* exported */
127 extern LWGEOM* lwgeom_node(const LWGEOM* lwgeom_in);
128 LWGEOM*
129 lwgeom_node(const LWGEOM* lwgeom_in)
130 {
131 #if POSTGIS_GEOS_VERSION < 33
132  lwerror("The GEOS version this postgis binary "
133  "was compiled against (%d) doesn't support "
134  "'GEOSUnaryUnion' function (3.3.0+ required)",
136  return NULL;
137 #else /* POSTGIS_GEOS_VERSION >= 33 */
138  GEOSGeometry *g1, *gu, *gm;
139  LWGEOM *ep, *lines;
140  LWCOLLECTION *col, *tc;
141  int pn, ln, np, nl;
142 
143  if ( lwgeom_dimension(lwgeom_in) != 1 ) {
144  lwerror("Noding geometries of dimension != 1 is unsupported");
145  return NULL;
146  }
147 
149  g1 = LWGEOM2GEOS(lwgeom_in, 1);
150  if ( ! g1 ) {
151  lwerror("LWGEOM2GEOS: %s", lwgeom_geos_errmsg);
152  return NULL;
153  }
154 
155  ep = lwgeom_extract_unique_endpoints(lwgeom_in);
156  if ( ! ep ) {
157  GEOSGeom_destroy(g1);
158  lwerror("Error extracting unique endpoints from input");
159  return NULL;
160  }
161 
162  /* Unary union input to fully node */
163  gu = GEOSUnaryUnion(g1);
164  GEOSGeom_destroy(g1);
165  if ( ! gu ) {
166  lwgeom_free(ep);
167  lwerror("GEOSUnaryUnion: %s", lwgeom_geos_errmsg);
168  return NULL;
169  }
170 
171  /* Linemerge (in case of overlaps) */
172  gm = GEOSLineMerge(gu);
173  GEOSGeom_destroy(gu);
174  if ( ! gm ) {
175  lwgeom_free(ep);
176  lwerror("GEOSLineMerge: %s", lwgeom_geos_errmsg);
177  return NULL;
178  }
179 
180  lines = GEOS2LWGEOM(gm, FLAGS_GET_Z(lwgeom_in->flags));
181  GEOSGeom_destroy(gm);
182  if ( ! lines ) {
183  lwgeom_free(ep);
184  lwerror("Error during GEOS2LWGEOM");
185  return NULL;
186  }
187 
188  /*
189  * Reintroduce endpoints from input, using split-line-by-point.
190  * Note that by now we can be sure that each point splits at
191  * most _one_ segment as any point shared by multiple segments
192  * would already be a node. Also we can be sure that any of
193  * the segments endpoints won't split any other segment.
194  * We can use the above 2 assertions to early exit the loop.
195  */
196 
198  FLAGS_GET_Z(lwgeom_in->flags),
199  FLAGS_GET_M(lwgeom_in->flags));
200 
201  np = lwgeom_ngeoms(ep);
202  for (pn=0; pn<np; ++pn) { /* for each point */
203 
204  const LWPOINT* p = (LWPOINT*)lwgeom_subgeom(ep, pn);
205 
206  nl = lwgeom_ngeoms(lines);
207  for (ln=0; ln<nl; ++ln) { /* for each line */
208 
209  const LWLINE* l = (LWLINE*)lwgeom_subgeom(lines, ln);
210 
211  int s = lwline_split_by_point_to(l, p, (LWMLINE*)col);
212 
213  if ( ! s ) continue; /* not on this line */
214 
215  if ( s == 1 ) {
216  /* found on this line, but not splitting it */
217  break;
218  }
219 
220  /* splits this line */
221 
222  /* replace this line with the two splits */
223  if ( lwgeom_is_collection(lines) ) {
224  tc = (LWCOLLECTION*)lines;
225  lwcollection_reserve(tc, nl + 1);
226  while (nl > ln+1) {
227  tc->geoms[nl] = tc->geoms[nl-1];
228  --nl;
229  }
230  lwgeom_free(tc->geoms[ln]);
231  tc->geoms[ln] = col->geoms[0];
232  tc->geoms[ln+1] = col->geoms[1];
233  tc->ngeoms++;
234  } else {
235  lwgeom_free(lines);
236  /* transfer ownership rather than cloning */
237  lines = (LWGEOM*)lwcollection_clone_deep(col);
238  assert(col->ngeoms == 2);
239  lwgeom_free(col->geoms[0]);
240  lwgeom_free(col->geoms[1]);
241  }
242 
243  /* reset the vector */
244  assert(col->ngeoms == 2);
245  col->ngeoms = 0;
246 
247  break;
248  }
249 
250  }
251 
252  lwgeom_free(ep);
253  lwcollection_free(col);
254 
255  lines->srid = lwgeom_in->srid;
256  return (LWGEOM*)lines;
257 #endif /* POSTGIS_GEOS_VERSION >= 33 */
258 }
259 
#define LINETYPE
Definition: liblwgeom.h:71
#define POSTGIS_GEOS_VERSION
Definition: sqldefines.h:10
int lwgeom_is_collection(const LWGEOM *lwgeom)
Determine whether a LWGEOM can contain sub-geometries or not.
Definition: lwgeom.c:991
static LWGEOM * lwgeom_extract_unique_endpoints(const LWGEOM *lwg)
LWGEOM * lwgeom_node(const LWGEOM *lwgeom_in)
int npoints
Definition: liblwgeom.h:355
LWGEOM * lwcollection_getsubgeom(LWCOLLECTION *col, int gnum)
Definition: lwcollection.c:100
uint8_t flags
Definition: liblwgeom.h:381
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1050
static int lwgeom_ngeoms(const LWGEOM *n)
char lwgeom_geos_errmsg[LWGEOM_GEOS_ERRMSG_MAXSIZE]
int32_t srid
Definition: liblwgeom.h:383
void lwmpoint_free(LWMPOINT *mpt)
Definition: lwmpoint.c:59
const char * lwtype_name(uint8_t type)
Return the type name string associated with a type number (e.g.
Definition: lwutil.c:188
void lwgeom_geos_error(const char *fmt,...)
static const LWGEOM * lwgeom_subgeom(const LWGEOM *g, int n)
LWGEOM ** geoms
Definition: liblwgeom.h:493
#define SRID_UNKNOWN
Unknown SRID value.
Definition: liblwgeom.h:172
LWMPOINT * lwmpoint_construct_empty(int srid, char hasz, char hasm)
Definition: lwmpoint.c:26
char * s
Definition: cu_in_wkt.c:23
#define FLAGS_GET_Z(flags)
Macros for manipulating the 'flags' byte.
Definition: liblwgeom.h:124
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, int autofix)
LWCOLLECTION * lwcollection_clone_deep(const LWCOLLECTION *lwgeom)
Deep clone LWCOLLECTION object.
Definition: lwcollection.c:136
static void lwgeom_collect_endpoints(const LWGEOM *lwg, LWMPOINT *col)
LWCOLLECTION * lwgeom_as_lwcollection(const LWGEOM *lwgeom)
Definition: lwgeom.c:143
int lwgeom_dimension(const LWGEOM *geom)
For an LWGEOM, returns 0 for points, 1 for lines, 2 for polygons, 3 for volume, and the max dimension...
Definition: lwgeom.c:1192
LWMPOINT * lwmpoint_add_lwpoint(LWMPOINT *mobj, const LWPOINT *obj)
Definition: lwmpoint.c:32
#define FLAGS_GET_M(flags)
Definition: liblwgeom.h:125
LWGEOM * GEOS2LWGEOM(const GEOSGeometry *geom, char want3d)
LWPOINT * lwline_get_lwpoint(const LWLINE *line, int where)
Returns freshly allocated LWPOINT that corresponds to the index where.
Definition: lwline.c:295
uint8_t type
Definition: liblwgeom.h:380
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:326
#define MULTILINETYPE
Definition: liblwgeom.h:74
LWCOLLECTION * lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm)
Definition: lwcollection.c:81
static LWMPOINT * lwgeom_extract_endpoints(const LWGEOM *lwg)
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
void lwcollection_reserve(LWCOLLECTION *col, int ngeoms)
Ensure the collection can hold at least up to ngeoms geometries.
Definition: lwcollection.c:161
int lwline_split_by_point_to(const LWLINE *ln, const LWPOINT *pt, LWMLINE *to)
Split a line by a point and push components to the provided multiline.
POINTARRAY * points
Definition: liblwgeom.h:406