PostGIS  2.4.9dev-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  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright (C) 2011 Sandro Santilli <strk@kbt.io>
22  *
23  **********************************************************************/
24 
25 
26 #include "lwgeom_geos.h"
27 #include "liblwgeom_internal.h"
28 
29 #include <string.h>
30 #include <assert.h>
31 
32 static int
34 {
36  if ( c ) return c->ngeoms;
37  else return 1;
38 }
39 
40 static const LWGEOM*
41 lwgeom_subgeom(const LWGEOM* g, int n)
42 {
44  if ( c ) return lwcollection_getsubgeom((LWCOLLECTION*)c, n);
45  else return g;
46 }
47 
48 
49 static void
51 {
52  int i, n;
53  LWLINE* l;
54 
55  switch (lwg->type)
56  {
57  case MULTILINETYPE:
58  for ( i = 0,
59  n = lwgeom_ngeoms(lwg);
60  i < n; ++i )
61  {
63  lwgeom_subgeom(lwg, i),
64  col);
65  }
66  break;
67  case LINETYPE:
68  l = (LWLINE*)lwg;
69  col = lwmpoint_add_lwpoint(col,
70  lwline_get_lwpoint(l, 0));
71  col = lwmpoint_add_lwpoint(col,
73  break;
74  default:
75  lwerror("lwgeom_collect_endpoints: invalid type %s",
76  lwtype_name(lwg->type));
77  break;
78  }
79 }
80 
81 static LWMPOINT*
83 {
85  FLAGS_GET_Z(lwg->flags),
86  FLAGS_GET_M(lwg->flags));
87  lwgeom_collect_endpoints(lwg, col);
88 
89  return col;
90 }
91 
92 /* Assumes initGEOS was called already */
93 /* May return LWPOINT or LWMPOINT */
94 static LWGEOM*
96 {
97  LWGEOM* ret;
98  GEOSGeometry *gepu;
99  LWMPOINT *epall = lwgeom_extract_endpoints(lwg);
100  GEOSGeometry *gepall = LWGEOM2GEOS((LWGEOM*)epall, 1);
101  lwmpoint_free(epall);
102  if ( ! gepall ) {
103  lwerror("LWGEOM2GEOS: %s", lwgeom_geos_errmsg);
104  return NULL;
105  }
106 
107  /* UnaryUnion to remove duplicates */
108  /* TODO: do it all within pgis using indices */
109  gepu = GEOSUnaryUnion(gepall);
110  if ( ! gepu ) {
111  GEOSGeom_destroy(gepall);
112  lwerror("GEOSUnaryUnion: %s", lwgeom_geos_errmsg);
113  return NULL;
114  }
115  GEOSGeom_destroy(gepall);
116 
117  ret = GEOS2LWGEOM(gepu, FLAGS_GET_Z(lwg->flags));
118  GEOSGeom_destroy(gepu);
119  if ( ! ret ) {
120  lwerror("Error during GEOS2LWGEOM");
121  return NULL;
122  }
123 
124  return ret;
125 }
126 
127 /* exported */
128 extern LWGEOM* lwgeom_node(const LWGEOM* lwgeom_in);
129 LWGEOM*
130 lwgeom_node(const LWGEOM* lwgeom_in)
131 {
132  GEOSGeometry *g1, *gn, *gm;
133  LWGEOM *ep, *lines;
134  LWCOLLECTION *col, *tc;
135  int pn, ln, np, nl;
136 
137  if ( lwgeom_dimension(lwgeom_in) != 1 ) {
138  lwerror("Noding geometries of dimension != 1 is unsupported");
139  return NULL;
140  }
141 
143  g1 = LWGEOM2GEOS(lwgeom_in, 1);
144  if ( ! g1 ) {
145  lwerror("LWGEOM2GEOS: %s", lwgeom_geos_errmsg);
146  return NULL;
147  }
148 
149  ep = lwgeom_extract_unique_endpoints(lwgeom_in);
150  if ( ! ep ) {
151  GEOSGeom_destroy(g1);
152  lwerror("Error extracting unique endpoints from input");
153  return NULL;
154  }
155 
156  gn = GEOSNode(g1);
157  GEOSGeom_destroy(g1);
158  if ( ! gn ) {
159  lwgeom_free(ep);
160  lwerror("GEOSUnaryUnion: %s", lwgeom_geos_errmsg);
161  return NULL;
162  }
163 
164  gm = GEOSLineMerge(gn);
165  GEOSGeom_destroy(gn);
166  if ( ! gm ) {
167  lwgeom_free(ep);
168  lwerror("GEOSLineMerge: %s", lwgeom_geos_errmsg);
169  return NULL;
170  }
171 
172  lines = GEOS2LWGEOM(gm, FLAGS_GET_Z(lwgeom_in->flags));
173  GEOSGeom_destroy(gm);
174  if ( ! lines ) {
175  lwgeom_free(ep);
176  lwerror("Error during GEOS2LWGEOM");
177  return NULL;
178  }
179 
180  /*
181  * Reintroduce endpoints from input, using split-line-by-point.
182  * Note that by now we can be sure that each point splits at
183  * most _one_ segment as any point shared by multiple segments
184  * would already be a node. Also we can be sure that any of
185  * the segments endpoints won't split any other segment.
186  * We can use the above 2 assertions to early exit the loop.
187  */
188 
190  FLAGS_GET_Z(lwgeom_in->flags),
191  FLAGS_GET_M(lwgeom_in->flags));
192 
193  np = lwgeom_ngeoms(ep);
194  for (pn=0; pn<np; ++pn) { /* for each point */
195 
196  const LWPOINT* p = (LWPOINT*)lwgeom_subgeom(ep, pn);
197 
198  nl = lwgeom_ngeoms(lines);
199  for (ln=0; ln<nl; ++ln) { /* for each line */
200 
201  const LWLINE* l = (LWLINE*)lwgeom_subgeom(lines, ln);
202 
203  int s = lwline_split_by_point_to(l, p, (LWMLINE*)col);
204 
205  if ( ! s ) continue; /* not on this line */
206 
207  if ( s == 1 ) {
208  /* found on this line, but not splitting it */
209  break;
210  }
211 
212  /* splits this line */
213 
214  /* replace this line with the two splits */
215  if ( lwgeom_is_collection(lines) ) {
216  tc = (LWCOLLECTION*)lines;
217  lwcollection_reserve(tc, nl + 1);
218  while (nl > ln+1) {
219  tc->geoms[nl] = tc->geoms[nl-1];
220  --nl;
221  }
222  lwgeom_free(tc->geoms[ln]);
223  tc->geoms[ln] = col->geoms[0];
224  tc->geoms[ln+1] = col->geoms[1];
225  tc->ngeoms++;
226  } else {
227  lwgeom_free(lines);
228  /* transfer ownership rather than cloning */
229  lines = (LWGEOM*)lwcollection_clone_deep(col);
230  assert(col->ngeoms == 2);
231  lwgeom_free(col->geoms[0]);
232  lwgeom_free(col->geoms[1]);
233  }
234 
235  /* reset the vector */
236  assert(col->ngeoms == 2);
237  col->ngeoms = 0;
238 
239  break;
240  }
241 
242  }
243 
244  lwgeom_free(ep);
245  lwcollection_free(col);
246 
247  lines->srid = lwgeom_in->srid;
248  return (LWGEOM*)lines;
249 }
250 
#define LINETYPE
Definition: liblwgeom.h:86
int lwgeom_is_collection(const LWGEOM *lwgeom)
Determine whether a LWGEOM can contain sub-geometries or not.
Definition: lwgeom.c:1040
static LWGEOM * lwgeom_extract_unique_endpoints(const LWGEOM *lwg)
LWGEOM * lwgeom_node(const LWGEOM *lwgeom_in)
int npoints
Definition: liblwgeom.h:371
LWGEOM * lwcollection_getsubgeom(LWCOLLECTION *col, int gnum)
Definition: lwcollection.c:113
uint8_t flags
Definition: liblwgeom.h:397
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1099
static int lwgeom_ngeoms(const LWGEOM *n)
char lwgeom_geos_errmsg[LWGEOM_GEOS_ERRMSG_MAXSIZE]
int32_t srid
Definition: liblwgeom.h:399
int ngeoms
Definition: liblwgeom.h:481
void lwmpoint_free(LWMPOINT *mpt)
Definition: lwmpoint.c:72
const char * lwtype_name(uint8_t type)
Return the type name string associated with a type number (e.g.
Definition: lwutil.c:218
void lwgeom_geos_error(const char *fmt,...)
static const LWGEOM * lwgeom_subgeom(const LWGEOM *g, int n)
LWGEOM ** geoms
Definition: liblwgeom.h:509
#define SRID_UNKNOWN
Unknown SRID value.
Definition: liblwgeom.h:188
LWMPOINT * lwmpoint_construct_empty(int srid, char hasz, char hasm)
Definition: lwmpoint.c:39
char * s
Definition: cu_in_wkt.c:23
#define FLAGS_GET_Z(flags)
Macros for manipulating the &#39;flags&#39; byte.
Definition: liblwgeom.h:140
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, int autofix)
LWCOLLECTION * lwcollection_clone_deep(const LWCOLLECTION *lwgeom)
Deep clone LWCOLLECTION object.
Definition: lwcollection.c:149
LWLINE ** geoms
Definition: liblwgeom.h:483
static void lwgeom_collect_endpoints(const LWGEOM *lwg, LWMPOINT *col)
LWCOLLECTION * lwgeom_as_lwcollection(const LWGEOM *lwgeom)
Definition: lwgeom.c:192
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:1241
LWMPOINT * lwmpoint_add_lwpoint(LWMPOINT *mobj, const LWPOINT *obj)
Definition: lwmpoint.c:45
#define FLAGS_GET_M(flags)
Definition: liblwgeom.h:141
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:324
uint8_t type
Definition: liblwgeom.h:396
void lwcollection_free(LWCOLLECTION *col)
Definition: lwcollection.c:340
#define MULTILINETYPE
Definition: liblwgeom.h:89
LWCOLLECTION * lwcollection_construct_empty(uint8_t type, int srid, char hasz, char hasm)
Definition: lwcollection.c:94
static LWMPOINT * lwgeom_extract_endpoints(const LWGEOM *lwg)
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
void lwcollection_reserve(LWCOLLECTION *col, int ngeoms)
Ensure the collection can hold at least up to ngeoms geometries.
Definition: lwcollection.c:174
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:422