PostGIS  2.5.0dev-r@@SVN_REVISION@@
lwgeom_topo.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) 2015-2017 Sandro Santilli <strk@kbt.io>
22  *
23  **********************************************************************/
24 
25 
26 
27 #include "../postgis_config.h"
28 
29 /*#define POSTGIS_DEBUG_LEVEL 1*/
30 #include "lwgeom_log.h"
31 
32 #include "liblwgeom_internal.h"
34 #include "lwgeom_geos.h"
35 
36 #include <stdio.h>
37 #include <inttypes.h> /* for PRId64 */
38 #include <errno.h>
39 #include <math.h>
40 
41 #ifdef WIN32
42 # define LWTFMT_ELEMID "lld"
43 #else
44 # define LWTFMT_ELEMID PRId64
45 #endif
46 
47 /*********************************************************************
48  *
49  * Backend iface
50  *
51  ********************************************************************/
52 
54 {
55  LWT_BE_IFACE *iface = lwalloc(sizeof(LWT_BE_IFACE));
56  iface->data = data;
57  iface->cb = NULL;
58  return iface;
59 }
60 
62  const LWT_BE_CALLBACKS* cb)
63 {
64  iface->cb = cb;
65 }
66 
68 {
69  lwfree(iface);
70 }
71 
72 /*********************************************************************
73  *
74  * Backend wrappers
75  *
76  ********************************************************************/
77 
78 #define CHECKCB(be, method) do { \
79  if ( ! (be)->cb || ! (be)->cb->method ) \
80  lwerror("Callback " # method " not registered by backend"); \
81 } while (0)
82 
83 #define CB0(be, method) \
84  CHECKCB(be, method);\
85  return (be)->cb->method((be)->data)
86 
87 #define CB1(be, method, a1) \
88  CHECKCB(be, method);\
89  return (be)->cb->method((be)->data, a1)
90 
91 #define CBT0(to, method) \
92  CHECKCB((to)->be_iface, method);\
93  return (to)->be_iface->cb->method((to)->be_topo)
94 
95 #define CBT1(to, method, a1) \
96  CHECKCB((to)->be_iface, method);\
97  return (to)->be_iface->cb->method((to)->be_topo, a1)
98 
99 #define CBT2(to, method, a1, a2) \
100  CHECKCB((to)->be_iface, method);\
101  return (to)->be_iface->cb->method((to)->be_topo, a1, a2)
102 
103 #define CBT3(to, method, a1, a2, a3) \
104  CHECKCB((to)->be_iface, method);\
105  return (to)->be_iface->cb->method((to)->be_topo, a1, a2, a3)
106 
107 #define CBT4(to, method, a1, a2, a3, a4) \
108  CHECKCB((to)->be_iface, method);\
109  return (to)->be_iface->cb->method((to)->be_topo, a1, a2, a3, a4)
110 
111 #define CBT5(to, method, a1, a2, a3, a4, a5) \
112  CHECKCB((to)->be_iface, method);\
113  return (to)->be_iface->cb->method((to)->be_topo, a1, a2, a3, a4, a5)
114 
115 #define CBT6(to, method, a1, a2, a3, a4, a5, a6) \
116  CHECKCB((to)->be_iface, method);\
117  return (to)->be_iface->cb->method((to)->be_topo, a1, a2, a3, a4, a5, a6)
118 
119 const char *
121 {
122  CB0(be, lastErrorMessage);
123 }
124 
127 {
128  CB1(be, loadTopologyByName, name);
129 }
130 
131 static int
133 {
134  CBT0(topo, topoGetSRID);
135 }
136 
137 static double
139 {
140  CBT0(topo, topoGetPrecision);
141 }
142 
143 static int
145 {
146  CBT0(topo, topoHasZ);
147 }
148 
149 int
151 {
152  CBT0(topo, freeTopology);
153 }
154 
157  int* numelems, int fields)
158 {
159  CBT3(topo, getNodeById, ids, numelems, fields);
160 }
161 
164  double dist, int* numelems, int fields,
165  int limit)
166 {
167  CBT5(topo, getNodeWithinDistance2D, pt, dist, numelems, fields, limit);
168 }
169 
170 static LWT_ISO_NODE*
172  const GBOX* box, int* numelems, int fields,
173  int limit )
174 {
175  CBT4(topo, getNodeWithinBox2D, box, numelems, fields, limit);
176 }
177 
178 static LWT_ISO_EDGE*
180  const GBOX* box, int* numelems, int fields,
181  int limit )
182 {
183  CBT4(topo, getEdgeWithinBox2D, box, numelems, fields, limit);
184 }
185 
186 static LWT_ISO_FACE*
188  const GBOX* box, int* numelems, int fields,
189  int limit )
190 {
191  CBT4(topo, getFaceWithinBox2D, box, numelems, fields, limit);
192 }
193 
194 int
195 lwt_be_insertNodes(LWT_TOPOLOGY* topo, LWT_ISO_NODE* node, int numelems)
196 {
197  CBT2(topo, insertNodes, node, numelems);
198 }
199 
200 static int
201 lwt_be_insertFaces(LWT_TOPOLOGY* topo, LWT_ISO_FACE* face, int numelems)
202 {
203  CBT2(topo, insertFaces, face, numelems);
204 }
205 
206 static int
207 lwt_be_deleteFacesById(const LWT_TOPOLOGY* topo, const LWT_ELEMID* ids, int numelems)
208 {
209  CBT2(topo, deleteFacesById, ids, numelems);
210 }
211 
212 static int
213 lwt_be_deleteNodesById(const LWT_TOPOLOGY* topo, const LWT_ELEMID* ids, int numelems)
214 {
215  CBT2(topo, deleteNodesById, ids, numelems);
216 }
217 
220 {
221  CBT0(topo, getNextEdgeId);
222 }
223 
226  int* numelems, int fields)
227 {
228  CBT3(topo, getEdgeById, ids, numelems, fields);
229 }
230 
231 static LWT_ISO_FACE*
233  int* numelems, int fields)
234 {
235  CBT3(topo, getFaceById, ids, numelems, fields);
236 }
237 
238 static LWT_ISO_EDGE*
240  int* numelems, int fields)
241 {
242  CBT3(topo, getEdgeByNode, ids, numelems, fields);
243 }
244 
245 static LWT_ISO_EDGE*
247  int* numelems, int fields, const GBOX *box)
248 {
249  CBT4(topo, getEdgeByFace, ids, numelems, fields, box);
250 }
251 
252 static LWT_ISO_NODE*
254  int* numelems, int fields, const GBOX *box)
255 {
256  CBT4(topo, getNodeByFace, ids, numelems, fields, box);
257 }
258 
261  double dist, int* numelems, int fields,
262  int limit)
263 {
264  CBT5(topo, getEdgeWithinDistance2D, pt, dist, numelems, fields, limit);
265 }
266 
267 int
268 lwt_be_insertEdges(LWT_TOPOLOGY* topo, LWT_ISO_EDGE* edge, int numelems)
269 {
270  CBT2(topo, insertEdges, edge, numelems);
271 }
272 
273 int
275  const LWT_ISO_EDGE* sel_edge, int sel_fields,
276  const LWT_ISO_EDGE* upd_edge, int upd_fields,
277  const LWT_ISO_EDGE* exc_edge, int exc_fields
278 )
279 {
280  CBT6(topo, updateEdges, sel_edge, sel_fields,
281  upd_edge, upd_fields,
282  exc_edge, exc_fields);
283 }
284 
285 static int
287  const LWT_ISO_NODE* sel_node, int sel_fields,
288  const LWT_ISO_NODE* upd_node, int upd_fields,
289  const LWT_ISO_NODE* exc_node, int exc_fields
290 )
291 {
292  CBT6(topo, updateNodes, sel_node, sel_fields,
293  upd_node, upd_fields,
294  exc_node, exc_fields);
295 }
296 
297 static int
299  const LWT_ISO_FACE* faces, int numfaces
300 )
301 {
302  CBT2(topo, updateFacesById, faces, numfaces);
303 }
304 
305 static int
307  const LWT_ISO_EDGE* edges, int numedges, int upd_fields
308 )
309 {
310  CBT3(topo, updateEdgesById, edges, numedges, upd_fields);
311 }
312 
313 static int
315  const LWT_ISO_NODE* nodes, int numnodes, int upd_fields
316 )
317 {
318  CBT3(topo, updateNodesById, nodes, numnodes, upd_fields);
319 }
320 
321 int
323  const LWT_ISO_EDGE* sel_edge, int sel_fields
324 )
325 {
326  CBT2(topo, deleteEdges, sel_edge, sel_fields);
327 }
328 
331 {
332  CBT1(topo, getFaceContainingPoint, pt);
333 }
334 
335 
336 int
338 {
339  CBT3(topo, updateTopoGeomEdgeSplit, split_edge, new_edge1, new_edge2);
340 }
341 
342 static int
344  LWT_ELEMID new_face1, LWT_ELEMID new_face2)
345 {
346  CBT3(topo, updateTopoGeomFaceSplit, split_face, new_face1, new_face2);
347 }
348 
349 static int
351  LWT_ELEMID face_left, LWT_ELEMID face_right)
352 {
353  CBT3(topo, checkTopoGeomRemEdge, edge_id, face_left, face_right);
354 }
355 
356 static int
358  LWT_ELEMID eid1, LWT_ELEMID eid2)
359 {
360  CBT3(topo, checkTopoGeomRemNode, node_id, eid1, eid2);
361 }
362 
363 static int
365  LWT_ELEMID face1, LWT_ELEMID face2,
366  LWT_ELEMID newface)
367 {
368  CBT3(topo, updateTopoGeomFaceHeal, face1, face2, newface);
369 }
370 
371 static int
373  LWT_ELEMID edge1, LWT_ELEMID edge2,
374  LWT_ELEMID newedge)
375 {
376  CBT3(topo, updateTopoGeomEdgeHeal, edge1, edge2, newedge);
377 }
378 
379 static LWT_ELEMID*
381  LWT_ELEMID edge, int *numedges, int limit )
382 {
383  CBT3(topo, getRingEdges, edge, numedges, limit);
384 }
385 
386 
387 /* wrappers of backend wrappers... */
388 
389 int
391 {
392  int exists = 0;
393  lwt_be_getNodeWithinDistance2D(topo, pt, 0, &exists, 0, -1);
394  if ( exists == -1 ) {
395  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
396  return 0;
397  }
398  return exists;
399 }
400 
401 int
403 {
404  int exists = 0;
405  lwt_be_getEdgeWithinDistance2D(topo, pt, 0, &exists, 0, -1);
406  if ( exists == -1 ) {
407  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
408  return 0;
409  }
410  return exists;
411 }
412 
413 /************************************************************************
414  *
415  * Utility functions
416  *
417  ************************************************************************/
418 
419 static LWGEOM *
420 _lwt_toposnap(LWGEOM *src, LWGEOM *tgt, double tol)
421 {
422  LWGEOM *tmp = src;
423  LWGEOM *tmp2;
424  int changed;
425  int iterations = 0;
426 
427  int maxiterations = lwgeom_count_vertices(tgt);
428 
429  /* GEOS snapping can be unstable */
430  /* See https://trac.osgeo.org/geos/ticket/760 */
431  do {
432  tmp2 = lwgeom_snap(tmp, tgt, tol);
433  ++iterations;
434  changed = ( lwgeom_count_vertices(tmp2) != lwgeom_count_vertices(tmp) );
435  LWDEBUGF(2, "After iteration %d, geometry changed ? %d (%d vs %d vertices)", iterations, changed, lwgeom_count_vertices(tmp2), lwgeom_count_vertices(tmp));
436  if ( tmp != src ) lwgeom_free(tmp);
437  tmp = tmp2;
438  } while ( changed && iterations <= maxiterations );
439 
440  LWDEBUGF(1, "It took %d/%d iterations to properly snap",
441  iterations, maxiterations);
442 
443  return tmp;
444 }
445 
446 static void
447 _lwt_release_faces(LWT_ISO_FACE *faces, int num_faces)
448 {
449  int i;
450  for ( i=0; i<num_faces; ++i ) {
451  if ( faces[i].mbr ) lwfree(faces[i].mbr);
452  }
453  lwfree(faces);
454 }
455 
456 static void
457 _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
458 {
459  int i;
460  for ( i=0; i<num_edges; ++i ) {
461  if ( edges[i].geom ) lwline_free(edges[i].geom);
462  }
463  lwfree(edges);
464 }
465 
466 static void
467 _lwt_release_nodes(LWT_ISO_NODE *nodes, int num_nodes)
468 {
469  int i;
470  for ( i=0; i<num_nodes; ++i ) {
471  if ( nodes[i].geom ) lwpoint_free(nodes[i].geom);
472  }
473  lwfree(nodes);
474 }
475 
476 /************************************************************************
477  *
478  * API implementation
479  *
480  ************************************************************************/
481 
482 LWT_TOPOLOGY *
483 lwt_LoadTopology( LWT_BE_IFACE *iface, const char *name )
484 {
485  LWT_BE_TOPOLOGY* be_topo;
486  LWT_TOPOLOGY* topo;
487 
488  be_topo = lwt_be_loadTopologyByName(iface, name);
489  if ( ! be_topo ) {
490  //lwerror("Could not load topology from backend: %s",
491  lwerror("%s", lwt_be_lastErrorMessage(iface));
492  return NULL;
493  }
494  topo = lwalloc(sizeof(LWT_TOPOLOGY));
495  topo->be_iface = iface;
496  topo->be_topo = be_topo;
497  topo->srid = lwt_be_topoGetSRID(topo);
498  topo->hasZ = lwt_be_topoHasZ(topo);
499  topo->precision = lwt_be_topoGetPrecision(topo);
500 
501  return topo;
502 }
503 
504 void
506 {
507  if ( ! lwt_be_freeTopology(topo) ) {
508  lwnotice("Could not release backend topology memory: %s",
510  }
511  lwfree(topo);
512 }
513 
522 static LWT_ELEMID
524  LWPOINT* pt, int skipISOChecks, int checkFace )
525 {
526  LWT_ELEMID foundInFace = -1;
527 
528  if ( lwpoint_is_empty(pt) )
529  {
530  lwerror("Cannot add empty point as isolated node");
531  return -1;
532  }
533 
534 
535  if ( ! skipISOChecks )
536  {
537  if ( lwt_be_ExistsCoincidentNode(topo, pt) ) /*x*/
538  {
539  lwerror("SQL/MM Spatial exception - coincident node");
540  return -1;
541  }
542  if ( lwt_be_ExistsEdgeIntersectingPoint(topo, pt) ) /*x*/
543  {
544  lwerror("SQL/MM Spatial exception - edge crosses node.");
545  return -1;
546  }
547  }
548 
549  if ( checkFace && ( face == -1 || ! skipISOChecks ) )
550  {
551  foundInFace = lwt_be_getFaceContainingPoint(topo, pt); /*x*/
552  if ( foundInFace == -2 ) {
553  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
554  return -1;
555  }
556  if ( foundInFace == -1 ) foundInFace = 0;
557  }
558 
559  if ( face == -1 ) {
560  face = foundInFace;
561  }
562  else if ( ! skipISOChecks && foundInFace != face ) {
563 #if 0
564  lwerror("SQL/MM Spatial exception - within face %d (not %d)",
565  foundInFace, face);
566 #else
567  lwerror("SQL/MM Spatial exception - not within face");
568 #endif
569  return -1;
570  }
571 
572  LWT_ISO_NODE node;
573  node.node_id = -1;
574  node.containing_face = face;
575  node.geom = pt;
576  if ( ! lwt_be_insertNodes(topo, &node, 1) )
577  {
578  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
579  return -1;
580  }
581 
582  return node.node_id;
583 }
584 
587  LWPOINT* pt, int skipISOChecks )
588 {
589  return _lwt_AddIsoNode( topo, face, pt, skipISOChecks, 1 );
590 }
591 
592 /* Check that an edge does not cross an existing node or edge
593  *
594  * @param myself the id of an edge to skip, if any
595  * (for ChangeEdgeGeom). Can use 0 for none.
596  *
597  * Return -1 on cross or error, 0 if everything is fine.
598  * Note that before returning -1, lwerror is invoked...
599  */
600 static int
602  LWT_ELEMID start_node, LWT_ELEMID end_node,
603  const LWLINE *geom, LWT_ELEMID myself )
604 {
605  int i, num_nodes, num_edges;
606  LWT_ISO_EDGE *edges;
607  LWT_ISO_NODE *nodes;
608  const GBOX *edgebox;
609  GEOSGeometry *edgegg;
610  const GEOSPreparedGeometry* prepared_edge;
611 
612  initGEOS(lwnotice, lwgeom_geos_error);
613 
614  edgegg = LWGEOM2GEOS( lwline_as_lwgeom(geom), 0);
615  if ( ! edgegg ) {
616  lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
617  return -1;
618  }
619  prepared_edge = GEOSPrepare( edgegg );
620  if ( ! prepared_edge ) {
621  lwerror("Could not prepare edge geometry: %s", lwgeom_geos_errmsg);
622  return -1;
623  }
624  edgebox = lwgeom_get_bbox( lwline_as_lwgeom(geom) );
625 
626  /* loop over each node within the edge's gbox */
627  nodes = lwt_be_getNodeWithinBox2D( topo, edgebox, &num_nodes,
628  LWT_COL_NODE_ALL, 0 );
629  LWDEBUGF(1, "lwt_be_getNodeWithinBox2D returned %d nodes", num_nodes);
630  if ( num_nodes == -1 ) {
631  GEOSPreparedGeom_destroy(prepared_edge);
632  GEOSGeom_destroy(edgegg);
633  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
634  return -1;
635  }
636  for ( i=0; i<num_nodes; ++i )
637  {
638  LWT_ISO_NODE* node = &(nodes[i]);
639  GEOSGeometry *nodegg;
640  int contains;
641  if ( node->node_id == start_node ) continue;
642  if ( node->node_id == end_node ) continue;
643  /* check if the edge contains this node (not on boundary) */
644  nodegg = LWGEOM2GEOS( lwpoint_as_lwgeom(node->geom) , 0);
645  /* ST_RelateMatch(rec.relate, 'T********') */
646  contains = GEOSPreparedContains( prepared_edge, nodegg );
647  GEOSGeom_destroy(nodegg);
648  if (contains == 2)
649  {
650  GEOSPreparedGeom_destroy(prepared_edge);
651  GEOSGeom_destroy(edgegg);
652  _lwt_release_nodes(nodes, num_nodes);
653  lwerror("GEOS exception on PreparedContains: %s", lwgeom_geos_errmsg);
654  return -1;
655  }
656  if ( contains )
657  {
658  GEOSPreparedGeom_destroy(prepared_edge);
659  GEOSGeom_destroy(edgegg);
660  _lwt_release_nodes(nodes, num_nodes);
661  lwerror("SQL/MM Spatial exception - geometry crosses a node");
662  return -1;
663  }
664  }
665  if ( nodes ) _lwt_release_nodes(nodes, num_nodes);
666  /* may be NULL if num_nodes == 0 */
667 
668  /* loop over each edge within the edge's gbox */
669  edges = lwt_be_getEdgeWithinBox2D( topo, edgebox, &num_edges, LWT_COL_EDGE_ALL, 0 );
670  LWDEBUGF(1, "lwt_be_getEdgeWithinBox2D returned %d edges", num_edges);
671  if ( num_edges == -1 ) {
672  GEOSPreparedGeom_destroy(prepared_edge);
673  GEOSGeom_destroy(edgegg);
674  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
675  return -1;
676  }
677  for ( i=0; i<num_edges; ++i )
678  {
679  LWT_ISO_EDGE* edge = &(edges[i]);
680  LWT_ELEMID edge_id = edge->edge_id;
681  GEOSGeometry *eegg;
682  char *relate;
683  int match;
684 
685  if ( edge_id == myself ) continue;
686 
687  if ( ! edge->geom ) {
688  _lwt_release_edges(edges, num_edges);
689  lwerror("Edge %d has NULL geometry!", edge_id);
690  return -1;
691  }
692 
693  eegg = LWGEOM2GEOS( lwline_as_lwgeom(edge->geom), 0 );
694  if ( ! eegg ) {
695  GEOSPreparedGeom_destroy(prepared_edge);
696  GEOSGeom_destroy(edgegg);
697  _lwt_release_edges(edges, num_edges);
698  lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
699  return -1;
700  }
701 
702  LWDEBUGF(2, "Edge %d converted to GEOS", edge_id);
703 
704  /* check if the edge crosses our edge (not boundary-boundary) */
705 
706  relate = GEOSRelateBoundaryNodeRule(eegg, edgegg, 2);
707  if ( ! relate ) {
708  GEOSGeom_destroy(eegg);
709  GEOSPreparedGeom_destroy(prepared_edge);
710  GEOSGeom_destroy(edgegg);
711  _lwt_release_edges(edges, num_edges);
712  lwerror("GEOSRelateBoundaryNodeRule error: %s", lwgeom_geos_errmsg);
713  return -1;
714  }
715 
716  LWDEBUGF(2, "Edge %d relate pattern is %s", edge_id, relate);
717 
718  match = GEOSRelatePatternMatch(relate, "F********");
719  if ( match ) {
720  /* error or no interior intersection */
721  GEOSGeom_destroy(eegg);
722  GEOSFree(relate);
723  if ( match == 2 ) {
724  _lwt_release_edges(edges, num_edges);
725  GEOSPreparedGeom_destroy(prepared_edge);
726  GEOSGeom_destroy(edgegg);
727  lwerror("GEOSRelatePatternMatch error: %s", lwgeom_geos_errmsg);
728  return -1;
729  }
730  else continue; /* no interior intersection */
731  }
732 
733  match = GEOSRelatePatternMatch(relate, "1FFF*FFF2");
734  if ( match ) {
735  _lwt_release_edges(edges, num_edges);
736  GEOSPreparedGeom_destroy(prepared_edge);
737  GEOSGeom_destroy(edgegg);
738  GEOSGeom_destroy(eegg);
739  GEOSFree(relate);
740  if ( match == 2 ) {
741  lwerror("GEOSRelatePatternMatch error: %s", lwgeom_geos_errmsg);
742  } else {
743  lwerror("SQL/MM Spatial exception - coincident edge %" LWTFMT_ELEMID,
744  edge_id);
745  }
746  return -1;
747  }
748 
749  match = GEOSRelatePatternMatch(relate, "1********");
750  if ( match ) {
751  _lwt_release_edges(edges, num_edges);
752  GEOSPreparedGeom_destroy(prepared_edge);
753  GEOSGeom_destroy(edgegg);
754  GEOSGeom_destroy(eegg);
755  GEOSFree(relate);
756  if ( match == 2 ) {
757  lwerror("GEOSRelatePatternMatch error: %s", lwgeom_geos_errmsg);
758  } else {
759  lwerror("Spatial exception - geometry intersects edge %"
760  LWTFMT_ELEMID, edge_id);
761  }
762  return -1;
763  }
764 
765  match = GEOSRelatePatternMatch(relate, "T********");
766  if ( match ) {
767  _lwt_release_edges(edges, num_edges);
768  GEOSPreparedGeom_destroy(prepared_edge);
769  GEOSGeom_destroy(edgegg);
770  GEOSGeom_destroy(eegg);
771  GEOSFree(relate);
772  if ( match == 2 ) {
773  lwerror("GEOSRelatePatternMatch error: %s", lwgeom_geos_errmsg);
774  } else {
775  lwerror("SQL/MM Spatial exception - geometry crosses edge %"
776  LWTFMT_ELEMID, edge_id);
777  }
778  return -1;
779  }
780 
781  LWDEBUGF(2, "Edge %d analisys completed, it does no harm", edge_id);
782 
783  GEOSFree(relate);
784  GEOSGeom_destroy(eegg);
785  }
786  if ( edges ) _lwt_release_edges(edges, num_edges);
787  /* would be NULL if num_edges was 0 */
788 
789  GEOSPreparedGeom_destroy(prepared_edge);
790  GEOSGeom_destroy(edgegg);
791 
792  return 0;
793 }
794 
795 
798  LWT_ELEMID endNode, const LWLINE* geom )
799 {
800  int num_nodes;
801  int i;
802  LWT_ISO_EDGE newedge;
803  LWT_ISO_NODE *endpoints;
804  LWT_ELEMID containing_face = -1;
805  LWT_ELEMID node_ids[2];
806  LWT_ISO_NODE updated_nodes[2];
807  int skipISOChecks = 0;
808  POINT2D p1, p2;
809 
810  /* NOT IN THE SPECS:
811  * A closed edge is never isolated (as it forms a face)
812  */
813  if ( startNode == endNode )
814  {
815  lwerror("Closed edges would not be isolated, try lwt_AddEdgeNewFaces");
816  return -1;
817  }
818 
819  if ( ! skipISOChecks )
820  {
821  /* Acurve must be simple */
822  if ( ! lwgeom_is_simple(lwline_as_lwgeom(geom)) )
823  {
824  lwerror("SQL/MM Spatial exception - curve not simple");
825  return -1;
826  }
827  }
828 
829  /*
830  * Check for:
831  * existence of nodes
832  * nodes faces match
833  * Extract:
834  * nodes face id
835  * nodes geoms
836  */
837  num_nodes = 2;
838  node_ids[0] = startNode;
839  node_ids[1] = endNode;
840  endpoints = lwt_be_getNodeById( topo, node_ids, &num_nodes,
842  if ( num_nodes < 0 )
843  {
844  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
845  return -1;
846  }
847  else if ( num_nodes < 2 )
848  {
849  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
850  lwerror("SQL/MM Spatial exception - non-existent node");
851  return -1;
852  }
853  for ( i=0; i<num_nodes; ++i )
854  {
855  const LWT_ISO_NODE *n = &(endpoints[i]);
856  if ( n->containing_face == -1 )
857  {
858  _lwt_release_nodes(endpoints, num_nodes);
859  lwerror("SQL/MM Spatial exception - not isolated node");
860  return -1;
861  }
862  if ( containing_face == -1 ) containing_face = n->containing_face;
863  else if ( containing_face != n->containing_face )
864  {
865  _lwt_release_nodes(endpoints, num_nodes);
866  lwerror("SQL/MM Spatial exception - nodes in different faces");
867  return -1;
868  }
869 
870  if ( ! skipISOChecks )
871  {
872  if ( n->node_id == startNode )
873  {
874  /* l) Check that start point of acurve match start node geoms. */
875  getPoint2d_p(geom->points, 0, &p1);
876  getPoint2d_p(n->geom->point, 0, &p2);
877  if ( ! p2d_same(&p1, &p2) )
878  {
879  _lwt_release_nodes(endpoints, num_nodes);
880  lwerror("SQL/MM Spatial exception - "
881  "start node not geometry start point.");
882  return -1;
883  }
884  }
885  else
886  {
887  /* m) Check that end point of acurve match end node geoms. */
888  getPoint2d_p(geom->points, geom->points->npoints-1, &p1);
889  getPoint2d_p(n->geom->point, 0, &p2);
890  if ( ! p2d_same(&p1, &p2) )
891  {
892  _lwt_release_nodes(endpoints, num_nodes);
893  lwerror("SQL/MM Spatial exception - "
894  "end node not geometry end point.");
895  return -1;
896  }
897  }
898  }
899  }
900 
901  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
902 
903  if ( ! skipISOChecks )
904  {
905  if ( _lwt_CheckEdgeCrossing( topo, startNode, endNode, geom, 0 ) )
906  {
907  /* would have called lwerror already, leaking :( */
908  return -1;
909  }
910  }
911 
912  /*
913  * All checks passed, time to prepare the new edge
914  */
915 
916  newedge.edge_id = lwt_be_getNextEdgeId( topo );
917  if ( newedge.edge_id == -1 ) {
918  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
919  return -1;
920  }
921 
922  /* TODO: this should likely be an exception instead ! */
923  if ( containing_face == -1 ) containing_face = 0;
924 
925  newedge.start_node = startNode;
926  newedge.end_node = endNode;
927  newedge.face_left = newedge.face_right = containing_face;
928  newedge.next_left = -newedge.edge_id;
929  newedge.next_right = newedge.edge_id;
930  newedge.geom = (LWLINE *)geom; /* const cast.. */
931 
932  int ret = lwt_be_insertEdges(topo, &newedge, 1);
933  if ( ret == -1 ) {
934  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
935  return -1;
936  } else if ( ret == 0 ) {
937  lwerror("Insertion of split edge failed (no reason)");
938  return -1;
939  }
940 
941  /*
942  * Update Node containing_face values
943  *
944  * the nodes anode and anothernode are no more isolated
945  * because now there is an edge connecting them
946  */
947  updated_nodes[0].node_id = startNode;
948  updated_nodes[0].containing_face = -1;
949  updated_nodes[1].node_id = endNode;
950  updated_nodes[1].containing_face = -1;
951  ret = lwt_be_updateNodesById(topo, updated_nodes, 2,
953  if ( ret == -1 ) {
954  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
955  return -1;
956  }
957 
958  return newedge.edge_id;
959 }
960 
961 static LWCOLLECTION *
962 _lwt_EdgeSplit( LWT_TOPOLOGY* topo, LWT_ELEMID edge, LWPOINT* pt, int skipISOChecks, LWT_ISO_EDGE** oldedge )
963 {
964  LWGEOM *split;
965  LWCOLLECTION *split_col;
966  int i;
967 
968  /* Get edge */
969  i = 1;
970  LWDEBUG(1, "calling lwt_be_getEdgeById");
971  *oldedge = lwt_be_getEdgeById(topo, &edge, &i, LWT_COL_EDGE_ALL);
972  LWDEBUGF(1, "lwt_be_getEdgeById returned %p", *oldedge);
973  if ( ! *oldedge )
974  {
975  LWDEBUGF(1, "lwt_be_getEdgeById returned NULL and set i=%d", i);
976  if ( i == -1 )
977  {
978  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
979  return NULL;
980  }
981  else if ( i == 0 )
982  {
983  lwerror("SQL/MM Spatial exception - non-existent edge");
984  return NULL;
985  }
986  else
987  {
988  lwerror("Backend coding error: getEdgeById callback returned NULL "
989  "but numelements output parameter has value %d "
990  "(expected 0 or 1)", i);
991  return NULL;
992  }
993  }
994 
995 
996  /*
997  * - check if a coincident node already exists
998  */
999  if ( ! skipISOChecks )
1000  {
1001  LWDEBUG(1, "calling lwt_be_ExistsCoincidentNode");
1002  if ( lwt_be_ExistsCoincidentNode(topo, pt) ) /*x*/
1003  {
1004  LWDEBUG(1, "lwt_be_ExistsCoincidentNode returned");
1005  _lwt_release_edges(*oldedge, 1);
1006  lwerror("SQL/MM Spatial exception - coincident node");
1007  return NULL;
1008  }
1009  LWDEBUG(1, "lwt_be_ExistsCoincidentNode returned");
1010  }
1011 
1012  /* Split edge */
1013  split = lwgeom_split((LWGEOM*)(*oldedge)->geom, (LWGEOM*)pt);
1014  if ( ! split )
1015  {
1016  _lwt_release_edges(*oldedge, 1);
1017  lwerror("could not split edge by point ?");
1018  return NULL;
1019  }
1020  split_col = lwgeom_as_lwcollection(split);
1021  if ( ! split_col ) {
1022  _lwt_release_edges(*oldedge, 1);
1023  lwgeom_free(split);
1024  lwerror("lwgeom_as_lwcollection returned NULL");
1025  return NULL;
1026  }
1027  if (split_col->ngeoms < 2) {
1028  _lwt_release_edges(*oldedge, 1);
1029  lwgeom_free(split);
1030  lwerror("SQL/MM Spatial exception - point not on edge");
1031  return NULL;
1032  }
1033 
1034 #if 0
1035  {
1036  size_t sz;
1037  char *wkt = lwgeom_to_wkt((LWGEOM*)split_col, WKT_EXTENDED, 2, &sz);
1038  LWDEBUGF(1, "returning split col: %s", wkt);
1039  lwfree(wkt);
1040  }
1041 #endif
1042  return split_col;
1043 }
1044 
1045 LWT_ELEMID
1047  LWPOINT* pt, int skipISOChecks )
1048 {
1049  LWT_ISO_NODE node;
1050  LWT_ISO_EDGE* oldedge = NULL;
1051  LWCOLLECTION *split_col;
1052  const LWGEOM *oldedge_geom;
1053  const LWGEOM *newedge_geom;
1054  LWT_ISO_EDGE newedge1;
1055  LWT_ISO_EDGE seledge, updedge, excedge;
1056  int ret;
1057 
1058  split_col = _lwt_EdgeSplit( topo, edge, pt, skipISOChecks, &oldedge );
1059  if ( ! split_col ) return -1; /* should have raised an exception */
1060  oldedge_geom = split_col->geoms[0];
1061  newedge_geom = split_col->geoms[1];
1062  /* Make sure the SRID is set on the subgeom */
1063  ((LWGEOM*)oldedge_geom)->srid = split_col->srid;
1064  ((LWGEOM*)newedge_geom)->srid = split_col->srid;
1065 
1066  /* Add new node, getting new id back */
1067  node.node_id = -1;
1068  node.containing_face = -1; /* means not-isolated */
1069  node.geom = pt;
1070  if ( ! lwt_be_insertNodes(topo, &node, 1) )
1071  {
1072  _lwt_release_edges(oldedge, 1);
1073  lwcollection_free(split_col);
1074  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1075  return -1;
1076  }
1077  if (node.node_id == -1) {
1078  /* should have been set by backend */
1079  _lwt_release_edges(oldedge, 1);
1080  lwcollection_free(split_col);
1081  lwerror("Backend coding error: "
1082  "insertNodes callback did not return node_id");
1083  return -1;
1084  }
1085 
1086  /* Insert the new edge */
1087  newedge1.edge_id = lwt_be_getNextEdgeId(topo);
1088  if ( newedge1.edge_id == -1 ) {
1089  _lwt_release_edges(oldedge, 1);
1090  lwcollection_free(split_col);
1091  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1092  return -1;
1093  }
1094  newedge1.start_node = node.node_id;
1095  newedge1.end_node = oldedge->end_node;
1096  newedge1.face_left = oldedge->face_left;
1097  newedge1.face_right = oldedge->face_right;
1098  newedge1.next_left = oldedge->next_left == -oldedge->edge_id ?
1099  -newedge1.edge_id : oldedge->next_left;
1100  newedge1.next_right = -oldedge->edge_id;
1101  newedge1.geom = lwgeom_as_lwline(newedge_geom);
1102  /* lwgeom_split of a line should only return lines ... */
1103  if ( ! newedge1.geom ) {
1104  _lwt_release_edges(oldedge, 1);
1105  lwcollection_free(split_col);
1106  lwerror("first geometry in lwgeom_split output is not a line");
1107  return -1;
1108  }
1109  ret = lwt_be_insertEdges(topo, &newedge1, 1);
1110  if ( ret == -1 ) {
1111  _lwt_release_edges(oldedge, 1);
1112  lwcollection_free(split_col);
1113  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1114  return -1;
1115  } else if ( ret == 0 ) {
1116  _lwt_release_edges(oldedge, 1);
1117  lwcollection_free(split_col);
1118  lwerror("Insertion of split edge failed (no reason)");
1119  return -1;
1120  }
1121 
1122  /* Update the old edge */
1123  updedge.geom = lwgeom_as_lwline(oldedge_geom);
1124  /* lwgeom_split of a line should only return lines ... */
1125  if ( ! updedge.geom ) {
1126  _lwt_release_edges(oldedge, 1);
1127  lwcollection_free(split_col);
1128  lwerror("second geometry in lwgeom_split output is not a line");
1129  return -1;
1130  }
1131  updedge.next_left = newedge1.edge_id;
1132  updedge.end_node = node.node_id;
1133  ret = lwt_be_updateEdges(topo,
1134  oldedge, LWT_COL_EDGE_EDGE_ID,
1136  NULL, 0);
1137  if ( ret == -1 ) {
1138  _lwt_release_edges(oldedge, 1);
1139  lwcollection_free(split_col);
1140  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1141  return -1;
1142  } else if ( ret == 0 ) {
1143  _lwt_release_edges(oldedge, 1);
1144  lwcollection_free(split_col);
1145  lwerror("Edge being split (%d) disappeared during operations?", oldedge->edge_id);
1146  return -1;
1147  } else if ( ret > 1 ) {
1148  _lwt_release_edges(oldedge, 1);
1149  lwcollection_free(split_col);
1150  lwerror("More than a single edge found with id %d !", oldedge->edge_id);
1151  return -1;
1152  }
1153 
1154  /* Update all next edge references to match new layout (ST_ModEdgeSplit) */
1155 
1156  updedge.next_right = -newedge1.edge_id;
1157  excedge.edge_id = newedge1.edge_id;
1158  seledge.next_right = -oldedge->edge_id;
1159  seledge.start_node = oldedge->end_node;
1160  ret = lwt_be_updateEdges(topo,
1162  &updedge, LWT_COL_EDGE_NEXT_RIGHT,
1163  &excedge, LWT_COL_EDGE_EDGE_ID);
1164  if ( ret == -1 ) {
1165  _lwt_release_edges(oldedge, 1);
1166  lwcollection_free(split_col);
1167  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1168  return -1;
1169  }
1170 
1171  updedge.next_left = -newedge1.edge_id;
1172  excedge.edge_id = newedge1.edge_id;
1173  seledge.next_left = -oldedge->edge_id;
1174  seledge.end_node = oldedge->end_node;
1175  ret = lwt_be_updateEdges(topo,
1177  &updedge, LWT_COL_EDGE_NEXT_LEFT,
1178  &excedge, LWT_COL_EDGE_EDGE_ID);
1179  if ( ret == -1 ) {
1180  _lwt_release_edges(oldedge, 1);
1181  lwcollection_free(split_col);
1182  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1183  return -1;
1184  }
1185 
1186  /* Update TopoGeometries composition */
1187  ret = lwt_be_updateTopoGeomEdgeSplit(topo, oldedge->edge_id, newedge1.edge_id, -1);
1188  if ( ! ret ) {
1189  _lwt_release_edges(oldedge, 1);
1190  lwcollection_free(split_col);
1191  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1192  return -1;
1193  }
1194 
1195  _lwt_release_edges(oldedge, 1);
1196  lwcollection_free(split_col);
1197 
1198  /* return new node id */
1199  return node.node_id;
1200 }
1201 
1202 LWT_ELEMID
1204  LWPOINT* pt, int skipISOChecks )
1205 {
1206  LWT_ISO_NODE node;
1207  LWT_ISO_EDGE* oldedge = NULL;
1208  LWCOLLECTION *split_col;
1209  const LWGEOM *oldedge_geom;
1210  const LWGEOM *newedge_geom;
1211  LWT_ISO_EDGE newedges[2];
1212  LWT_ISO_EDGE seledge, updedge;
1213  int ret;
1214 
1215  split_col = _lwt_EdgeSplit( topo, edge, pt, skipISOChecks, &oldedge );
1216  if ( ! split_col ) return -1; /* should have raised an exception */
1217  oldedge_geom = split_col->geoms[0];
1218  newedge_geom = split_col->geoms[1];
1219  /* Make sure the SRID is set on the subgeom */
1220  ((LWGEOM*)oldedge_geom)->srid = split_col->srid;
1221  ((LWGEOM*)newedge_geom)->srid = split_col->srid;
1222 
1223  /* Add new node, getting new id back */
1224  node.node_id = -1;
1225  node.containing_face = -1; /* means not-isolated */
1226  node.geom = pt;
1227  if ( ! lwt_be_insertNodes(topo, &node, 1) )
1228  {
1229  _lwt_release_edges(oldedge, 1);
1230  lwcollection_free(split_col);
1231  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1232  return -1;
1233  }
1234  if (node.node_id == -1) {
1235  _lwt_release_edges(oldedge, 1);
1236  lwcollection_free(split_col);
1237  /* should have been set by backend */
1238  lwerror("Backend coding error: "
1239  "insertNodes callback did not return node_id");
1240  return -1;
1241  }
1242 
1243  /* Delete the old edge */
1244  seledge.edge_id = edge;
1245  ret = lwt_be_deleteEdges(topo, &seledge, LWT_COL_EDGE_EDGE_ID);
1246  if ( ret == -1 ) {
1247  _lwt_release_edges(oldedge, 1);
1248  lwcollection_free(split_col);
1249  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1250  return -1;
1251  }
1252 
1253  /* Get new edges identifiers */
1254  newedges[0].edge_id = lwt_be_getNextEdgeId(topo);
1255  if ( newedges[0].edge_id == -1 ) {
1256  _lwt_release_edges(oldedge, 1);
1257  lwcollection_free(split_col);
1258  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1259  return -1;
1260  }
1261  newedges[1].edge_id = lwt_be_getNextEdgeId(topo);
1262  if ( newedges[1].edge_id == -1 ) {
1263  _lwt_release_edges(oldedge, 1);
1264  lwcollection_free(split_col);
1265  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1266  return -1;
1267  }
1268 
1269  /* Define the first new edge (to new node) */
1270  newedges[0].start_node = oldedge->start_node;
1271  newedges[0].end_node = node.node_id;
1272  newedges[0].face_left = oldedge->face_left;
1273  newedges[0].face_right = oldedge->face_right;
1274  newedges[0].next_left = newedges[1].edge_id;
1275  if ( oldedge->next_right == edge )
1276  newedges[0].next_right = newedges[0].edge_id;
1277  else if ( oldedge->next_right == -edge )
1278  newedges[0].next_right = -newedges[1].edge_id;
1279  else
1280  newedges[0].next_right = oldedge->next_right;
1281  newedges[0].geom = lwgeom_as_lwline(oldedge_geom);
1282  /* lwgeom_split of a line should only return lines ... */
1283  if ( ! newedges[0].geom ) {
1284  _lwt_release_edges(oldedge, 1);
1285  lwcollection_free(split_col);
1286  lwerror("first geometry in lwgeom_split output is not a line");
1287  return -1;
1288  }
1289 
1290  /* Define the second new edge (from new node) */
1291  newedges[1].start_node = node.node_id;
1292  newedges[1].end_node = oldedge->end_node;
1293  newedges[1].face_left = oldedge->face_left;
1294  newedges[1].face_right = oldedge->face_right;
1295  newedges[1].next_right = -newedges[0].edge_id;
1296  if ( oldedge->next_left == -edge )
1297  newedges[1].next_left = -newedges[1].edge_id;
1298  else if ( oldedge->next_left == edge )
1299  newedges[1].next_left = newedges[0].edge_id;
1300  else
1301  newedges[1].next_left = oldedge->next_left;
1302  newedges[1].geom = lwgeom_as_lwline(newedge_geom);
1303  /* lwgeom_split of a line should only return lines ... */
1304  if ( ! newedges[1].geom ) {
1305  _lwt_release_edges(oldedge, 1);
1306  lwcollection_free(split_col);
1307  lwerror("second geometry in lwgeom_split output is not a line");
1308  return -1;
1309  }
1310 
1311  /* Insert both new edges */
1312  ret = lwt_be_insertEdges(topo, newedges, 2);
1313  if ( ret == -1 ) {
1314  _lwt_release_edges(oldedge, 1);
1315  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1316  return -1;
1317  } else if ( ret == 0 ) {
1318  _lwt_release_edges(oldedge, 1);
1319  lwcollection_free(split_col);
1320  lwerror("Insertion of split edge failed (no reason)");
1321  return -1;
1322  }
1323 
1324  /* Update all next edge references pointing to old edge id */
1325 
1326  updedge.next_right = newedges[1].edge_id;
1327  seledge.next_right = edge;
1328  seledge.start_node = oldedge->start_node;
1329  ret = lwt_be_updateEdges(topo,
1331  &updedge, LWT_COL_EDGE_NEXT_RIGHT,
1332  NULL, 0);
1333  if ( ret == -1 ) {
1334  _lwt_release_edges(oldedge, 1);
1335  lwcollection_free(split_col);
1336  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1337  return -1;
1338  }
1339 
1340  updedge.next_right = -newedges[0].edge_id;
1341  seledge.next_right = -edge;
1342  seledge.start_node = oldedge->end_node;
1343  ret = lwt_be_updateEdges(topo,
1345  &updedge, LWT_COL_EDGE_NEXT_RIGHT,
1346  NULL, 0);
1347  if ( ret == -1 ) {
1348  _lwt_release_edges(oldedge, 1);
1349  lwcollection_free(split_col);
1350  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1351  return -1;
1352  }
1353 
1354  updedge.next_left = newedges[0].edge_id;
1355  seledge.next_left = edge;
1356  seledge.end_node = oldedge->start_node;
1357  ret = lwt_be_updateEdges(topo,
1359  &updedge, LWT_COL_EDGE_NEXT_LEFT,
1360  NULL, 0);
1361  if ( ret == -1 ) {
1362  _lwt_release_edges(oldedge, 1);
1363  lwcollection_free(split_col);
1364  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1365  return -1;
1366  }
1367 
1368  updedge.next_left = -newedges[1].edge_id;
1369  seledge.next_left = -edge;
1370  seledge.end_node = oldedge->end_node;
1371  ret = lwt_be_updateEdges(topo,
1373  &updedge, LWT_COL_EDGE_NEXT_LEFT,
1374  NULL, 0);
1375  if ( ret == -1 ) {
1376  _lwt_release_edges(oldedge, 1);
1377  lwcollection_release(split_col);
1378  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1379  return -1;
1380  }
1381 
1382  /* Update TopoGeometries composition */
1383  ret = lwt_be_updateTopoGeomEdgeSplit(topo, oldedge->edge_id, newedges[0].edge_id, newedges[1].edge_id);
1384  if ( ! ret ) {
1385  _lwt_release_edges(oldedge, 1);
1386  lwcollection_free(split_col);
1387  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1388  return -1;
1389  }
1390 
1391  _lwt_release_edges(oldedge, 1);
1392  lwcollection_free(split_col);
1393 
1394  /* return new node id */
1395  return node.node_id;
1396 }
1397 
1398 /* Data structure used by AddEdgeX functions */
1399 typedef struct edgeend_t {
1400  /* Signed identifier of next clockwise edge (+outgoing,-incoming) */
1402  /* Identifier of face between myaz and next CW edge */
1404  /* Signed identifier of next counterclockwise edge (+outgoing,-incoming) */
1406  /* Identifier of face between myaz and next CCW edge */
1409  double myaz; /* azimuth of edgeend geometry */
1410 } edgeend;
1411 
1412 /*
1413  * Get first distinct vertex from endpoint
1414  * @param pa the pointarray to seek points in
1415  * @param ref the point we want to search a distinct one
1416  * @param from vertex index to start from (will really start from "from"+dir)
1417  * @param dir 1 to go forward
1418  * -1 to go backward
1419  * @return 0 if edge is collapsed (no distinct points)
1420  */
1421 static int
1422 _lwt_FirstDistinctVertex2D(const POINTARRAY* pa, POINT2D *ref, int from, int dir, POINT2D *op)
1423 {
1424  int i, toofar, inc;
1425  POINT2D fp;
1426 
1427  if ( dir > 0 )
1428  {
1429  toofar = pa->npoints;
1430  inc = 1;
1431  }
1432  else
1433  {
1434  toofar = -1;
1435  inc = -1;
1436  }
1437 
1438  LWDEBUGF(1, "first point is index %d", from);
1439  fp = *ref; /* getPoint2d_p(pa, from, &fp); */
1440  for ( i = from+inc; i != toofar; i += inc )
1441  {
1442  LWDEBUGF(1, "testing point %d", i);
1443  getPoint2d_p(pa, i, op); /* pick next point */
1444  if ( p2d_same(op, &fp) ) continue; /* equal to startpoint */
1445  /* this is a good one, neither same of start nor of end point */
1446  return 1; /* found */
1447  }
1448 
1449  /* no distinct vertices found */
1450  return 0;
1451 }
1452 
1453 
1454 /*
1455  * Return non-zero on failure (lwerror is invoked in that case)
1456  * Possible failures:
1457  * -1 no two distinct vertices exist
1458  * -2 azimuth computation failed for first edge end
1459  */
1460 static int
1462  POINT2D *fp, POINT2D *lp)
1463 {
1464  POINTARRAY *pa = edge->points;
1465  POINT2D pt;
1466 
1467  fee->nextCW = fee->nextCCW =
1468  lee->nextCW = lee->nextCCW = 0;
1469  fee->cwFace = fee->ccwFace =
1470  lee->cwFace = lee->ccwFace = -1;
1471 
1472  /* Compute azimuth of first edge end */
1473  LWDEBUG(1, "computing azimuth of first edge end");
1474  if ( ! _lwt_FirstDistinctVertex2D(pa, fp, 0, 1, &pt) )
1475  {
1476  lwerror("Invalid edge (no two distinct vertices exist)");
1477  return -1;
1478  }
1479  if ( ! azimuth_pt_pt(fp, &pt, &(fee->myaz)) ) {
1480  lwerror("error computing azimuth of first edgeend [%.15g %.15g,%.15g %.15g]",
1481  fp->x, fp->y, pt.x, pt.y);
1482  return -2;
1483  }
1484  LWDEBUGF(1, "azimuth of first edge end [%.15g %.15g,%.15g %.15g] is %g",
1485  fp->x, fp->y, pt.x, pt.y, fee->myaz);
1486 
1487  /* Compute azimuth of second edge end */
1488  LWDEBUG(1, "computing azimuth of second edge end");
1489  if ( ! _lwt_FirstDistinctVertex2D(pa, lp, pa->npoints-1, -1, &pt) )
1490  {
1491  lwerror("Invalid edge (no two distinct vertices exist)");
1492  return -1;
1493  }
1494  if ( ! azimuth_pt_pt(lp, &pt, &(lee->myaz)) ) {
1495  lwerror("error computing azimuth of last edgeend [%.15g %.15g,%.15g %.15g]",
1496  lp->x, lp->y, pt.x, pt.y);
1497  return -2;
1498  }
1499  LWDEBUGF(1, "azimuth of last edge end [%.15g %.15g,%.15g %.15g] is %g",
1500  lp->x, lp->y, pt.x, pt.y, lee->myaz);
1501 
1502  return 0;
1503 }
1504 
1505 /*
1506  * Find the first edges encountered going clockwise and counterclockwise
1507  * around a node, starting from the given azimuth, and take
1508  * note of the face on the both sides.
1509  *
1510  * @param topo the topology to act upon
1511  * @param node the identifier of the node to analyze
1512  * @param data input (myaz) / output (nextCW, nextCCW) parameter
1513  * @param other edgeend, if also incident to given node (closed edge).
1514  * @param myedge_id identifier of the edge id that data->myaz belongs to
1515  * @return number of incident edges found
1516  *
1517  */
1518 static int
1520  edgeend *other, int myedge_id )
1521 {
1522  LWT_ISO_EDGE *edges;
1523  int numedges = 1;
1524  int i;
1525  double minaz, maxaz;
1526  double az, azdif;
1527 
1528  data->nextCW = data->nextCCW = 0;
1529  data->cwFace = data->ccwFace = -1;
1530 
1531  if ( other ) {
1532  azdif = other->myaz - data->myaz;
1533  if ( azdif < 0 ) azdif += 2 * M_PI;
1534  minaz = maxaz = azdif;
1535  /* TODO: set nextCW/nextCCW/cwFace/ccwFace to other->something ? */
1536  LWDEBUGF(1, "Other edge end has cwFace=%d and ccwFace=%d",
1537  other->cwFace, other->ccwFace);
1538  } else {
1539  minaz = maxaz = -1;
1540  }
1541 
1542  LWDEBUGF(1, "Looking for edges incident to node %" LWTFMT_ELEMID
1543  " and adjacent to azimuth %g", node, data->myaz);
1544 
1545  /* Get incident edges */
1546  edges = lwt_be_getEdgeByNode( topo, &node, &numedges, LWT_COL_EDGE_ALL );
1547  if ( numedges == -1 ) {
1548  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1549  return 0;
1550  }
1551 
1552  LWDEBUGF(1, "getEdgeByNode returned %d edges, minaz=%g, maxaz=%g",
1553  numedges, minaz, maxaz);
1554 
1555  /* For each incident edge-end (1 or 2): */
1556  for ( i = 0; i < numedges; ++i )
1557  {
1558  LWT_ISO_EDGE *edge;
1559  LWGEOM *g;
1560  LWGEOM *cleangeom;
1561  POINT2D p1, p2;
1562  POINTARRAY *pa;
1563 
1564  edge = &(edges[i]);
1565 
1566  if ( edge->edge_id == myedge_id ) continue;
1567 
1568  g = lwline_as_lwgeom(edge->geom);
1569  /* NOTE: remove_repeated_points call could be replaced by
1570  * some other mean to pick two distinct points for endpoints */
1571  cleangeom = lwgeom_remove_repeated_points( g, 0 );
1572  pa = lwgeom_as_lwline(cleangeom)->points;
1573 
1574  if ( pa->npoints < 2 ) {{
1575  LWT_ELEMID id = edge->edge_id;
1576  _lwt_release_edges(edges, numedges);
1577  lwgeom_free(cleangeom);
1578  lwerror("corrupted topology: edge %" LWTFMT_ELEMID
1579  " does not have two distinct points", id);
1580  return -1;
1581  }}
1582 
1583  if ( edge->start_node == node ) {
1584  getPoint2d_p(pa, 0, &p1);
1585  if ( ! _lwt_FirstDistinctVertex2D(pa, &p1, 0, 1, &p2) )
1586  {
1587  lwerror("Edge %d has no distinct vertices: [%.15g %.15g,%.15g %.15g]: ",
1588  edge->edge_id, p1.x, p1.y, p2.x, p2.y);
1589  return -1;
1590  }
1591  LWDEBUGF(1, "edge %" LWTFMT_ELEMID
1592  " starts on node %" LWTFMT_ELEMID
1593  ", edgeend is %g,%g-%g,%g",
1594  edge->edge_id, node, p1.x, p1.y, p2.x, p2.y);
1595  if ( ! azimuth_pt_pt(&p1, &p2, &az) ) {{
1596  LWT_ELEMID id = edge->edge_id;
1597  _lwt_release_edges(edges, numedges);
1598  lwgeom_free(cleangeom);
1599  lwerror("error computing azimuth of edge %d first edgeend [%.15g %.15g,%.15g %.15g]",
1600  id, p1.x, p1.y, p2.x, p2.y);
1601  return -1;
1602  }}
1603  azdif = az - data->myaz;
1604  LWDEBUGF(1, "azimuth of edge %" LWTFMT_ELEMID
1605  ": %g (diff: %g)", edge->edge_id, az, azdif);
1606 
1607  if ( azdif < 0 ) azdif += 2 * M_PI;
1608  if ( minaz == -1 ) {
1609  minaz = maxaz = azdif;
1610  data->nextCW = data->nextCCW = edge->edge_id; /* outgoing */
1611  data->cwFace = edge->face_left;
1612  data->ccwFace = edge->face_right;
1613  LWDEBUGF(1, "new nextCW and nextCCW edge is %" LWTFMT_ELEMID
1614  ", outgoing, "
1615  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1616  " (face_right is new ccwFace, face_left is new cwFace)",
1617  edge->edge_id, edge->face_left,
1618  edge->face_right);
1619  } else {
1620  if ( azdif < minaz ) {
1621  data->nextCW = edge->edge_id; /* outgoing */
1622  data->cwFace = edge->face_left;
1623  LWDEBUGF(1, "new nextCW edge is %" LWTFMT_ELEMID
1624  ", outgoing, "
1625  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1626  " (previous had minaz=%g, face_left is new cwFace)",
1627  edge->edge_id, edge->face_left,
1628  edge->face_right, minaz);
1629  minaz = azdif;
1630  }
1631  else if ( azdif > maxaz ) {
1632  data->nextCCW = edge->edge_id; /* outgoing */
1633  data->ccwFace = edge->face_right;
1634  LWDEBUGF(1, "new nextCCW edge is %" LWTFMT_ELEMID
1635  ", outgoing, "
1636  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1637  " (previous had maxaz=%g, face_right is new ccwFace)",
1638  edge->edge_id, edge->face_left,
1639  edge->face_right, maxaz);
1640  maxaz = azdif;
1641  }
1642  }
1643  }
1644 
1645  if ( edge->end_node == node ) {
1646  getPoint2d_p(pa, pa->npoints-1, &p1);
1647  if ( ! _lwt_FirstDistinctVertex2D(pa, &p1, pa->npoints-1, -1, &p2) )
1648  {
1649  lwerror("Edge %d has no distinct vertices: [%.15g %.15g,%.15g %.15g]: ",
1650  edge->edge_id, p1.x, p1.y, p2.x, p2.y);
1651  return -1;
1652  }
1653  LWDEBUGF(1, "edge %" LWTFMT_ELEMID " ends on node %" LWTFMT_ELEMID
1654  ", edgeend is %g,%g-%g,%g",
1655  edge->edge_id, node, p1.x, p1.y, p2.x, p2.y);
1656  if ( ! azimuth_pt_pt(&p1, &p2, &az) ) {{
1657  LWT_ELEMID id = edge->edge_id;
1658  _lwt_release_edges(edges, numedges);
1659  lwgeom_free(cleangeom);
1660  lwerror("error computing azimuth of edge %d last edgeend [%.15g %.15g,%.15g %.15g]",
1661  id, p1.x, p1.y, p2.x, p2.y);
1662  return -1;
1663  }}
1664  azdif = az - data->myaz;
1665  LWDEBUGF(1, "azimuth of edge %" LWTFMT_ELEMID
1666  ": %g (diff: %g)", edge->edge_id, az, azdif);
1667  if ( azdif < 0 ) azdif += 2 * M_PI;
1668  if ( minaz == -1 ) {
1669  minaz = maxaz = azdif;
1670  data->nextCW = data->nextCCW = -edge->edge_id; /* incoming */
1671  data->cwFace = edge->face_right;
1672  data->ccwFace = edge->face_left;
1673  LWDEBUGF(1, "new nextCW and nextCCW edge is %" LWTFMT_ELEMID
1674  ", incoming, "
1675  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1676  " (face_right is new cwFace, face_left is new ccwFace)",
1677  edge->edge_id, edge->face_left,
1678  edge->face_right);
1679  } else {
1680  if ( azdif < minaz ) {
1681  data->nextCW = -edge->edge_id; /* incoming */
1682  data->cwFace = edge->face_right;
1683  LWDEBUGF(1, "new nextCW edge is %" LWTFMT_ELEMID
1684  ", incoming, "
1685  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1686  " (previous had minaz=%g, face_right is new cwFace)",
1687  edge->edge_id, edge->face_left,
1688  edge->face_right, minaz);
1689  minaz = azdif;
1690  }
1691  else if ( azdif > maxaz ) {
1692  data->nextCCW = -edge->edge_id; /* incoming */
1693  data->ccwFace = edge->face_left;
1694  LWDEBUGF(1, "new nextCCW edge is %" LWTFMT_ELEMID
1695  ", outgoing, from start point, "
1696  "with face_left %" LWTFMT_ELEMID " and face_right %" LWTFMT_ELEMID
1697  " (previous had maxaz=%g, face_left is new ccwFace)",
1698  edge->edge_id, edge->face_left,
1699  edge->face_right, maxaz);
1700  maxaz = azdif;
1701  }
1702  }
1703  }
1704 
1705  lwgeom_free(cleangeom);
1706  }
1707  if ( numedges ) _lwt_release_edges(edges, numedges);
1708 
1709  LWDEBUGF(1, "edges adjacent to azimuth %g"
1710  " (incident to node %" LWTFMT_ELEMID ")"
1711  ": CW:%" LWTFMT_ELEMID "(%g) CCW:%" LWTFMT_ELEMID "(%g)",
1712  data->myaz, node, data->nextCW, minaz,
1713  data->nextCCW, maxaz);
1714 
1715  if ( myedge_id < 1 && numedges && data->cwFace != data->ccwFace )
1716  {
1717  if ( data->cwFace != -1 && data->ccwFace != -1 ) {
1718  lwerror("Corrupted topology: adjacent edges %" LWTFMT_ELEMID " and %" LWTFMT_ELEMID
1719  " bind different face (%" LWTFMT_ELEMID " and %" LWTFMT_ELEMID ")",
1720  data->nextCW, data->nextCCW,
1721  data->cwFace, data->ccwFace);
1722  return -1;
1723  }
1724  }
1725 
1726  /* Return number of incident edges found */
1727  return numedges;
1728 }
1729 
1730 /*
1731  * Get a point internal to the line and write it into the "ip"
1732  * parameter
1733  *
1734  * return 0 on failure (line is empty or collapsed), 1 otherwise
1735  */
1736 static int
1738 {
1739  uint32_t i;
1740  POINT2D fp, lp, tp;
1741  POINTARRAY *pa = edge->points;
1742 
1743  if ( pa->npoints < 2 ) return 0; /* empty or structurally collapsed */
1744 
1745  getPoint2d_p(pa, 0, &fp); /* save first point */
1746  getPoint2d_p(pa, pa->npoints-1, &lp); /* save last point */
1747  for (i=1; i<pa->npoints-1; ++i)
1748  {
1749  getPoint2d_p(pa, i, &tp); /* pick next point */
1750  if ( p2d_same(&tp, &fp) ) continue; /* equal to startpoint */
1751  if ( p2d_same(&tp, &lp) ) continue; /* equal to endpoint */
1752  /* this is a good one, neither same of start nor of end point */
1753  *ip = tp;
1754  return 1; /* found */
1755  }
1756 
1757  /* no distinct vertex found */
1758 
1759  /* interpolate if start point != end point */
1760 
1761  if ( p2d_same(&fp, &lp) ) return 0; /* no distinct points in edge */
1762 
1763  ip->x = fp.x + ( (lp.x - fp.x) * 0.5 );
1764  ip->y = fp.y + ( (lp.y - fp.y) * 0.5 );
1765 
1766  return 1;
1767 }
1768 
1769 static LWPOLY *
1770 _lwt_MakeRingShell(LWT_TOPOLOGY *topo, LWT_ELEMID *signed_edge_ids, int num_signed_edge_ids)
1771 {
1772  LWT_ELEMID *edge_ids;
1773  int numedges, i, j;
1774  LWT_ISO_EDGE *ring_edges;
1775 
1776  /* Construct a polygon using edges of the ring */
1777  numedges = 0;
1778  edge_ids = lwalloc(sizeof(LWT_ELEMID)*num_signed_edge_ids);
1779  for (i=0; i<num_signed_edge_ids; ++i) {
1780  int absid = llabs(signed_edge_ids[i]);
1781  int found = 0;
1782  /* Do not add the same edge twice */
1783  for (j=0; j<numedges; ++j) {
1784  if ( edge_ids[j] == absid ) {
1785  found = 1;
1786  break;
1787  }
1788  }
1789  if ( ! found ) edge_ids[numedges++] = absid;
1790  }
1791  i = numedges;
1792  ring_edges = lwt_be_getEdgeById(topo, edge_ids, &i,
1794  lwfree( edge_ids );
1795  if ( i == -1 )
1796  {
1797  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1798  return NULL;
1799  }
1800  else if ( i != numedges )
1801  {
1802  lwfree( signed_edge_ids );
1803  _lwt_release_edges(ring_edges, numedges);
1804  lwerror("Unexpected error: %d edges found when expecting %d", i, numedges);
1805  return NULL;
1806  }
1807 
1808  /* Should now build a polygon with those edges, in the order
1809  * given by GetRingEdges.
1810  */
1811  POINTARRAY *pa = NULL;
1812  for ( i=0; i<num_signed_edge_ids; ++i )
1813  {
1814  LWT_ELEMID eid = signed_edge_ids[i];
1815  LWDEBUGF(2, "Edge %d in ring is edge %" LWTFMT_ELEMID, i, eid);
1816  LWT_ISO_EDGE *edge = NULL;
1817  POINTARRAY *epa;
1818  for ( j=0; j<numedges; ++j )
1819  {
1820  if ( ring_edges[j].edge_id == llabs(eid) )
1821  {
1822  edge = &(ring_edges[j]);
1823  break;
1824  }
1825  }
1826  if ( edge == NULL )
1827  {
1828  _lwt_release_edges(ring_edges, numedges);
1829  lwerror("missing edge that was found in ring edges loop");
1830  return NULL;
1831  }
1832 
1833  if ( pa == NULL )
1834  {
1835  pa = ptarray_clone_deep(edge->geom->points);
1836  if ( eid < 0 ) ptarray_reverse_in_place(pa);
1837  }
1838  else
1839  {
1840  if ( eid < 0 )
1841  {
1842  epa = ptarray_clone_deep(edge->geom->points);
1844  ptarray_append_ptarray(pa, epa, 0);
1845  ptarray_free(epa);
1846  }
1847  else
1848  {
1849  /* avoid a clone here */
1850  ptarray_append_ptarray(pa, edge->geom->points, 0);
1851  }
1852  }
1853  }
1854  _lwt_release_edges(ring_edges, numedges);
1855  POINTARRAY **points = lwalloc(sizeof(POINTARRAY*));
1856  points[0] = pa;
1857 
1858  /* NOTE: the ring may very well have collapsed components,
1859  * which would make it topologically invalid
1860  */
1861  LWPOLY* shell = lwpoly_construct(0, 0, 1, points);
1862  return shell;
1863 }
1864 
1865 /*
1866  * Add a split face by walking on the edge side.
1867  *
1868  * @param topo the topology to act upon
1869  * @param sedge edge id and walking side and direction
1870  * (forward,left:positive backward,right:negative)
1871  * @param face the face in which the edge identifier is known to be
1872  * @param mbr_only do not create a new face but update MBR of the current
1873  *
1874  * @return:
1875  * -1: if mbr_only was requested
1876  * 0: if the edge does not form a ring
1877  * -1: if it is impossible to create a face on the requested side
1878  * ( new face on the side is the universe )
1879  * -2: error
1880  * >0 : id of newly added face
1881  */
1882 static LWT_ELEMID
1884  LWT_ELEMID sedge, LWT_ELEMID face,
1885  int mbr_only )
1886 {
1887  int numfaceedges, i, j;
1888  int newface_outside;
1889  int num_signed_edge_ids;
1890  LWT_ELEMID *signed_edge_ids;
1891  LWT_ISO_EDGE *edges;
1892  LWT_ISO_EDGE *forward_edges = NULL;
1893  int forward_edges_count = 0;
1894  LWT_ISO_EDGE *backward_edges = NULL;
1895  int backward_edges_count = 0;
1896 
1897  signed_edge_ids = lwt_be_getRingEdges(topo, sedge,
1898  &num_signed_edge_ids, 0);
1899  if ( ! signed_edge_ids ) {
1900  lwerror("Backend error (no ring edges for edge %" LWTFMT_ELEMID "): %s",
1901  sedge, lwt_be_lastErrorMessage(topo->be_iface));
1902  return -2;
1903  }
1904  LWDEBUGF(1, "getRingEdges returned %d edges", num_signed_edge_ids);
1905 
1906  /* You can't get to the other side of an edge forming a ring */
1907  for (i=0; i<num_signed_edge_ids; ++i) {
1908  if ( signed_edge_ids[i] == -sedge ) {
1909  /* No split here */
1910  LWDEBUG(1, "not a ring");
1911  lwfree( signed_edge_ids );
1912  return 0;
1913  }
1914  }
1915 
1916  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " split face %" LWTFMT_ELEMID " (mbr_only:%d)",
1917  sedge, face, mbr_only);
1918 
1919  /* Construct a polygon using edges of the ring */
1920  LWPOLY *shell = _lwt_MakeRingShell(topo, signed_edge_ids,
1921  num_signed_edge_ids);
1922  if ( ! shell ) {
1923  lwfree( signed_edge_ids );
1924  /* ring_edges should be NULL */
1925  lwerror("Could not create ring shell: %s", lwt_be_lastErrorMessage(topo->be_iface));
1926  return -2;
1927  }
1928  const POINTARRAY *pa = shell->rings[0];
1929 
1930  int isccw = ptarray_isccw(pa);
1931  LWDEBUGF(1, "Ring of edge %" LWTFMT_ELEMID " is %sclockwise",
1932  sedge, isccw ? "counter" : "");
1933  const GBOX* shellbox = lwgeom_get_bbox(lwpoly_as_lwgeom(shell));
1934 
1935  if ( face == 0 )
1936  {
1937  /* Edge split the universe face */
1938  if ( ! isccw )
1939  {
1940  lwpoly_free(shell);
1941  lwfree( signed_edge_ids );
1942  /* Face on the left side of this ring is the universe face.
1943  * Next call (for the other side) should create the split face
1944  */
1945  LWDEBUG(1, "The left face of this clockwise ring is the universe, "
1946  "won't create a new face there");
1947  return -1;
1948  }
1949  }
1950 
1951  if ( mbr_only && face != 0 )
1952  {
1953  if ( isccw )
1954  {{
1955  LWT_ISO_FACE updface;
1956  updface.face_id = face;
1957  updface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
1958  int ret = lwt_be_updateFacesById( topo, &updface, 1 );
1959  if ( ret == -1 )
1960  {
1961  lwfree( signed_edge_ids );
1962  lwpoly_free(shell); /* NOTE: owns shellbox above */
1963  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1964  return -2;
1965  }
1966  if ( ret != 1 )
1967  {
1968  lwfree( signed_edge_ids );
1969  lwpoly_free(shell); /* NOTE: owns shellbox above */
1970  lwerror("Unexpected error: %d faces found when expecting 1", ret);
1971  return -2;
1972  }
1973  }}
1974  lwfree( signed_edge_ids );
1975  lwpoly_free(shell); /* NOTE: owns shellbox above */
1976  return -1; /* mbr only was requested */
1977  }
1978 
1979  LWT_ISO_FACE *oldface = NULL;
1980  LWT_ISO_FACE newface;
1981  newface.face_id = -1;
1982  if ( face != 0 && ! isccw)
1983  {{
1984  /* Face created an hole in an outer face */
1985  int nfaces = 1;
1986  oldface = lwt_be_getFaceById(topo, &face, &nfaces, LWT_COL_FACE_ALL);
1987  if ( nfaces == -1 )
1988  {
1989  lwfree( signed_edge_ids );
1990  lwpoly_free(shell); /* NOTE: owns shellbox */
1991  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1992  return -2;
1993  }
1994  if ( nfaces != 1 )
1995  {
1996  lwfree( signed_edge_ids );
1997  lwpoly_free(shell); /* NOTE: owns shellbox */
1998  lwerror("Unexpected error: %d faces found when expecting 1", nfaces);
1999  return -2;
2000  }
2001  newface.mbr = oldface->mbr;
2002  }}
2003  else
2004  {
2005  newface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
2006  }
2007 
2008  /* Insert the new face */
2009  int ret = lwt_be_insertFaces( topo, &newface, 1 );
2010  if ( ret == -1 )
2011  {
2012  lwfree( signed_edge_ids );
2013  lwpoly_free(shell); /* NOTE: owns shellbox */
2014  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2015  return -2;
2016  }
2017  if ( ret != 1 )
2018  {
2019  lwfree( signed_edge_ids );
2020  lwpoly_free(shell); /* NOTE: owns shellbox */
2021  lwerror("Unexpected error: %d faces inserted when expecting 1", ret);
2022  return -2;
2023  }
2024  if ( oldface ) {
2025  newface.mbr = NULL; /* it is a reference to oldface mbr... */
2026  _lwt_release_faces(oldface, 1);
2027  }
2028 
2029  /* Update side location of new face edges */
2030 
2031  /* We want the new face to be on the left, if possible */
2032  if ( face != 0 && ! isccw ) { /* ring is clockwise in a real face */
2033  /* face shrinked, must update all non-contained edges and nodes */
2034  LWDEBUG(1, "New face is on the outside of the ring, updating rings in former shell");
2035  newface_outside = 1;
2036  /* newface is outside */
2037  } else {
2038  LWDEBUG(1, "New face is on the inside of the ring, updating forward edges in new ring");
2039  newface_outside = 0;
2040  /* newface is inside */
2041  }
2042 
2043  /* Update edges bounding the old face */
2044  /* (1) fetch all edges where left_face or right_face is = oldface */
2045  int fields = LWT_COL_EDGE_EDGE_ID |
2049  ;
2050  numfaceedges = 1;
2051  edges = lwt_be_getEdgeByFace( topo, &face, &numfaceedges, fields, newface.mbr );
2052  if ( numfaceedges == -1 ) {
2053  lwfree( signed_edge_ids );
2054  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2055  return -2;
2056  }
2057  LWDEBUGF(1, "lwt_be_getEdgeByFace returned %d edges", numfaceedges);
2058  GEOSGeometry *shellgg = 0;
2059  const GEOSPreparedGeometry* prepshell = 0;
2060  shellgg = LWGEOM2GEOS( lwpoly_as_lwgeom(shell), 0);
2061  if ( ! shellgg ) {
2062  lwpoly_free(shell);
2063  lwfree(signed_edge_ids);
2064  _lwt_release_edges(edges, numfaceedges);
2065  lwerror("Could not convert shell geometry to GEOS: %s", lwgeom_geos_errmsg);
2066  return -2;
2067  }
2068  prepshell = GEOSPrepare( shellgg );
2069  if ( ! prepshell ) {
2070  GEOSGeom_destroy(shellgg);
2071  lwpoly_free(shell);
2072  lwfree(signed_edge_ids);
2073  _lwt_release_edges(edges, numfaceedges);
2074  lwerror("Could not prepare shell geometry: %s", lwgeom_geos_errmsg);
2075  return -2;
2076  }
2077 
2078  if ( numfaceedges )
2079  {
2080  forward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
2081  forward_edges_count = 0;
2082  backward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
2083  backward_edges_count = 0;
2084 
2085  /* (2) loop over the results and: */
2086  for ( i=0; i<numfaceedges; ++i )
2087  {
2088  LWT_ISO_EDGE *e = &(edges[i]);
2089  int found = 0;
2090  int contains;
2091  GEOSGeometry *egg;
2092  LWPOINT *epgeom;
2093  POINT2D ep;
2094 
2095  /* (2.1) skip edges whose ID is in the list of boundary edges ? */
2096  for ( j=0; j<num_signed_edge_ids; ++j )
2097  {
2098  int seid = signed_edge_ids[j];
2099  if ( seid == e->edge_id )
2100  {
2101  /* IDEA: remove entry from signed_edge_ids ? */
2102  LWDEBUGF(1, "Edge %d is a forward edge of the new ring", e->edge_id);
2103  forward_edges[forward_edges_count].edge_id = e->edge_id;
2104  forward_edges[forward_edges_count++].face_left = newface.face_id;
2105  found++;
2106  if ( found == 2 ) break;
2107  }
2108  else if ( -seid == e->edge_id )
2109  {
2110  /* IDEA: remove entry from signed_edge_ids ? */
2111  LWDEBUGF(1, "Edge %d is a backward edge of the new ring", e->edge_id);
2112  backward_edges[backward_edges_count].edge_id = e->edge_id;
2113  backward_edges[backward_edges_count++].face_right = newface.face_id;
2114  found++;
2115  if ( found == 2 ) break;
2116  }
2117  }
2118  if ( found ) continue;
2119 
2120  /* We need to check only a single point
2121  * (to avoid collapsed elements of the shell polygon
2122  * giving false positive).
2123  * The point but must not be an endpoint.
2124  */
2125  if ( ! _lwt_GetInteriorEdgePoint(e->geom, &ep) )
2126  {
2127  GEOSPreparedGeom_destroy(prepshell);
2128  GEOSGeom_destroy(shellgg);
2129  lwfree(signed_edge_ids);
2130  lwpoly_free(shell);
2131  lwfree(forward_edges); /* contents owned by edges */
2132  lwfree(backward_edges); /* contents owned by edges */
2133  _lwt_release_edges(edges, numfaceedges);
2134  lwerror("Could not find interior point for edge %d: %s",
2136  return -2;
2137  }
2138 
2139  epgeom = lwpoint_make2d(0, ep.x, ep.y);
2140  egg = LWGEOM2GEOS( lwpoint_as_lwgeom(epgeom) , 0);
2141  lwpoint_free(epgeom);
2142  if ( ! egg ) {
2143  GEOSPreparedGeom_destroy(prepshell);
2144  GEOSGeom_destroy(shellgg);
2145  lwfree(signed_edge_ids);
2146  lwpoly_free(shell);
2147  lwfree(forward_edges); /* contents owned by edges */
2148  lwfree(backward_edges); /* contents owned by edges */
2149  _lwt_release_edges(edges, numfaceedges);
2150  lwerror("Could not convert edge geometry to GEOS: %s",
2152  return -2;
2153  }
2154  /* IDEA: can be optimized by computing this on our side rather
2155  * than on GEOS (saves conversion of big edges) */
2156  /* IDEA: check that bounding box shortcut is taken, or use
2157  * shellbox to do it here */
2158  contains = GEOSPreparedContains( prepshell, egg );
2159  GEOSGeom_destroy(egg);
2160  if ( contains == 2 )
2161  {
2162  GEOSPreparedGeom_destroy(prepshell);
2163  GEOSGeom_destroy(shellgg);
2164  lwfree(signed_edge_ids);
2165  lwpoly_free(shell);
2166  lwfree(forward_edges); /* contents owned by edges */
2167  lwfree(backward_edges); /* contents owned by edges */
2168  _lwt_release_edges(edges, numfaceedges);
2169  lwerror("GEOS exception on PreparedContains: %s", lwgeom_geos_errmsg);
2170  return -2;
2171  }
2172  LWDEBUGF(1, "Edge %d %scontained in new ring", e->edge_id,
2173  (contains?"":"not "));
2174 
2175  /* (2.2) skip edges (NOT, if newface_outside) contained in shell */
2176  if ( newface_outside )
2177  {
2178  if ( contains )
2179  {
2180  LWDEBUGF(1, "Edge %d contained in an hole of the new face",
2181  e->edge_id);
2182  continue;
2183  }
2184  }
2185  else
2186  {
2187  if ( ! contains )
2188  {
2189  LWDEBUGF(1, "Edge %d not contained in the face shell",
2190  e->edge_id);
2191  continue;
2192  }
2193  }
2194 
2195  /* (2.3) push to forward_edges if left_face = oface */
2196  if ( e->face_left == face )
2197  {
2198  LWDEBUGF(1, "Edge %d has new face on the left side", e->edge_id);
2199  forward_edges[forward_edges_count].edge_id = e->edge_id;
2200  forward_edges[forward_edges_count++].face_left = newface.face_id;
2201  }
2202 
2203  /* (2.4) push to backward_edges if right_face = oface */
2204  if ( e->face_right == face )
2205  {
2206  LWDEBUGF(1, "Edge %d has new face on the right side", e->edge_id);
2207  backward_edges[backward_edges_count].edge_id = e->edge_id;
2208  backward_edges[backward_edges_count++].face_right = newface.face_id;
2209  }
2210  }
2211 
2212  /* Update forward edges */
2213  if ( forward_edges_count )
2214  {
2215  ret = lwt_be_updateEdgesById(topo, forward_edges,
2216  forward_edges_count,
2218  if ( ret == -1 )
2219  {
2220  lwfree( signed_edge_ids );
2221  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2222  return -2;
2223  }
2224  if ( ret != forward_edges_count )
2225  {
2226  lwfree( signed_edge_ids );
2227  lwerror("Unexpected error: %d edges updated when expecting %d",
2228  ret, forward_edges_count);
2229  return -2;
2230  }
2231  }
2232 
2233  /* Update backward edges */
2234  if ( backward_edges_count )
2235  {
2236  ret = lwt_be_updateEdgesById(topo, backward_edges,
2237  backward_edges_count,
2239  if ( ret == -1 )
2240  {
2241  lwfree( signed_edge_ids );
2242  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2243  return -2;
2244  }
2245  if ( ret != backward_edges_count )
2246  {
2247  lwfree( signed_edge_ids );
2248  lwerror("Unexpected error: %d edges updated when expecting %d",
2249  ret, backward_edges_count);
2250  return -2;
2251  }
2252  }
2253 
2254  lwfree(forward_edges);
2255  lwfree(backward_edges);
2256 
2257  }
2258 
2259  _lwt_release_edges(edges, numfaceedges);
2260 
2261  /* Update isolated nodes which are now in new face */
2262  int numisonodes = 1;
2264  LWT_ISO_NODE *nodes = lwt_be_getNodeByFace(topo, &face,
2265  &numisonodes, fields, newface.mbr);
2266  if ( numisonodes == -1 ) {
2267  lwfree( signed_edge_ids );
2268  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2269  return -2;
2270  }
2271  if ( numisonodes ) {
2272  LWT_ISO_NODE *updated_nodes = lwalloc(sizeof(LWT_ISO_NODE)*numisonodes);
2273  int nodes_to_update = 0;
2274  for (i=0; i<numisonodes; ++i)
2275  {
2276  LWT_ISO_NODE *n = &(nodes[i]);
2277  GEOSGeometry *ngg;
2278  ngg = LWGEOM2GEOS( lwpoint_as_lwgeom(n->geom), 0 );
2279  int contains;
2280  if ( ! ngg ) {
2281  _lwt_release_nodes(nodes, numisonodes);
2282  if ( prepshell ) GEOSPreparedGeom_destroy(prepshell);
2283  if ( shellgg ) GEOSGeom_destroy(shellgg);
2284  lwfree(signed_edge_ids);
2285  lwpoly_free(shell);
2286  lwerror("Could not convert node geometry to GEOS: %s",
2288  return -2;
2289  }
2290  contains = GEOSPreparedContains( prepshell, ngg );
2291  GEOSGeom_destroy(ngg);
2292  if ( contains == 2 )
2293  {
2294  _lwt_release_nodes(nodes, numisonodes);
2295  if ( prepshell ) GEOSPreparedGeom_destroy(prepshell);
2296  if ( shellgg ) GEOSGeom_destroy(shellgg);
2297  lwfree(signed_edge_ids);
2298  lwpoly_free(shell);
2299  lwerror("GEOS exception on PreparedContains: %s", lwgeom_geos_errmsg);
2300  return -2;
2301  }
2302  LWDEBUGF(1, "Node %d is %scontained in new ring, newface is %s",
2303  n->node_id, contains ? "" : "not ",
2304  newface_outside ? "outside" : "inside" );
2305  if ( newface_outside )
2306  {
2307  if ( contains )
2308  {
2309  LWDEBUGF(1, "Node %d contained in an hole of the new face",
2310  n->node_id);
2311  continue;
2312  }
2313  }
2314  else
2315  {
2316  if ( ! contains )
2317  {
2318  LWDEBUGF(1, "Node %d not contained in the face shell",
2319  n->node_id);
2320  continue;
2321  }
2322  }
2323  updated_nodes[nodes_to_update].node_id = n->node_id;
2324  updated_nodes[nodes_to_update++].containing_face =
2325  newface.face_id;
2326  LWDEBUGF(1, "Node %d will be updated", n->node_id);
2327  }
2328  _lwt_release_nodes(nodes, numisonodes);
2329  if ( nodes_to_update )
2330  {
2331  int ret = lwt_be_updateNodesById(topo, updated_nodes,
2332  nodes_to_update,
2334  if ( ret == -1 ) {
2335  lwfree( signed_edge_ids );
2336  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2337  return -2;
2338  }
2339  }
2340  lwfree(updated_nodes);
2341  }
2342 
2343  GEOSPreparedGeom_destroy(prepshell);
2344  GEOSGeom_destroy(shellgg);
2345  lwfree(signed_edge_ids);
2346  lwpoly_free(shell);
2347 
2348  return newface.face_id;
2349 }
2350 
2358 static LWT_ELEMID
2360  LWT_ELEMID start_node, LWT_ELEMID end_node,
2361  LWLINE *geom, int skipChecks, int modFace )
2362 {
2363  LWT_ISO_EDGE newedge;
2364  LWGEOM *cleangeom;
2365  edgeend span; /* start point analisys */
2366  edgeend epan; /* end point analisys */
2367  POINT2D p1, pn, p2;
2368  POINTARRAY *pa;
2369  LWT_ELEMID node_ids[2];
2370  const LWPOINT *start_node_geom = NULL;
2371  const LWPOINT *end_node_geom = NULL;
2372  int num_nodes;
2373  LWT_ISO_NODE *endpoints;
2374  int i;
2375  int prev_left;
2376  int prev_right;
2377  LWT_ISO_EDGE seledge;
2378  LWT_ISO_EDGE updedge;
2379 
2380  if ( ! skipChecks )
2381  {
2382  /* curve must be simple */
2383  if ( ! lwgeom_is_simple(lwline_as_lwgeom(geom)) )
2384  {
2385  lwerror("SQL/MM Spatial exception - curve not simple");
2386  return -1;
2387  }
2388  }
2389 
2390  newedge.start_node = start_node;
2391  newedge.end_node = end_node;
2392  newedge.geom = geom;
2393  newedge.face_left = -1;
2394  newedge.face_right = -1;
2395  /* TODO: should do the repeated points removal in 2D space */
2396  cleangeom = lwgeom_remove_repeated_points( lwline_as_lwgeom(geom), 0 );
2397 
2398  pa = lwgeom_as_lwline(cleangeom)->points;
2399  if ( pa->npoints < 2 ) {
2400  lwgeom_free(cleangeom);
2401  lwerror("Invalid edge (no two distinct vertices exist)");
2402  return -1;
2403  }
2404 
2405  /* Initialize endpoint info (some of that ) */
2406  span.cwFace = span.ccwFace =
2407  epan.cwFace = epan.ccwFace = -1;
2408 
2409  /* Compute azimuth of first edge end on start node */
2410  getPoint2d_p(pa, 0, &p1);
2411  if ( ! _lwt_FirstDistinctVertex2D(pa, &p1, 0, 1, &pn) )
2412  {
2413  lwgeom_free(cleangeom);
2414  lwerror("Invalid edge (no two distinct vertices exist)");
2415  return -1;
2416  }
2417  if ( ! azimuth_pt_pt(&p1, &pn, &span.myaz) ) {
2418  lwgeom_free(cleangeom);
2419  lwerror("error computing azimuth of first edgeend [%.15g %.15g,%.15g %.15g]",
2420  p1.x, p1.y, pn.x, pn.y);
2421  return -1;
2422  }
2423  LWDEBUGF(1, "edge's start node is %g,%g", p1.x, p1.y);
2424 
2425  /* Compute azimuth of last edge end on end node */
2426  getPoint2d_p(pa, pa->npoints-1, &p2);
2427  if ( ! _lwt_FirstDistinctVertex2D(pa, &p2, pa->npoints-1, -1, &pn) )
2428  {
2429  lwgeom_free(cleangeom);
2430  /* This should never happen as we checked the edge while computing first edgend */
2431  lwerror("Invalid clean edge (no two distinct vertices exist) - should not happen");
2432  return -1;
2433  }
2434  lwgeom_free(cleangeom);
2435  if ( ! azimuth_pt_pt(&p2, &pn, &epan.myaz) ) {
2436  lwerror("error computing azimuth of last edgeend [%.15g %.15g,%.15g %.15g]",
2437  p2.x, p2.y, pn.x, pn.y);
2438  return -1;
2439  }
2440  LWDEBUGF(1, "edge's end node is %g,%g", p2.x, p2.y);
2441 
2442  /*
2443  * Check endpoints existance, match with Curve geometry
2444  * and get face information (if any)
2445  */
2446 
2447  if ( start_node != end_node ) {
2448  num_nodes = 2;
2449  node_ids[0] = start_node;
2450  node_ids[1] = end_node;
2451  } else {
2452  num_nodes = 1;
2453  node_ids[0] = start_node;
2454  }
2455 
2456  endpoints = lwt_be_getNodeById( topo, node_ids, &num_nodes, LWT_COL_NODE_ALL );
2457  if ( num_nodes < 0 ) {
2458  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2459  return -1;
2460  }
2461  for ( i=0; i<num_nodes; ++i )
2462  {
2463  LWT_ISO_NODE* node = &(endpoints[i]);
2464  if ( node->containing_face != -1 )
2465  {
2466  if ( newedge.face_left == -1 )
2467  {
2468  newedge.face_left = newedge.face_right = node->containing_face;
2469  }
2470  else if ( newedge.face_left != node->containing_face )
2471  {
2472  _lwt_release_nodes(endpoints, num_nodes);
2473  lwerror("SQL/MM Spatial exception - geometry crosses an edge"
2474  " (endnodes in faces %" LWTFMT_ELEMID " and %" LWTFMT_ELEMID ")",
2475  newedge.face_left, node->containing_face);
2476  }
2477  }
2478 
2479  LWDEBUGF(1, "Node %d, with geom %p (looking for %d and %d)",
2480  node->node_id, node->geom, start_node, end_node);
2481  if ( node->node_id == start_node ) {
2482  start_node_geom = node->geom;
2483  }
2484  if ( node->node_id == end_node ) {
2485  end_node_geom = node->geom;
2486  }
2487  }
2488 
2489  if ( ! skipChecks )
2490  {
2491  if ( ! start_node_geom )
2492  {
2493  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2494  lwerror("SQL/MM Spatial exception - non-existent node");
2495  return -1;
2496  }
2497  else
2498  {
2499  pa = start_node_geom->point;
2500  getPoint2d_p(pa, 0, &pn);
2501  if ( ! p2d_same(&pn, &p1) )
2502  {
2503  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2504  lwerror("SQL/MM Spatial exception"
2505  " - start node not geometry start point."
2506  //" - start node not geometry start point (%g,%g != %g,%g).", pn.x, pn.y, p1.x, p1.y
2507  );
2508  return -1;
2509  }
2510  }
2511 
2512  if ( ! end_node_geom )
2513  {
2514  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2515  lwerror("SQL/MM Spatial exception - non-existent node");
2516  return -1;
2517  }
2518  else
2519  {
2520  pa = end_node_geom->point;
2521  getPoint2d_p(pa, 0, &pn);
2522  if ( ! p2d_same(&pn, &p2) )
2523  {
2524  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2525  lwerror("SQL/MM Spatial exception"
2526  " - end node not geometry end point."
2527  //" - end node not geometry end point (%g,%g != %g,%g).", pn.x, pn.y, p2.x, p2.y
2528  );
2529  return -1;
2530  }
2531  }
2532 
2533  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2534 
2535  if ( _lwt_CheckEdgeCrossing( topo, start_node, end_node, geom, 0 ) )
2536  return -1;
2537 
2538  } /* ! skipChecks */
2539 
2540  /*
2541  * All checks passed, time to prepare the new edge
2542  */
2543 
2544  newedge.edge_id = lwt_be_getNextEdgeId( topo );
2545  if ( newedge.edge_id == -1 ) {
2546  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2547  return -1;
2548  }
2549 
2550  /* Find adjacent edges to each endpoint */
2551  int isclosed = start_node == end_node;
2552  int found;
2553  found = _lwt_FindAdjacentEdges( topo, start_node, &span,
2554  isclosed ? &epan : NULL, -1 );
2555  if ( found ) {
2556  span.was_isolated = 0;
2557  newedge.next_right = span.nextCW ? span.nextCW : -newedge.edge_id;
2558  prev_left = span.nextCCW ? -span.nextCCW : newedge.edge_id;
2559  LWDEBUGF(1, "New edge %d is connected on start node, "
2560  "next_right is %d, prev_left is %d",
2561  newedge.edge_id, newedge.next_right, prev_left);
2562  if ( newedge.face_right == -1 ) {
2563  newedge.face_right = span.cwFace;
2564  }
2565  if ( newedge.face_left == -1 ) {
2566  newedge.face_left = span.ccwFace;
2567  }
2568  } else {
2569  span.was_isolated = 1;
2570  newedge.next_right = isclosed ? -newedge.edge_id : newedge.edge_id;
2571  prev_left = isclosed ? newedge.edge_id : -newedge.edge_id;
2572  LWDEBUGF(1, "New edge %d is isolated on start node, "
2573  "next_right is %d, prev_left is %d",
2574  newedge.edge_id, newedge.next_right, prev_left);
2575  }
2576 
2577  found = _lwt_FindAdjacentEdges( topo, end_node, &epan,
2578  isclosed ? &span : NULL, -1 );
2579  if ( found ) {
2580  epan.was_isolated = 0;
2581  newedge.next_left = epan.nextCW ? epan.nextCW : newedge.edge_id;
2582  prev_right = epan.nextCCW ? -epan.nextCCW : -newedge.edge_id;
2583  LWDEBUGF(1, "New edge %d is connected on end node, "
2584  "next_left is %d, prev_right is %d",
2585  newedge.edge_id, newedge.next_left, prev_right);
2586  if ( newedge.face_right == -1 ) {
2587  newedge.face_right = span.ccwFace;
2588  } else if ( modFace != -1 && newedge.face_right != epan.ccwFace ) {
2589  /* side-location conflict */
2590  lwerror("Side-location conflict: "
2591  "new edge starts in face"
2592  " %" LWTFMT_ELEMID " and ends in face"
2593  " %" LWTFMT_ELEMID,
2594  newedge.face_right, epan.ccwFace
2595  );
2596  return -1;
2597  }
2598  if ( newedge.face_left == -1 ) {
2599  newedge.face_left = span.cwFace;
2600  } else if ( modFace != -1 && newedge.face_left != epan.cwFace ) {
2601  /* side-location conflict */
2602  lwerror("Side-location conflict: "
2603  "new edge starts in face"
2604  " %" LWTFMT_ELEMID " and ends in face"
2605  " %" LWTFMT_ELEMID,
2606  newedge.face_left, epan.cwFace
2607  );
2608  return -1;
2609  }
2610  } else {
2611  epan.was_isolated = 1;
2612  newedge.next_left = isclosed ? newedge.edge_id : -newedge.edge_id;
2613  prev_right = isclosed ? -newedge.edge_id : newedge.edge_id;
2614  LWDEBUGF(1, "New edge %d is isolated on end node, "
2615  "next_left is %d, prev_right is %d",
2616  newedge.edge_id, newedge.next_left, prev_right);
2617  }
2618 
2619  /*
2620  * If we don't have faces setup by now we must have encountered
2621  * a malformed topology (no containing_face on isolated nodes, no
2622  * left/right faces on adjacent edges or mismatching values)
2623  */
2624  if ( newedge.face_left != newedge.face_right )
2625  {
2626  lwerror("Left(%" LWTFMT_ELEMID ")/right(%" LWTFMT_ELEMID ")"
2627  "faces mismatch: invalid topology ?",
2628  newedge.face_left, newedge.face_right);
2629  return -1;
2630  }
2631  else if ( newedge.face_left == -1 && modFace > -1 )
2632  {
2633  lwerror("Could not derive edge face from linked primitives:"
2634  " invalid topology ?");
2635  return -1;
2636  }
2637 
2638  /*
2639  * Insert the new edge, and update all linking
2640  */
2641 
2642  int ret = lwt_be_insertEdges(topo, &newedge, 1);
2643  if ( ret == -1 ) {
2644  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2645  return -1;
2646  } else if ( ret == 0 ) {
2647  lwerror("Insertion of split edge failed (no reason)");
2648  return -1;
2649  }
2650 
2651  int updfields;
2652 
2653  /* Link prev_left to us
2654  * (if it's not us already) */
2655  if ( llabs(prev_left) != newedge.edge_id )
2656  {
2657  if ( prev_left > 0 )
2658  {
2659  /* its next_left_edge is us */
2660  updfields = LWT_COL_EDGE_NEXT_LEFT;
2661  updedge.next_left = newedge.edge_id;
2662  seledge.edge_id = prev_left;
2663  }
2664  else
2665  {
2666  /* its next_right_edge is us */
2667  updfields = LWT_COL_EDGE_NEXT_RIGHT;
2668  updedge.next_right = newedge.edge_id;
2669  seledge.edge_id = -prev_left;
2670  }
2671 
2672  ret = lwt_be_updateEdges(topo,
2673  &seledge, LWT_COL_EDGE_EDGE_ID,
2674  &updedge, updfields,
2675  NULL, 0);
2676  if ( ret == -1 ) {
2677  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2678  return -1;
2679  }
2680  }
2681 
2682  /* Link prev_right to us
2683  * (if it's not us already) */
2684  if ( llabs(prev_right) != newedge.edge_id )
2685  {
2686  if ( prev_right > 0 )
2687  {
2688  /* its next_left_edge is -us */
2689  updfields = LWT_COL_EDGE_NEXT_LEFT;
2690  updedge.next_left = -newedge.edge_id;
2691  seledge.edge_id = prev_right;
2692  }
2693  else
2694  {
2695  /* its next_right_edge is -us */
2696  updfields = LWT_COL_EDGE_NEXT_RIGHT;
2697  updedge.next_right = -newedge.edge_id;
2698  seledge.edge_id = -prev_right;
2699  }
2700 
2701  ret = lwt_be_updateEdges(topo,
2702  &seledge, LWT_COL_EDGE_EDGE_ID,
2703  &updedge, updfields,
2704  NULL, 0);
2705  if ( ret == -1 ) {
2706  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2707  return -1;
2708  }
2709  }
2710 
2711  /* NOT IN THE SPECS...
2712  * set containing_face = null for start_node and end_node
2713  * if they where isolated
2714  *
2715  */
2716  LWT_ISO_NODE updnode, selnode;
2717  updnode.containing_face = -1;
2718  if ( span.was_isolated )
2719  {
2720  selnode.node_id = start_node;
2721  ret = lwt_be_updateNodes(topo,
2722  &selnode, LWT_COL_NODE_NODE_ID,
2723  &updnode, LWT_COL_NODE_CONTAINING_FACE,
2724  NULL, 0);
2725  if ( ret == -1 ) {
2726  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2727  return -1;
2728  }
2729  }
2730  if ( epan.was_isolated )
2731  {
2732  selnode.node_id = end_node;
2733  ret = lwt_be_updateNodes(topo,
2734  &selnode, LWT_COL_NODE_NODE_ID,
2735  &updnode, LWT_COL_NODE_CONTAINING_FACE,
2736  NULL, 0);
2737  if ( ret == -1 ) {
2738  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2739  return -1;
2740  }
2741  }
2742 
2743  /* Check face splitting, if required */
2744 
2745  if ( modFace > -1 ) {
2746 
2747  if ( ! isclosed && ( epan.was_isolated || span.was_isolated ) )
2748  {
2749  LWDEBUG(1, "New edge is dangling, so it cannot split any face");
2750  return newedge.edge_id; /* no split */
2751  }
2752 
2753  int newface1 = -1;
2754 
2755  /* IDEA: avoid building edge ring if input is closed, which means we
2756  * know in advance it splits a face */
2757 
2758  if ( ! modFace )
2759  {
2760  newface1 = _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 0 );
2761  if ( newface1 == 0 ) {
2762  LWDEBUG(1, "New edge does not split any face");
2763  return newedge.edge_id; /* no split */
2764  }
2765  }
2766 
2767  int newface = _lwt_AddFaceSplit( topo, newedge.edge_id,
2768  newedge.face_left, 0 );
2769  if ( modFace )
2770  {
2771  if ( newface == 0 ) {
2772  LWDEBUG(1, "New edge does not split any face");
2773  return newedge.edge_id; /* no split */
2774  }
2775 
2776  if ( newface < 0 )
2777  {
2778  /* face on the left is the universe face */
2779  /* must be forming a maximal ring in universal face */
2780  newface = _lwt_AddFaceSplit( topo, -newedge.edge_id,
2781  newedge.face_left, 0 );
2782  if ( newface < 0 ) return newedge.edge_id; /* no split */
2783  }
2784  else
2785  {
2786  _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 1 );
2787  }
2788  }
2789 
2790  /*
2791  * Update topogeometries, if needed
2792  */
2793  if ( newedge.face_left != 0 )
2794  {
2795  ret = lwt_be_updateTopoGeomFaceSplit(topo, newedge.face_left,
2796  newface, newface1);
2797  if ( ret == 0 ) {
2798  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2799  return -1;
2800  }
2801 
2802  if ( ! modFace )
2803  {
2804  /* drop old face from the face table */
2805  ret = lwt_be_deleteFacesById(topo, &(newedge.face_left), 1);
2806  if ( ret == -1 ) {
2807  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2808  return -1;
2809  }
2810  }
2811  }
2812 
2813  } // end of face split checking
2814 
2815  return newedge.edge_id;
2816 }
2817 
2818 LWT_ELEMID
2820  LWT_ELEMID start_node, LWT_ELEMID end_node,
2821  LWLINE *geom, int skipChecks )
2822 {
2823  return _lwt_AddEdge( topo, start_node, end_node, geom, skipChecks, 1 );
2824 }
2825 
2826 LWT_ELEMID
2828  LWT_ELEMID start_node, LWT_ELEMID end_node,
2829  LWLINE *geom, int skipChecks )
2830 {
2831  return _lwt_AddEdge( topo, start_node, end_node, geom, skipChecks, 0 );
2832 }
2833 
2834 static LWGEOM *
2835 _lwt_FaceByEdges(LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edges, int numfaceedges)
2836 {
2837  LWGEOM *outg;
2838  LWCOLLECTION *bounds;
2839  LWGEOM **geoms = lwalloc( sizeof(LWGEOM*) * numfaceedges );
2840  int i, validedges = 0;
2841 
2842  for ( i=0; i<numfaceedges; ++i )
2843  {
2844  /* NOTE: skipping edges with same face on both sides, although
2845  * correct, results in a failure to build faces from
2846  * invalid topologies as expected by legacy tests.
2847  * TODO: update legacy tests expectances/unleash this skipping ?
2848  */
2849  /* if ( edges[i].face_left == edges[i].face_right ) continue; */
2850  geoms[validedges++] = lwline_as_lwgeom(edges[i].geom);
2851  }
2852  if ( ! validedges )
2853  {
2854  /* Face has no valid boundary edges, we'll return EMPTY, see
2855  * https://trac.osgeo.org/postgis/ticket/3221 */
2856  if ( numfaceedges ) lwfree(geoms);
2857  LWDEBUG(1, "_lwt_FaceByEdges returning empty polygon");
2858  return lwpoly_as_lwgeom(
2859  lwpoly_construct_empty(topo->srid, topo->hasZ, 0)
2860  );
2861  }
2863  topo->srid,
2864  NULL, /* gbox */
2865  validedges,
2866  geoms);
2867  outg = lwgeom_buildarea( lwcollection_as_lwgeom(bounds) );
2868  lwcollection_release(bounds);
2869  lwfree(geoms);
2870 #if 0
2871  {
2872  size_t sz;
2873  char *wkt = lwgeom_to_wkt(outg, WKT_EXTENDED, 2, &sz);
2874  LWDEBUGF(1, "_lwt_FaceByEdges returning area: %s", wkt);
2875  lwfree(wkt);
2876  }
2877 #endif
2878  return outg;
2879 }
2880 
2881 LWGEOM*
2883 {
2884  int numfaceedges;
2885  LWT_ISO_EDGE *edges;
2886  LWT_ISO_FACE *face;
2887  LWPOLY *out;
2888  LWGEOM *outg;
2889  int i;
2890  int fields;
2891 
2892  if ( faceid == 0 )
2893  {
2894  lwerror("SQL/MM Spatial exception - universal face has no geometry");
2895  return NULL;
2896  }
2897 
2898  /* Construct the face geometry */
2899  numfaceedges = 1;
2900  fields = LWT_COL_EDGE_GEOM |
2903  ;
2904  edges = lwt_be_getEdgeByFace( topo, &faceid, &numfaceedges, fields, NULL );
2905  if ( numfaceedges == -1 ) {
2906  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2907  return NULL;
2908  }
2909 
2910  if ( numfaceedges == 0 )
2911  {
2912  i = 1;
2913  face = lwt_be_getFaceById(topo, &faceid, &i, LWT_COL_FACE_FACE_ID);
2914  if ( i == -1 ) {
2915  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2916  return NULL;
2917  }
2918  if ( i == 0 ) {
2919  lwerror("SQL/MM Spatial exception - non-existent face.");
2920  return NULL;
2921  }
2922  lwfree( face );
2923  if ( i > 1 ) {
2924  lwerror("Corrupted topology: multiple face records have face_id=%"
2925  LWTFMT_ELEMID, faceid);
2926  return NULL;
2927  }
2928  /* Face has no boundary edges, we'll return EMPTY, see
2929  * https://trac.osgeo.org/postgis/ticket/3221 */
2930  out = lwpoly_construct_empty(topo->srid, topo->hasZ, 0);
2931  return lwpoly_as_lwgeom(out);
2932  }
2933 
2934  outg = _lwt_FaceByEdges( topo, edges, numfaceedges );
2935  _lwt_release_edges(edges, numfaceedges);
2936 
2937  return outg;
2938 }
2939 
2940 /* Find which edge from the "edges" set defines the next
2941  * portion of the given "ring".
2942  *
2943  * The edge might be either forward or backward.
2944  *
2945  * @param ring The ring to find definition of.
2946  * It is assumed it does not contain duplicated vertices.
2947  * @param from offset of the ring point to start looking from
2948  * @param edges array of edges to search into
2949  * @param numedges number of edges in the edges array
2950  *
2951  * @return index of the edge defining the next ring portion or
2952  * -1 if no edge was found to be part of the ring
2953  */
2954 static int
2955 _lwt_FindNextRingEdge(const POINTARRAY *ring, int from,
2956  const LWT_ISO_EDGE *edges, int numedges)
2957 {
2958  int i;
2959  POINT2D p1;
2960 
2961  /* Get starting ring point */
2962  getPoint2d_p(ring, from, &p1);
2963 
2964  LWDEBUGF(1, "Ring's 'from' point (%d) is %g,%g", from, p1.x, p1.y);
2965 
2966  /* find the edges defining the next portion of ring starting from
2967  * vertex "from" */
2968  for ( i=0; i<numedges; ++i )
2969  {
2970  const LWT_ISO_EDGE *isoe = &(edges[i]);
2971  LWLINE *edge = isoe->geom;
2972  POINTARRAY *epa = edge->points;
2973  POINT2D p2, pt;
2974  int match = 0;
2975  uint32_t j;
2976 
2977  /* Skip if the edge is a dangling one */
2978  if ( isoe->face_left == isoe->face_right )
2979  {
2980  LWDEBUGF(3, "_lwt_FindNextRingEdge: edge %" LWTFMT_ELEMID
2981  " has same face (%" LWTFMT_ELEMID
2982  ") on both sides, skipping",
2983  isoe->edge_id, isoe->face_left);
2984  continue;
2985  }
2986 
2987  if (epa->npoints < 2)
2988  {
2989  LWDEBUGF(3, "_lwt_FindNextRingEdge: edge %" LWTFMT_ELEMID
2990  " has only %"PRIu32" points",
2991  isoe->edge_id, epa->npoints);
2992  continue;
2993  }
2994 
2995 #if 0
2996  size_t sz;
2997  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " is %s",
2998  isoe->edge_id,
2999  lwgeom_to_wkt(lwline_as_lwgeom(edge), WKT_EXTENDED, 2, &sz));
3000 #endif
3001 
3002  /* ptarray_remove_repeated_points ? */
3003 
3004  getPoint2d_p(epa, 0, &p2);
3005  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " 'first' point is %g,%g",
3006  isoe->edge_id, p2.x, p2.y);
3007  LWDEBUGF(1, "Rings's 'from' point is still %g,%g", p1.x, p1.y);
3008  if ( p2d_same(&p1, &p2) )
3009  {
3010  LWDEBUG(1, "p2d_same(p1,p2) returned true");
3011  LWDEBUGF(1, "First point of edge %" LWTFMT_ELEMID
3012  " matches ring vertex %d", isoe->edge_id, from);
3013  /* first point matches, let's check next non-equal one */
3014  for ( j=1; j<epa->npoints; ++j )
3015  {
3016  getPoint2d_p(epa, j, &p2);
3017  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " 'next' point %d is %g,%g",
3018  isoe->edge_id, j, p2.x, p2.y);
3019  /* we won't check duplicated edge points */
3020  if ( p2d_same(&p1, &p2) ) continue;
3021  /* we assume there are no duplicated points in ring */
3022  getPoint2d_p(ring, from+1, &pt);
3023  LWDEBUGF(1, "Ring's point %d is %g,%g",
3024  from+1, pt.x, pt.y);
3025  match = p2d_same(&pt, &p2);
3026  break; /* we want to check a single non-equal next vertex */
3027  }
3028 #if POSTGIS_DEBUG_LEVEL > 0
3029  if ( match ) {
3030  LWDEBUGF(1, "Prev point of edge %" LWTFMT_ELEMID
3031  " matches ring vertex %d", isoe->edge_id, from+1);
3032  } else {
3033  LWDEBUGF(1, "Prev point of edge %" LWTFMT_ELEMID
3034  " does not match ring vertex %d", isoe->edge_id, from+1);
3035  }
3036 #endif
3037  }
3038 
3039  if ( ! match )
3040  {
3041  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " did not match as forward",
3042  isoe->edge_id);
3043  getPoint2d_p(epa, epa->npoints-1, &p2);
3044  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " 'last' point is %g,%g",
3045  isoe->edge_id, p2.x, p2.y);
3046  if ( p2d_same(&p1, &p2) )
3047  {
3048  LWDEBUGF(1, "Last point of edge %" LWTFMT_ELEMID
3049  " matches ring vertex %d", isoe->edge_id, from);
3050  /* last point matches, let's check next non-equal one */
3051  for ( j=2; j<=epa->npoints; j++ )
3052  {
3053  getPoint2d_p(epa, epa->npoints - j, &p2);
3054  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " 'prev' point %d is %g,%g",
3055  isoe->edge_id, epa->npoints - j, p2.x, p2.y);
3056  /* we won't check duplicated edge points */
3057  if ( p2d_same(&p1, &p2) ) continue;
3058  /* we assume there are no duplicated points in ring */
3059  getPoint2d_p(ring, from+1, &pt);
3060  LWDEBUGF(1, "Ring's point %d is %g,%g",
3061  from+1, pt.x, pt.y);
3062  match = p2d_same(&pt, &p2);
3063  break; /* we want to check a single non-equal next vertex */
3064  }
3065  }
3066 #if POSTGIS_DEBUG_LEVEL > 0
3067  if ( match ) {
3068  LWDEBUGF(1, "Prev point of edge %" LWTFMT_ELEMID
3069  " matches ring vertex %d", isoe->edge_id, from+1);
3070  } else {
3071  LWDEBUGF(1, "Prev point of edge %" LWTFMT_ELEMID
3072  " does not match ring vertex %d", isoe->edge_id, from+1);
3073  }
3074 #endif
3075  }
3076 
3077  if ( match ) return i;
3078 
3079  }
3080 
3081  return -1;
3082 }
3083 
3084 /* Reverse values in array between "from" (inclusive)
3085  * and "to" (exclusive) indexes */
3086 static void
3087 _lwt_ReverseElemidArray(LWT_ELEMID *ary, int from, int to)
3088 {
3089  LWT_ELEMID t;
3090  while (from < to)
3091  {
3092  t = ary[from];
3093  ary[from++] = ary[to];
3094  ary[to--] = t;
3095  }
3096 }
3097 
3098 /* Rotate values in array between "from" (inclusive)
3099  * and "to" (exclusive) indexes, so that "rotidx" is
3100  * the new value at "from" */
3101 static void
3102 _lwt_RotateElemidArray(LWT_ELEMID *ary, int from, int to, int rotidx)
3103 {
3104  _lwt_ReverseElemidArray(ary, from, rotidx-1);
3105  _lwt_ReverseElemidArray(ary, rotidx, to-1);
3106  _lwt_ReverseElemidArray(ary, from, to-1);
3107 }
3108 
3109 
3110 int
3112 {
3113  LWGEOM *face;
3114  LWPOLY *facepoly;
3115  LWT_ISO_EDGE *edges;
3116  int numfaceedges;
3117  int fields;
3118  uint32_t i;
3119  int nseid = 0; /* number of signed edge ids */
3120  int prevseid;
3121  LWT_ELEMID *seid; /* signed edge ids */
3122 
3123  /* Get list of face edges */
3124  numfaceedges = 1;
3125  fields = LWT_COL_EDGE_EDGE_ID |
3129  ;
3130  edges = lwt_be_getEdgeByFace( topo, &face_id, &numfaceedges, fields, NULL );
3131  if ( numfaceedges == -1 ) {
3132  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3133  return -1;
3134  }
3135  if ( ! numfaceedges ) return 0; /* no edges in output */
3136 
3137  /* order edges by occurrence in face */
3138 
3139  face = _lwt_FaceByEdges(topo, edges, numfaceedges);
3140  if ( ! face )
3141  {
3142  /* _lwt_FaceByEdges should have already invoked lwerror in this case */
3143  _lwt_release_edges(edges, numfaceedges);
3144  return -1;
3145  }
3146 
3147  if ( lwgeom_is_empty(face) )
3148  {
3149  /* no edges in output */
3150  _lwt_release_edges(edges, numfaceedges);
3151  lwgeom_free(face);
3152  return 0;
3153  }
3154 
3155  /* force_lhr, if the face is not the universe */
3156  /* _lwt_FaceByEdges seems to guaranteed RHR */
3157  /* lwgeom_force_clockwise(face); */
3158  if ( face_id ) lwgeom_reverse_in_place(face);
3159 
3160 #if 0
3161  {
3162  size_t sz;
3163  char *wkt = lwgeom_to_wkt(face, WKT_EXTENDED, 6, &sz);
3164  LWDEBUGF(1, "Geometry of face %" LWTFMT_ELEMID " is: %s",
3165  face_id, wkt);
3166  lwfree(wkt);
3167  }
3168 #endif
3169 
3170  facepoly = lwgeom_as_lwpoly(face);
3171  if ( ! facepoly )
3172  {
3173  _lwt_release_edges(edges, numfaceedges);
3174  lwgeom_free(face);
3175  lwerror("Geometry of face %" LWTFMT_ELEMID " is not a polygon", face_id);
3176  return -1;
3177  }
3178 
3179  nseid = prevseid = 0;
3180  seid = lwalloc( sizeof(LWT_ELEMID) * numfaceedges );
3181 
3182  /* for each ring of the face polygon... */
3183  for ( i=0; i<facepoly->nrings; ++i )
3184  {
3185  const POINTARRAY *ring = facepoly->rings[i];
3186  int32_t j = 0;
3187  LWT_ISO_EDGE *nextedge;
3188  LWLINE *nextline;
3189 
3190  LWDEBUGF(1, "Ring %d has %d points", i, ring->npoints);
3191 
3192  while ( j < (int32_t) ring->npoints-1 )
3193  {
3194  LWDEBUGF(1, "Looking for edge covering ring %d from vertex %d",
3195  i, j);
3196 
3197  int edgeno = _lwt_FindNextRingEdge(ring, j, edges, numfaceedges);
3198  if ( edgeno == -1 )
3199  {
3200  /* should never happen */
3201  _lwt_release_edges(edges, numfaceedges);
3202  lwgeom_free(face);
3203  lwfree(seid);
3204  lwerror("No edge (among %d) found to be defining geometry of face %"
3205  LWTFMT_ELEMID, numfaceedges, face_id);
3206  return -1;
3207  }
3208 
3209  nextedge = &(edges[edgeno]);
3210  nextline = nextedge->geom;
3211 
3212  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID
3213  " covers ring %d from vertex %d to %d",
3214  nextedge->edge_id, i, j, j + nextline->points->npoints - 1);
3215 
3216 #if 0
3217  {
3218  size_t sz;
3219  char *wkt = lwgeom_to_wkt(lwline_as_lwgeom(nextline), WKT_EXTENDED, 6, &sz);
3220  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " is %s",
3221  nextedge->edge_id, wkt);
3222  lwfree(wkt);
3223  }
3224 #endif
3225 
3226  j += nextline->points->npoints - 1;
3227 
3228  /* Add next edge to the output array */
3229  seid[nseid++] = nextedge->face_left == face_id ?
3230  nextedge->edge_id :
3231  -nextedge->edge_id;
3232 
3233  /* avoid checking again on next time turn */
3234  nextedge->face_left = nextedge->face_right = -1;
3235  }
3236 
3237  /* now "scroll" the list of edges so that the one
3238  * with smaller absolute edge_id is first */
3239  /* Range is: [prevseid, nseid) -- [inclusive, exclusive) */
3240  if ( (nseid - prevseid) > 1 )
3241  {{
3242  LWT_ELEMID minid = 0;
3243  int minidx = 0;
3244  LWDEBUGF(1, "Looking for smallest id among the %d edges "
3245  "composing ring %d", (nseid-prevseid), i);
3246  for ( j=prevseid; j<nseid; ++j )
3247  {
3248  LWT_ELEMID id = llabs(seid[j]);
3249  LWDEBUGF(1, "Abs id of edge in pos %d is %" LWTFMT_ELEMID, j, id);
3250  if ( ! minid || id < minid )
3251  {
3252  minid = id;
3253  minidx = j;
3254  }
3255  }
3256  LWDEBUGF(1, "Smallest id is %" LWTFMT_ELEMID
3257  " at position %d", minid, minidx);
3258  if ( minidx != prevseid )
3259  {
3260  _lwt_RotateElemidArray(seid, prevseid, nseid, minidx);
3261  }
3262  }}
3263 
3264  prevseid = nseid;
3265  }
3266 
3267  lwgeom_free(face);
3268  _lwt_release_edges(edges, numfaceedges);
3269 
3270  *out = seid;
3271  return nseid;
3272 }
3273 
3274 static GEOSGeometry *
3275 _lwt_EdgeMotionArea(LWLINE *geom, int isclosed)
3276 {
3277  GEOSGeometry *gg;
3278  POINT4D p4d;
3279  POINTARRAY *pa;
3280  POINTARRAY **pas;
3281  LWPOLY *poly;
3282  LWGEOM *g;
3283 
3284  pas = lwalloc(sizeof(POINTARRAY*));
3285 
3286  initGEOS(lwnotice, lwgeom_geos_error);
3287 
3288  if ( isclosed )
3289  {
3290  pas[0] = ptarray_clone_deep( geom->points );
3291  poly = lwpoly_construct(0, 0, 1, pas);
3292  gg = LWGEOM2GEOS( lwpoly_as_lwgeom(poly), 0 );
3293  lwpoly_free(poly); /* should also delete the pointarrays */
3294  }
3295  else
3296  {
3297  pa = geom->points;
3298  getPoint4d_p(pa, 0, &p4d);
3299  pas[0] = ptarray_clone_deep( pa );
3300  /* don't bother dup check */
3301  if ( LW_FAILURE == ptarray_append_point(pas[0], &p4d, LW_TRUE) )
3302  {
3303  ptarray_free(pas[0]);
3304  lwfree(pas);
3305  lwerror("Could not append point to pointarray");
3306  return NULL;
3307  }
3308  poly = lwpoly_construct(0, NULL, 1, pas);
3309  /* make valid, in case the edge self-intersects on its first-last
3310  * vertex segment */
3312  lwpoly_free(poly); /* should also delete the pointarrays */
3313  if ( ! g )
3314  {
3315  lwerror("Could not make edge motion area valid");
3316  return NULL;
3317  }
3318  gg = LWGEOM2GEOS(g, 0);
3319  lwgeom_free(g);
3320  }
3321  if ( ! gg )
3322  {
3323  lwerror("Could not convert old edge area geometry to GEOS: %s",
3325  return NULL;
3326  }
3327  return gg;
3328 }
3329 
3330 int
3332 {
3333  LWT_ISO_EDGE *oldedge;
3334  LWT_ISO_EDGE newedge;
3335  POINT2D p1, p2, pt;
3336  int i;
3337  int isclosed = 0;
3338 
3339  /* curve must be simple */
3340  if ( ! lwgeom_is_simple(lwline_as_lwgeom(geom)) )
3341  {
3342  lwerror("SQL/MM Spatial exception - curve not simple");
3343  return -1;
3344  }
3345 
3346  i = 1;
3347  oldedge = lwt_be_getEdgeById(topo, &edge_id, &i, LWT_COL_EDGE_ALL);
3348  if ( ! oldedge )
3349  {
3350  LWDEBUGF(1, "lwt_ChangeEdgeGeom: "
3351  "lwt_be_getEdgeById returned NULL and set i=%d", i);
3352  if ( i == -1 )
3353  {
3354  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3355  return -1;
3356  }
3357  else if ( i == 0 )
3358  {
3359  lwerror("SQL/MM Spatial exception - non-existent edge %"
3360  LWTFMT_ELEMID, edge_id);
3361  return -1;
3362  }
3363  else
3364  {
3365  lwerror("Backend coding error: getEdgeById callback returned NULL "
3366  "but numelements output parameter has value %d "
3367  "(expected 0 or 1)", i);
3368  return -1;
3369  }
3370  }
3371 
3372  LWDEBUGF(1, "lwt_ChangeEdgeGeom: "
3373  "old edge has %d points, new edge has %d points",
3374  oldedge->geom->points->npoints, geom->points->npoints);
3375 
3376  /*
3377  * e) Check StartPoint consistency
3378  */
3379  getPoint2d_p(oldedge->geom->points, 0, &p1);
3380  getPoint2d_p(geom->points, 0, &pt);
3381  if ( ! p2d_same(&p1, &pt) )
3382  {
3383  _lwt_release_edges(oldedge, 1);
3384  lwerror("SQL/MM Spatial exception - "
3385  "start node not geometry start point.");
3386  return -1;
3387  }
3388 
3389  /*
3390  * f) Check EndPoint consistency
3391  */
3392  if ( oldedge->geom->points->npoints < 2 )
3393  {
3394  _lwt_release_edges(oldedge, 1);
3395  lwerror("Corrupted topology: edge %" LWTFMT_ELEMID
3396  " has less than 2 vertices", oldedge->edge_id);
3397  return -1;
3398  }
3399  getPoint2d_p(oldedge->geom->points, oldedge->geom->points->npoints-1, &p2);
3400  if ( geom->points->npoints < 2 )
3401  {
3402  _lwt_release_edges(oldedge, 1);
3403  lwerror("Invalid edge: less than 2 vertices");
3404  return -1;
3405  }
3406  getPoint2d_p(geom->points, geom->points->npoints-1, &pt);
3407  if ( ! p2d_same(&pt, &p2) )
3408  {
3409  _lwt_release_edges(oldedge, 1);
3410  lwerror("SQL/MM Spatial exception - "
3411  "end node not geometry end point.");
3412  return -1;
3413  }
3414 
3415  /* Not in the specs:
3416  * if the edge is closed, check we didn't change winding !
3417  * (should be part of isomorphism checking)
3418  */
3419  if ( oldedge->start_node == oldedge->end_node )
3420  {
3421  isclosed = 1;
3422 #if 1 /* TODO: this is actually bogus as a test */
3423  /* check for valid edge (distinct vertices must exist) */
3424  if ( ! _lwt_GetInteriorEdgePoint(geom, &pt) )
3425  {
3426  _lwt_release_edges(oldedge, 1);
3427  lwerror("Invalid edge (no two distinct vertices exist)");
3428  return -1;
3429  }
3430 #endif
3431 
3432  if ( ptarray_isccw(oldedge->geom->points) !=
3433  ptarray_isccw(geom->points) )
3434  {
3435  _lwt_release_edges(oldedge, 1);
3436  lwerror("Edge twist at node POINT(%g %g)", p1.x, p1.y);
3437  return -1;
3438  }
3439  }
3440 
3441  if ( _lwt_CheckEdgeCrossing(topo, oldedge->start_node,
3442  oldedge->end_node, geom, edge_id ) )
3443  {
3444  /* would have called lwerror already, leaking :( */
3445  _lwt_release_edges(oldedge, 1);
3446  return -1;
3447  }
3448 
3449  LWDEBUG(1, "lwt_ChangeEdgeGeom: "
3450  "edge crossing check passed ");
3451 
3452  /*
3453  * Not in the specs:
3454  * Check topological isomorphism
3455  */
3456 
3457  /* Check that the "motion range" doesn't include any node */
3458  // 1. compute combined bbox of old and new edge
3459  GBOX mbox; /* motion box */
3460  lwgeom_add_bbox((LWGEOM*)oldedge->geom); /* just in case */
3461  lwgeom_add_bbox((LWGEOM*)geom); /* just in case */
3462  gbox_union(oldedge->geom->bbox, geom->bbox, &mbox);
3463  // 2. fetch all nodes in the combined box
3464  LWT_ISO_NODE *nodes;
3465  int numnodes;
3466  nodes = lwt_be_getNodeWithinBox2D(topo, &mbox, &numnodes,
3467  LWT_COL_NODE_ALL, 0);
3468  LWDEBUGF(1, "lwt_be_getNodeWithinBox2D returned %d nodes", numnodes);
3469  if ( numnodes == -1 ) {
3470  _lwt_release_edges(oldedge, 1);
3471  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3472  return -1;
3473  }
3474  // 3. if any node beside endnodes are found:
3475  if ( numnodes > ( 1 + isclosed ? 0 : 1 ) )
3476  {{
3477  GEOSGeometry *oarea, *narea;
3478  const GEOSPreparedGeometry *oareap, *nareap;
3479 
3480  initGEOS(lwnotice, lwgeom_geos_error);
3481 
3482  oarea = _lwt_EdgeMotionArea(oldedge->geom, isclosed);
3483  if ( ! oarea )
3484  {
3485  _lwt_release_edges(oldedge, 1);
3486  lwerror("Could not compute edge motion area for old edge");
3487  return -1;
3488  }
3489 
3490  narea = _lwt_EdgeMotionArea(geom, isclosed);
3491  if ( ! narea )
3492  {
3493  GEOSGeom_destroy(oarea);
3494  _lwt_release_edges(oldedge, 1);
3495  lwerror("Could not compute edge motion area for new edge");
3496  return -1;
3497  }
3498 
3499  // 3.2. bail out if any node is in one and not the other
3500  oareap = GEOSPrepare( oarea );
3501  nareap = GEOSPrepare( narea );
3502  for (i=0; i<numnodes; ++i)
3503  {
3504  LWT_ISO_NODE *n = &(nodes[i]);
3505  GEOSGeometry *ngg;
3506  int ocont, ncont;
3507  size_t sz;
3508  char *wkt;
3509  if ( n->node_id == oldedge->start_node ) continue;
3510  if ( n->node_id == oldedge->end_node ) continue;
3511  ngg = LWGEOM2GEOS( lwpoint_as_lwgeom(n->geom) , 0);
3512  ocont = GEOSPreparedContains( oareap, ngg );
3513  ncont = GEOSPreparedContains( nareap, ngg );
3514  GEOSGeom_destroy(ngg);
3515  if (ocont == 2 || ncont == 2)
3516  {
3517  _lwt_release_nodes(nodes, numnodes);
3518  GEOSPreparedGeom_destroy(oareap);
3519  GEOSGeom_destroy(oarea);
3520  GEOSPreparedGeom_destroy(nareap);
3521  GEOSGeom_destroy(narea);
3522  lwerror("GEOS exception on PreparedContains: %s", lwgeom_geos_errmsg);
3523  return -1;
3524  }
3525  if (ocont != ncont)
3526  {
3527  GEOSPreparedGeom_destroy(oareap);
3528  GEOSGeom_destroy(oarea);
3529  GEOSPreparedGeom_destroy(nareap);
3530  GEOSGeom_destroy(narea);
3531  wkt = lwgeom_to_wkt(lwpoint_as_lwgeom(n->geom), WKT_ISO, 15, &sz);
3532  _lwt_release_nodes(nodes, numnodes);
3533  lwerror("Edge motion collision at %s", wkt);
3534  lwfree(wkt); /* would not necessarely reach this point */
3535  return -1;
3536  }
3537  }
3538  GEOSPreparedGeom_destroy(oareap);
3539  GEOSGeom_destroy(oarea);
3540  GEOSPreparedGeom_destroy(nareap);
3541  GEOSGeom_destroy(narea);
3542  }}
3543  if ( numnodes ) _lwt_release_nodes(nodes, numnodes);
3544 
3545  LWDEBUG(1, "nodes containment check passed");
3546 
3547  /*
3548  * Check edge adjacency before
3549  * TODO: can be optimized to gather azimuths of all edge ends once
3550  */
3551 
3552  edgeend span_pre, epan_pre;
3553  /* initialize span_pre.myaz and epan_pre.myaz with existing edge */
3554  i = _lwt_InitEdgeEndByLine(&span_pre, &epan_pre,
3555  oldedge->geom, &p1, &p2);
3556  if ( i ) return -1; /* lwerror should have been raised */
3557  _lwt_FindAdjacentEdges( topo, oldedge->start_node, &span_pre,
3558  isclosed ? &epan_pre : NULL, edge_id );
3559  _lwt_FindAdjacentEdges( topo, oldedge->end_node, &epan_pre,
3560  isclosed ? &span_pre : NULL, edge_id );
3561 
3562  LWDEBUGF(1, "edges adjacent to old edge are %" LWTFMT_ELEMID
3563  " and %" LWTFMT_ELEMID " (first point), %" LWTFMT_ELEMID
3564  " and %" LWTFMT_ELEMID " (last point)",
3565  span_pre.nextCW, span_pre.nextCCW,
3566  epan_pre.nextCW, epan_pre.nextCCW);
3567 
3568  /* update edge geometry */
3569  newedge.edge_id = edge_id;
3570  newedge.geom = geom;
3571  i = lwt_be_updateEdgesById(topo, &newedge, 1, LWT_COL_EDGE_GEOM);
3572  if ( i == -1 )
3573  {
3574  _lwt_release_edges(oldedge, 1);
3575  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3576  return -1;
3577  }
3578  if ( ! i )
3579  {
3580  _lwt_release_edges(oldedge, 1);
3581  lwerror("Unexpected error: %d edges updated when expecting 1", i);
3582  return -1;
3583  }
3584 
3585  /*
3586  * Check edge adjacency after
3587  */
3588  edgeend span_post, epan_post;
3589  i = _lwt_InitEdgeEndByLine(&span_post, &epan_post, geom, &p1, &p2);
3590  if ( i ) return -1; /* lwerror should have been raised */
3591  /* initialize epan_post.myaz and epan_post.myaz */
3592  i = _lwt_InitEdgeEndByLine(&span_post, &epan_post,
3593  geom, &p1, &p2);
3594  if ( i ) return -1; /* lwerror should have been raised */
3595  _lwt_FindAdjacentEdges( topo, oldedge->start_node, &span_post,
3596  isclosed ? &epan_post : NULL, edge_id );
3597  _lwt_FindAdjacentEdges( topo, oldedge->end_node, &epan_post,
3598  isclosed ? &span_post : NULL, edge_id );
3599 
3600  LWDEBUGF(1, "edges adjacent to new edge are %" LWTFMT_ELEMID
3601  " and %" LWTFMT_ELEMID " (first point), %" LWTFMT_ELEMID
3602  " and %" LWTFMT_ELEMID " (last point)",
3603  span_pre.nextCW, span_pre.nextCCW,
3604  epan_pre.nextCW, epan_pre.nextCCW);
3605 
3606 
3607  /* Bail out if next CW or CCW edge on start node changed */
3608  if ( span_pre.nextCW != span_post.nextCW ||
3609  span_pre.nextCCW != span_post.nextCCW )
3610  {{
3611  LWT_ELEMID nid = oldedge->start_node;
3612  _lwt_release_edges(oldedge, 1);
3613  lwerror("Edge changed disposition around start node %"
3614  LWTFMT_ELEMID, nid);
3615  return -1;
3616  }}
3617 
3618  /* Bail out if next CW or CCW edge on end node changed */
3619  if ( epan_pre.nextCW != epan_post.nextCW ||
3620  epan_pre.nextCCW != epan_post.nextCCW )
3621  {{
3622  LWT_ELEMID nid = oldedge->end_node;
3623  _lwt_release_edges(oldedge, 1);
3624  lwerror("Edge changed disposition around end node %"
3625  LWTFMT_ELEMID, nid);
3626  return -1;
3627  }}
3628 
3629  /*
3630  -- Update faces MBR of left and right faces
3631  -- TODO: think about ways to optimize this part, like see if
3632  -- the old edge geometry partecipated in the definition
3633  -- of the current MBR (for shrinking) or the new edge MBR
3634  -- would be larger than the old face MBR...
3635  --
3636  */
3637  const GBOX* oldbox = lwgeom_get_bbox(lwline_as_lwgeom(oldedge->geom));
3638  const GBOX* newbox = lwgeom_get_bbox(lwline_as_lwgeom(geom));
3639  if ( ! gbox_same(oldbox, newbox) )
3640  {{
3641  int facestoupdate = 0;
3642  LWT_ISO_FACE faces[2];
3643  LWGEOM *nface1 = NULL;
3644  LWGEOM *nface2 = NULL;
3645  if ( oldedge->face_left > 0 )
3646  {
3647  nface1 = lwt_GetFaceGeometry(topo, oldedge->face_left);
3648  if ( ! nface1 )
3649  {
3650  lwerror("lwt_ChangeEdgeGeom could not construct face %"
3651  LWTFMT_ELEMID ", on the left of edge %" LWTFMT_ELEMID,
3652  oldedge->face_left, edge_id);
3653  return -1;
3654  }
3655  #if 0
3656  {
3657  size_t sz;
3658  char *wkt = lwgeom_to_wkt(nface1, WKT_EXTENDED, 2, &sz);
3659  LWDEBUGF(1, "new geometry of face left (%d): %s", (int)oldedge->face_left, wkt);
3660  lwfree(wkt);
3661  }
3662  #endif
3663  lwgeom_add_bbox(nface1);
3664  faces[facestoupdate].face_id = oldedge->face_left;
3665  /* ownership left to nface */
3666  faces[facestoupdate++].mbr = nface1->bbox;
3667  }
3668  if ( oldedge->face_right > 0
3669  /* no need to update twice the same face.. */
3670  && oldedge->face_right != oldedge->face_left )
3671  {
3672  nface2 = lwt_GetFaceGeometry(topo, oldedge->face_right);
3673  if ( ! nface2 )
3674  {
3675  lwerror("lwt_ChangeEdgeGeom could not construct face %"
3676  LWTFMT_ELEMID ", on the right of edge %" LWTFMT_ELEMID,
3677  oldedge->face_right, edge_id);
3678  return -1;
3679  }
3680  #if 0
3681  {
3682  size_t sz;
3683  char *wkt = lwgeom_to_wkt(nface2, WKT_EXTENDED, 2, &sz);
3684  LWDEBUGF(1, "new geometry of face right (%d): %s", (int)oldedge->face_right, wkt);
3685  lwfree(wkt);
3686  }
3687  #endif
3688  lwgeom_add_bbox(nface2);
3689  faces[facestoupdate].face_id = oldedge->face_right;
3690  faces[facestoupdate++].mbr = nface2->bbox; /* ownership left to nface */
3691  }
3692  LWDEBUGF(1, "%d faces to update", facestoupdate);
3693  if ( facestoupdate )
3694  {
3695  i = lwt_be_updateFacesById( topo, &(faces[0]), facestoupdate );
3696  if ( i != facestoupdate )
3697  {
3698  if ( nface1 ) lwgeom_free(nface1);
3699  if ( nface2 ) lwgeom_free(nface2);
3700  _lwt_release_edges(oldedge, 1);
3701  if ( i == -1 )
3702  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3703  else
3704  lwerror("Unexpected error: %d faces found when expecting 1", i);
3705  return -1;
3706  }
3707  }
3708  if ( nface1 ) lwgeom_free(nface1);
3709  if ( nface2 ) lwgeom_free(nface2);
3710  }} else {{
3711  lwnotice("BBOX of changed edge did not change");
3712  }}
3713 
3714  LWDEBUG(1, "all done, cleaning up edges");
3715 
3716  _lwt_release_edges(oldedge, 1);
3717  return 0; /* success */
3718 }
3719 
3720 /* Only return CONTAINING_FACE in the node object */
3721 static LWT_ISO_NODE *
3723 {
3724  LWT_ISO_NODE *node;
3725  int n = 1;
3726 
3727  node = lwt_be_getNodeById( topo, &nid, &n, LWT_COL_NODE_CONTAINING_FACE );
3728  if ( n < 0 ) {
3729  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3730  return 0;
3731  }
3732  if ( n < 1 ) {
3733  lwerror("SQL/MM Spatial exception - non-existent node");
3734  return 0;
3735  }
3736  if ( node->containing_face == -1 )
3737  {
3738  lwfree(node);
3739  lwerror("SQL/MM Spatial exception - not isolated node");
3740  return 0;
3741  }
3742 
3743  return node;
3744 }
3745 
3746 int
3748 {
3749  LWT_ISO_NODE *node;
3750  int ret;
3751 
3752  node = _lwt_GetIsoNode( topo, nid );
3753  if ( ! node ) return -1;
3754 
3755  if ( lwt_be_ExistsCoincidentNode(topo, pt) )
3756  {
3757  lwfree(node);
3758  lwerror("SQL/MM Spatial exception - coincident node");
3759  return -1;
3760  }
3761 
3762  if ( lwt_be_ExistsEdgeIntersectingPoint(topo, pt) )
3763  {
3764  lwfree(node);
3765  lwerror("SQL/MM Spatial exception - edge crosses node.");
3766  return -1;
3767  }
3768 
3769  /* TODO: check that the new point is in the same containing face !
3770  * See https://trac.osgeo.org/postgis/ticket/3232
3771  */
3772 
3773  node->node_id = nid;
3774  node->geom = pt;
3775  ret = lwt_be_updateNodesById(topo, node, 1,
3777  if ( ret == -1 ) {
3778  lwfree(node);
3779  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3780  return -1;
3781  }
3782 
3783  lwfree(node);
3784  return 0;
3785 }
3786 
3787 int
3789 {
3790  LWT_ISO_NODE *node;
3791  int n = 1;
3792 
3793  node = _lwt_GetIsoNode( topo, nid );
3794  if ( ! node ) return -1;
3795 
3796  n = lwt_be_deleteNodesById( topo, &nid, n );
3797  if ( n == -1 )
3798  {
3799  lwfree(node);
3800  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3801  return -1;
3802  }
3803  if ( n != 1 )
3804  {
3805  lwfree(node);
3806  lwerror("Unexpected error: %d nodes deleted when expecting 1", n);
3807  return -1;
3808  }
3809 
3810  /* TODO: notify to caller about node being removed ?
3811  * See https://trac.osgeo.org/postgis/ticket/3231
3812  */
3813 
3814  lwfree(node);
3815  return 0; /* success */
3816 }
3817 
3818 int
3820 {
3821  LWT_ISO_EDGE deledge;
3822  LWT_ISO_EDGE *edge;
3823  LWT_ELEMID nid[2];
3824  LWT_ISO_NODE upd_node[2];
3825  LWT_ELEMID containing_face;
3826  int n = 1;
3827  int i;
3828 
3829  edge = lwt_be_getEdgeById( topo, &id, &n, LWT_COL_EDGE_START_NODE|
3833  if ( ! edge )
3834  {
3835  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3836  return -1;
3837  }
3838  if ( ! n )
3839  {
3840  lwerror("SQL/MM Spatial exception - non-existent edge");
3841  return -1;
3842  }
3843  if ( n > 1 )
3844  {
3845  lwfree(edge);
3846  lwerror("Corrupted topology: more than a single edge have id %"
3847  LWTFMT_ELEMID, id);
3848  return -1;
3849  }
3850 
3851  if ( edge[0].face_left != edge[0].face_right )
3852  {
3853  lwfree(edge);
3854  lwerror("SQL/MM Spatial exception - not isolated edge");
3855  return -1;
3856  }
3857  containing_face = edge[0].face_left;
3858 
3859  nid[0] = edge[0].start_node;
3860  nid[1] = edge[0].end_node;
3861  lwfree(edge);
3862 
3863  n = 2;
3864  edge = lwt_be_getEdgeByNode( topo, nid, &n, LWT_COL_EDGE_EDGE_ID );
3865  if ((n == -1) || (edge == NULL))
3866  {
3867  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3868  return -1;
3869  }
3870  for (i = 0; i < n; ++i)
3871  {
3872  if (edge[i].edge_id != id)
3873  {
3874  lwfree(edge);
3875  lwerror("SQL/MM Spatial exception - not isolated edge");
3876  return -1;
3877  }
3878  }
3879  lwfree(edge);
3880 
3881  deledge.edge_id = id;
3882  n = lwt_be_deleteEdges( topo, &deledge, LWT_COL_EDGE_EDGE_ID );
3883  if ( n == -1 )
3884  {
3885  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3886  return -1;
3887  }
3888  if ( n != 1 )
3889  {
3890  lwerror("Unexpected error: %d edges deleted when expecting 1", n);
3891  return -1;
3892  }
3893 
3894  upd_node[0].node_id = nid[0];
3895  upd_node[0].containing_face = containing_face;
3896  n = 1;
3897  if ( nid[1] != nid[0] ) {
3898  upd_node[1].node_id = nid[1];
3899  upd_node[1].containing_face = containing_face;
3900  ++n;
3901  }
3902  n = lwt_be_updateNodesById(topo, upd_node, n,
3904  if ( n == -1 )
3905  {
3906  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
3907  return -1;
3908  }
3909 
3910  /* TODO: notify to caller about edge being removed ?
3911  * See https://trac.osgeo.org/postgis/ticket/3248
3912  */
3913 
3914  return 0; /* success */
3915 }
3916 
3917 /* Used by _lwt_RemEdge to update edge face ref on healing
3918  *
3919  * @param of old face id (never 0 as you cannot remove face 0)
3920  * @param nf new face id
3921  * @return 0 on success, -1 on backend error
3922  */
3923 static int
3925 {
3926  LWT_ISO_EDGE sel_edge, upd_edge;
3927  int ret;
3928 
3929  assert( of != 0 );
3930 
3931  /* Update face_left for all edges still referencing old face */
3932  sel_edge.face_left = of;
3933  upd_edge.face_left = nf;
3934  ret = lwt_be_updateEdges(topo, &sel_edge, LWT_COL_EDGE_FACE_LEFT,
3935  &upd_edge, LWT_COL_EDGE_FACE_LEFT,
3936  NULL, 0);
3937  if ( ret == -1 ) return -1;
3938 
3939  /* Update face_right for all edges still referencing old face */
3940  sel_edge.face_right = of;
3941  upd_edge.face_right = nf;
3942  ret = lwt_be_updateEdges(topo, &sel_edge, LWT_COL_EDGE_FACE_RIGHT,
3943  &upd_edge, LWT_COL_EDGE_FACE_RIGHT,
3944  NULL, 0);
3945  if ( ret == -1 ) return -1;
3946 
3947  return 0;
3948 }
3949 
3950 /* Used by _lwt_RemEdge to update node face ref on healing
3951  *
3952  * @param of old face id (never 0 as you cannot remove face 0)
3953  * @param nf new face id
3954  * @return 0 on success, -1 on backend error
3955  */
3956 static int
3958 {
3959  LWT_ISO_NODE sel, upd;
3960  int ret;
3961 
3962  assert( of != 0 );
3963 
3964  /* Update face_left for all edges still referencing old face */
3965  sel.containing_face = of;
3966  upd.containing_face = nf;
3969  NULL, 0);
3970  if ( ret == -1 ) return -1;
3971 
3972  return 0;
3973 }
3974 
3975 /* Used by lwt_RemEdgeModFace and lwt_RemEdgeNewFaces
3976  *
3977  * Returns -1 on error, identifier of the face that takes up the space
3978  * previously occupied by the removed edge if modFace is 1, identifier of
3979  * the created face (0 if none) if modFace is 0.
3980  */
3981 static LWT_ELEMID
3982 _lwt_RemEdge( LWT_TOPOLOGY* topo, LWT_ELEMID edge_id, int modFace )
3983 {
3984  int i, nedges, nfaces, fields;
3985  LWT_ISO_EDGE *edge = NULL;
3986  LWT_ISO_EDGE *upd_edge = NULL;
3987  LWT_ISO_EDGE upd_edge_left[2];
3988  int nedge_left = 0;
3989  LWT_ISO_EDGE upd_edge_right[2];
3990  int nedge_right = 0;
3991  LWT_ISO_NODE upd_node[2];
3992  int nnode = 0;
3993  LWT_ISO_FACE *faces = NULL;
3994  LWT_ISO_FACE newface;
3995  LWT_ELEMID node_ids[2];
3996  LWT_ELEMID face_ids[2];
3997  int fnode_edges = 0; /* number of edges on the first node (excluded
3998  * the one being removed ) */
3999  int lnode_edges = 0; /* number of edges on the last node (excluded
4000  * the one being removed ) */
4001 
4002  newface.face_id = 0;
4003 
4004  i = 1;
4005  edge = lwt_be_getEdgeById(topo, &edge_id, &i, LWT_COL_EDGE_ALL);
4006  if ( ! edge )
4007  {
4008  LWDEBUGF(1, "lwt_be_getEdgeById returned NULL and set i=%d", i);
4009  if ( i == -1 )
4010  {
4011  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4012  return -1;
4013  }
4014  else if ( i == 0 )
4015  {
4016  lwerror("SQL/MM Spatial exception - non-existent edge %"
4017  LWTFMT_ELEMID, edge_id);
4018  return -1;
4019  }
4020  else
4021  {
4022  lwerror("Backend coding error: getEdgeById callback returned NULL "
4023  "but numelements output parameter has value %d "
4024  "(expected 0 or 1)", i);
4025  return -1;
4026  }
4027  }
4028 
4029  if ( ! lwt_be_checkTopoGeomRemEdge(topo, edge_id,
4030  edge->face_left, edge->face_right) )
4031  {
4033  return -1;
4034  }
4035 
4036  LWDEBUG(1, "Updating next_{right,left}_face of ring edges...");
4037 
4038  /* Update edge linking */
4039 
4040  nedges = 0;
4041  node_ids[nedges++] = edge->start_node;
4042  if ( edge->end_node != edge->start_node )
4043  {
4044  node_ids[nedges++] = edge->end_node;
4045  }
4049  upd_edge = lwt_be_getEdgeByNode( topo, &(node_ids[0]), &nedges, fields );
4050  if ( nedges == -1 ) {
4051  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4052  return -1;
4053  }
4054  nedge_left = nedge_right = 0;
4055  for ( i=0; i<nedges; ++i )
4056  {
4057  LWT_ISO_EDGE *e = &(upd_edge[i]);
4058  if ( e->edge_id == edge_id ) continue;
4059  if ( e->start_node == edge->start_node || e->end_node == edge->start_node )
4060  {
4061  ++fnode_edges;
4062  }
4063  if ( e->start_node == edge->end_node || e->end_node == edge->end_node )
4064  {
4065  ++lnode_edges;
4066  }
4067  if ( e->next_left == -edge_id )
4068  {
4069  upd_edge_left[nedge_left].edge_id = e->edge_id;
4070  upd_edge_left[nedge_left++].next_left =
4071  edge->next_left != edge_id ? edge->next_left : edge->next_right;
4072  }
4073  else if ( e->next_left == edge_id )
4074  {
4075  upd_edge_left[nedge_left].edge_id = e->edge_id;
4076  upd_edge_left[nedge_left++].next_left =
4077  edge->next_right != -edge_id ? edge->next_right : edge->next_left;
4078  }
4079 
4080  if ( e->next_right == -edge_id )
4081  {
4082  upd_edge_right[nedge_right].edge_id = e->edge_id;
4083  upd_edge_right[nedge_right++].next_right =
4084  edge->next_left != edge_id ? edge->next_left : edge->next_right;
4085  }
4086  else if ( e->next_right == edge_id )
4087  {
4088  upd_edge_right[nedge_right].edge_id = e->edge_id;
4089  upd_edge_right[nedge_right++].next_right =
4090  edge->next_right != -edge_id ? edge->next_right : edge->next_left;
4091  }
4092  }
4093 
4094  if ( nedge_left )
4095  {
4096  LWDEBUGF(1, "updating %d 'next_left' edges", nedge_left);
4097  /* update edges in upd_edge_left set next_left */
4098  i = lwt_be_updateEdgesById(topo, &(upd_edge_left[0]), nedge_left,
4100  if ( i == -1 )
4101  {
4102  _lwt_release_edges(edge, 1);
4103  lwfree(upd_edge);
4104  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4105  return -1;
4106  }
4107  }
4108  if ( nedge_right )
4109  {
4110  LWDEBUGF(1, "updating %d 'next_right' edges", nedge_right);
4111  /* update edges in upd_edge_right set next_right */
4112  i = lwt_be_updateEdgesById(topo, &(upd_edge_right[0]), nedge_right,
4114  if ( i == -1 )
4115  {
4116  _lwt_release_edges(edge, 1);
4117  lwfree(upd_edge);
4118  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4119  return -1;
4120  }
4121  }
4122  LWDEBUGF(1, "releasing %d updateable edges in %p", nedges, upd_edge);
4123  lwfree(upd_edge);
4124 
4125  /* Id of face that will take up all the space previously
4126  * taken by left and right faces of the edge */
4127  LWT_ELEMID floodface;
4128 
4129  /* Find floodface, and update its mbr if != 0 */
4130  if ( edge->face_left == edge->face_right )
4131  {
4132  floodface = edge->face_right;
4133  }
4134  else
4135  {
4136  /* Two faces healed */
4137  if ( edge->face_left == 0 || edge->face_right == 0 )
4138  {
4139  floodface = 0;
4140  LWDEBUG(1, "floodface is universe");
4141  }
4142  else
4143  {
4144  /* we choose right face as the face that will remain
4145  * to be symmetric with ST_AddEdgeModFace */
4146  floodface = edge->face_right;
4147  LWDEBUGF(1, "floodface is %" LWTFMT_ELEMID, floodface);
4148  /* update mbr of floodface as union of mbr of both faces */
4149  face_ids[0] = edge->face_left;
4150  face_ids[1] = edge->face_right;
4151  nfaces = 2;
4152  fields = LWT_COL_FACE_ALL;
4153  faces = lwt_be_getFaceById(topo, face_ids, &nfaces, fields);
4154  if ( nfaces == -1 ) {
4155  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4156  return -1;
4157  }
4158  GBOX *box1=NULL;
4159  GBOX *box2=NULL;
4160  for ( i=0; i<nfaces; ++i )
4161  {
4162  if ( faces[i].face_id == edge->face_left )
4163  {
4164  if ( ! box1 ) box1 = faces[i].mbr;
4165  else
4166  {
4167  i = edge->face_left;
4168  _lwt_release_edges(edge, 1);
4169  _lwt_release_faces(faces, nfaces);
4170  lwerror("corrupted topology: more than 1 face have face_id=%"
4171  LWTFMT_ELEMID, i);
4172  return -1;
4173  }
4174  }
4175  else if ( faces[i].face_id == edge->face_right )
4176  {
4177  if ( ! box2 ) box2 = faces[i].mbr;
4178  else
4179  {
4180  i = edge->face_right;
4181  _lwt_release_edges(edge, 1);
4182  _lwt_release_faces(faces, nfaces);
4183  lwerror("corrupted topology: more than 1 face have face_id=%"
4184  LWTFMT_ELEMID, i);
4185  return -1;
4186  }
4187  }
4188  else
4189  {
4190  i = faces[i].face_id;
4191  _lwt_release_edges(edge, 1);
4192  _lwt_release_faces(faces, nfaces);
4193  lwerror("Backend coding error: getFaceById returned face "
4194  "with non-requested id %" LWTFMT_ELEMID, i);
4195  return -1;
4196  }
4197  }
4198  if ( ! box1 ) {
4199  i = edge->face_left;
4200  _lwt_release_edges(edge, 1);
4201  _lwt_release_faces(faces, nfaces);
4202  lwerror("corrupted topology: no face have face_id=%"
4203  LWTFMT_ELEMID " (left face for edge %"
4204  LWTFMT_ELEMID ")", i, edge_id);
4205  return -1;
4206  }
4207  if ( ! box2 ) {
4208  i = edge->face_right;
4209  _lwt_release_edges(edge, 1);
4210  _lwt_release_faces(faces, nfaces);
4211  lwerror("corrupted topology: no face have face_id=%"
4212  LWTFMT_ELEMID " (right face for edge %"
4213  LWTFMT_ELEMID ")", i, edge_id);
4214  return -1;
4215  }
4216  gbox_merge(box2, box1); /* box1 is now the union of the two */
4217  newface.mbr = box1;
4218  if ( modFace )
4219  {
4220  newface.face_id = floodface;
4221  i = lwt_be_updateFacesById( topo, &newface, 1 );
4222  _lwt_release_faces(faces, 2);
4223  if ( i == -1 )
4224  {
4225  _lwt_release_edges(edge, 1);
4226  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4227  return -1;
4228  }
4229  if ( i != 1 )
4230  {
4231  _lwt_release_edges(edge, 1);
4232  lwerror("Unexpected error: %d faces updated when expecting 1", i);
4233  return -1;
4234  }
4235  }
4236  else
4237  {
4238  /* New face replaces the old two faces */
4239  newface.face_id = -1;
4240  i = lwt_be_insertFaces( topo, &newface, 1 );
4241  _lwt_release_faces(faces, 2);
4242  if ( i == -1 )
4243  {
4244  _lwt_release_edges(edge, 1);
4245  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4246  return -1;
4247  }
4248  if ( i != 1 )
4249  {
4250  _lwt_release_edges(edge, 1);
4251  lwerror("Unexpected error: %d faces inserted when expecting 1", i);
4252  return -1;
4253  }
4254  floodface = newface.face_id;
4255  }
4256  }
4257 
4258  /* Update face references for edges and nodes still referencing
4259  * the removed face(s) */
4260 
4261  if ( edge->face_left != floodface )
4262  {
4263  if ( -1 == _lwt_UpdateEdgeFaceRef(topo, edge->face_left, floodface) )
4264  {
4265  _lwt_release_edges(edge, 1);
4266  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4267  return -1;
4268  }
4269  if ( -1 == _lwt_UpdateNodeFaceRef(topo, edge->face_left, floodface) )
4270  {
4271  _lwt_release_edges(edge, 1);
4272  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4273  return -1;
4274  }
4275  }
4276 
4277  if ( edge->face_right != floodface )
4278  {
4279  if ( -1 == _lwt_UpdateEdgeFaceRef(topo, edge->face_right, floodface) )
4280  {
4281  _lwt_release_edges(edge, 1);
4282  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4283  return -1;
4284  }
4285  if ( -1 == _lwt_UpdateNodeFaceRef(topo, edge->face_right, floodface) )
4286  {
4287  _lwt_release_edges(edge, 1);
4288  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4289  return -1;
4290  }
4291  }
4292 
4293  /* Update topogeoms on heal */
4294  if ( ! lwt_be_updateTopoGeomFaceHeal(topo,
4295  edge->face_right, edge->face_left,
4296  floodface) )
4297  {
4298  _lwt_release_edges(edge, 1);
4300  return -1;
4301  }
4302  } /* two faces healed */
4303 
4304  /* Delete the edge */
4305  i = lwt_be_deleteEdges(topo, edge, LWT_COL_EDGE_EDGE_ID);
4306  if ( i == -1 ) {
4307  _lwt_release_edges(edge, 1);
4308  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4309  return -1;
4310  }
4311 
4312  /* If any of the edge nodes remained isolated, set
4313  * containing_face = floodface
4314  */
4315  if ( ! fnode_edges )
4316  {
4317  upd_node[nnode].node_id = edge->start_node;
4318  upd_node[nnode].containing_face = floodface;
4319  ++nnode;
4320  }
4321  if ( edge->end_node != edge->start_node && ! lnode_edges )
4322  {
4323  upd_node[nnode].node_id = edge->end_node;
4324  upd_node[nnode].containing_face = floodface;
4325  ++nnode;
4326  }
4327  if ( nnode )
4328  {
4329  i = lwt_be_updateNodesById(topo, upd_node, nnode,
4331  if ( i == -1 ) {
4332  _lwt_release_edges(edge, 1);
4333  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4334  return -1;
4335  }
4336  }
4337 
4338  if ( edge->face_left != edge->face_right )
4339  /* or there'd be no face to remove */
4340  {
4341  LWT_ELEMID ids[2];
4342  int nids = 0;
4343  if ( edge->face_right != floodface )
4344  ids[nids++] = edge->face_right;
4345  if ( edge->face_left != floodface )
4346  ids[nids++] = edge->face_left;
4347  i = lwt_be_deleteFacesById(topo, ids, nids);
4348  if ( i == -1 ) {
4349  _lwt_release_edges(edge, 1);
4350  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4351  return -1;
4352  }
4353  }
4354 
4355  _lwt_release_edges(edge, 1);
4356  return modFace ? floodface : newface.face_id;
4357 }
4358 
4359 LWT_ELEMID
4361 {
4362  return _lwt_RemEdge( topo, edge_id, 1 );
4363 }
4364 
4365 LWT_ELEMID
4367 {
4368  return _lwt_RemEdge( topo, edge_id, 0 );
4369 }
4370 
4371 static LWT_ELEMID
4373  int modEdge )
4374 {
4375  LWT_ELEMID ids[2];
4376  LWT_ELEMID commonnode = -1;
4377  int caseno = 0;
4378  LWT_ISO_EDGE *node_edges;
4379  int num_node_edges;
4380  LWT_ISO_EDGE *edges;
4381  LWT_ISO_EDGE *e1 = NULL;
4382  LWT_ISO_EDGE *e2 = NULL;
4383  LWT_ISO_EDGE newedge, updedge, seledge;
4384  int nedges, i;
4385  int e1freenode;
4386  int e2sign, e2freenode;
4387  POINTARRAY *pa;
4388  char buf[256];
4389  char *ptr;
4390  size_t bufleft = 256;
4391 
4392  ptr = buf;
4393 
4394  /* NOT IN THE SPECS: see if the same edge is given twice.. */
4395  if ( eid1 == eid2 )
4396  {
4397  lwerror("Cannot heal edge %" LWTFMT_ELEMID
4398  " with itself, try with another", eid1);
4399  return -1;
4400  }
4401  ids[0] = eid1;
4402  ids[1] = eid2;
4403  nedges = 2;
4404  edges = lwt_be_getEdgeById(topo, ids, &nedges, LWT_COL_EDGE_ALL);
4405  if ((nedges == -1) || (edges == NULL))
4406  {
4407  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4408  return -1;
4409  }
4410  for ( i=0; i<nedges; ++i )
4411  {
4412  if ( edges[i].edge_id == eid1 ) {
4413  if ( e1 ) {
4414  _lwt_release_edges(edges, nedges);
4415  lwerror("Corrupted topology: multiple edges have id %"
4416  LWTFMT_ELEMID, eid1);
4417  return -1;
4418  }
4419  e1 = &(edges[i]);
4420  }
4421  else if ( edges[i].edge_id == eid2 ) {
4422  if ( e2 ) {
4423  _lwt_release_edges(edges, nedges);
4424  lwerror("Corrupted topology: multiple edges have id %"
4425  LWTFMT_ELEMID, eid2);
4426  return -1;
4427  }
4428  e2 = &(edges[i]);
4429  }
4430  }
4431  if ( ! e1 )
4432  {
4433  _lwt_release_edges(edges, nedges);
4434  lwerror(
4435  "SQL/MM Spatial exception - non-existent edge %" LWTFMT_ELEMID,
4436  eid1);
4437  return -1;
4438  }
4439  if ( ! e2 )
4440  {
4441  _lwt_release_edges(edges, nedges);
4442  lwerror(
4443  "SQL/MM Spatial exception - non-existent edge %" LWTFMT_ELEMID,
4444  eid2);
4445  return -1;
4446  }
4447 
4448  /* NOT IN THE SPECS: See if any of the two edges are closed. */
4449  if ( e1->start_node == e1->end_node )
4450  {
4451  _lwt_release_edges(edges, nedges);
4452  lwerror("Edge %" LWTFMT_ELEMID " is closed, cannot heal to edge %"
4453  LWTFMT_ELEMID, eid1, eid2);
4454  return -1;
4455  }
4456  if ( e2->start_node == e2->end_node )
4457  {
4458  _lwt_release_edges(edges, nedges);
4459  lwerror("Edge %" LWTFMT_ELEMID " is closed, cannot heal to edge %"
4460  LWTFMT_ELEMID, eid2, eid1);
4461  return -1;
4462  }
4463 
4464  /* Find common node */
4465 
4466  if ( e1->end_node == e2->start_node )
4467  {
4468  commonnode = e1->end_node;
4469  caseno = 1;
4470  }
4471  else if ( e1->end_node == e2->end_node )
4472  {
4473  commonnode = e1->end_node;
4474  caseno = 2;
4475  }
4476  /* Check if any other edge is connected to the common node, if found */
4477  if ( commonnode != -1 )
4478  {
4479  num_node_edges = 1;
4480  node_edges = lwt_be_getEdgeByNode( topo, &commonnode,
4481  &num_node_edges, LWT_COL_EDGE_EDGE_ID );
4482  if ( num_node_edges == -1 ) {
4483  _lwt_release_edges(edges, nedges);
4484  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4485  return -1;
4486  }
4487  for (i=0; i<num_node_edges; ++i)
4488  {
4489  int r;
4490  if ( node_edges[i].edge_id == eid1 ) continue;
4491  if ( node_edges[i].edge_id == eid2 ) continue;
4492  commonnode = -1;
4493  /* append to string, for error message */
4494  if ( bufleft > 0 ) {
4495  r = snprintf(ptr, bufleft, "%s%" LWTFMT_ELEMID,
4496  ( ptr==buf ? "" : "," ), node_edges[i].edge_id);
4497  if ( r >= (int) bufleft )
4498  {
4499  bufleft = 0;
4500  buf[252] = '.';
4501  buf[253] = '.';
4502  buf[254] = '.';
4503  buf[255] = '\0';
4504  }
4505  else
4506  {
4507  bufleft -= r;
4508  ptr += r;
4509  }
4510  }
4511  }
4512  lwfree(node_edges);
4513  }
4514 
4515  if ( commonnode == -1 )
4516  {
4517  if ( e1->start_node == e2->start_node )
4518  {
4519  commonnode = e1->start_node;
4520  caseno = 3;
4521  }
4522  else if ( e1->start_node == e2->end_node )
4523  {
4524  commonnode = e1->start_node;
4525  caseno = 4;
4526  }
4527  /* Check if any other edge is connected to the common node, if found */
4528  if ( commonnode != -1 )
4529  {
4530  num_node_edges = 1;
4531  node_edges = lwt_be_getEdgeByNode( topo, &commonnode,
4532  &num_node_edges, LWT_COL_EDGE_EDGE_ID );
4533  if ( num_node_edges == -1 ) {
4534  _lwt_release_edges(edges, nedges);
4535  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4536  return -1;
4537  }
4538  for (i=0; i<num_node_edges; ++i)
4539  {
4540  int r;
4541  if ( node_edges[i].edge_id == eid1 ) continue;
4542  if ( node_edges[i].edge_id == eid2 ) continue;
4543  commonnode = -1;
4544  /* append to string, for error message */
4545  if ( bufleft > 0 ) {
4546  r = snprintf(ptr, bufleft, "%s%" LWTFMT_ELEMID,
4547  ( ptr==buf ? "" : "," ), node_edges[i].edge_id);
4548  if ( r >= (int) bufleft )
4549  {
4550  bufleft = 0;
4551  buf[252] = '.';
4552  buf[253] = '.';
4553  buf[254] = '.';
4554  buf[255] = '\0';
4555  }
4556  else
4557  {
4558  bufleft -= r;
4559  ptr += r;
4560  }
4561  }
4562  }
4563  if ( num_node_edges ) lwfree(node_edges);
4564  }
4565  }
4566 
4567  if ( commonnode == -1 )
4568  {
4569  _lwt_release_edges(edges, nedges);
4570  if ( ptr != buf )
4571  {
4572  lwerror("SQL/MM Spatial exception - other edges connected (%s)",
4573  buf);
4574  }
4575  else
4576  {
4577  lwerror("SQL/MM Spatial exception - non-connected edges");
4578  }
4579  return -1;
4580  }
4581 
4582  if ( ! lwt_be_checkTopoGeomRemNode(topo, commonnode,
4583  eid1, eid2 ) )
4584  {
4585  _lwt_release_edges(edges, nedges);
4587  return -1;
4588  }
4589 
4590  /* Construct the geometry of the new edge */
4591  switch (caseno)
4592  {
4593  case 1: /* e1.end = e2.start */
4594  pa = ptarray_clone_deep(e1->geom->points);
4595  //pa = ptarray_merge(pa, e2->geom->points);
4596  ptarray_append_ptarray(pa, e2->geom->points, 0);
4597  newedge.start_node = e1->start_node;
4598  newedge.end_node = e2->end_node;
4599  newedge.next_left = e2->next_left;
4600  newedge.next_right = e1->next_right;
4601  e1freenode = 1;
4602  e2freenode = -1;
4603  e2sign = 1;
4604  break;
4605  case 2: /* e1.end = e2.end */
4606  {
4607  POINTARRAY *pa2;
4608  pa2 = ptarray_clone_deep(e2->geom->points);
4610  pa = ptarray_clone_deep(e1->geom->points);
4611  //pa = ptarray_merge(e1->geom->points, pa);
4612  ptarray_append_ptarray(pa, pa2, 0);
4613  ptarray_free(pa2);
4614  newedge.start_node = e1->start_node;
4615  newedge.end_node = e2->start_node;
4616  newedge.next_left = e2->next_right;
4617  newedge.next_right = e1->next_right;
4618  e1freenode = 1;
4619  e2freenode = 1;
4620  e2sign = -1;
4621  break;
4622  }
4623  case 3: /* e1.start = e2.start */
4624  pa = ptarray_clone_deep(e2->geom->points);
4626  //pa = ptarray_merge(pa, e1->geom->points);
4627  ptarray_append_ptarray(pa, e1->geom->points, 0);
4628  newedge.end_node = e1->end_node;
4629  newedge.start_node = e2->end_node;
4630  newedge.next_left = e1->next_left;
4631  newedge.next_right = e2->next_left;
4632  e1freenode = -1;
4633  e2freenode = -1;
4634  e2sign = -1;
4635  break;
4636  case 4: /* e1.start = e2.end */
4637  pa = ptarray_clone_deep(e2->geom->points);
4638  //pa = ptarray_merge(pa, e1->geom->points);
4639  ptarray_append_ptarray(pa, e1->geom->points, 0);
4640  newedge.end_node = e1->end_node;
4641  newedge.start_node = e2->start_node;
4642  newedge.next_left = e1->next_left;
4643  newedge.next_right = e2->next_right;
4644  e1freenode = -1;
4645  e2freenode = 1;
4646  e2sign = 1;
4647  break;
4648  default:
4649  pa = NULL;
4650  e1freenode = 0;
4651  e2freenode = 0;
4652  e2sign = 0;
4653  _lwt_release_edges(edges, nedges);
4654  lwerror("Coding error: caseno=%d should never happen", caseno);
4655  break;
4656  }
4657  newedge.geom = lwline_construct(topo->srid, NULL, pa);
4658 
4659  if ( modEdge )
4660  {
4661  /* Update data of the first edge */
4662  newedge.edge_id = eid1;
4663  i = lwt_be_updateEdgesById(topo, &newedge, 1,
4669  if ( i == -1 )
4670  {
4671  lwline_free(newedge.geom);
4672  _lwt_release_edges(edges, nedges);
4673  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4674  return -1;
4675  }
4676  else if ( i != 1 )
4677  {
4678  lwline_free(newedge.geom);
4679  if ( edges ) _lwt_release_edges(edges, nedges);
4680  lwerror("Unexpected error: %d edges updated when expecting 1", i);
4681  return -1;
4682  }
4683  }
4684  else
4685  {
4686  /* Add new edge */
4687  newedge.edge_id = -1;
4688  newedge.face_left = e1->face_left;
4689  newedge.face_right = e1->face_right;
4690  i = lwt_be_insertEdges(topo, &newedge, 1);
4691  if ( i == -1 ) {
4692  lwline_free(newedge.geom);
4693  _lwt_release_edges(edges, nedges);
4694  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4695  return -1;
4696  } else if ( i == 0 ) {
4697  lwline_free(newedge.geom);
4698  _lwt_release_edges(edges, nedges);
4699  lwerror("Insertion of split edge failed (no reason)");
4700  return -1;
4701  }
4702  }
4703  lwline_free(newedge.geom);
4704 
4705  /*
4706  -- Update next_left_edge/next_right_edge for
4707  -- any edge having them still pointing at the edge being removed
4708  -- (eid2 only when modEdge, or both otherwise)
4709  --
4710  -- NOTE:
4711  -- e#freenode is 1 when edge# end node was the common node
4712  -- and -1 otherwise. This gives the sign of possibly found references
4713  -- to its "free" (non connected to other edge) endnode.
4714  -- e2sign is -1 if edge1 direction is opposite to edge2 direction,
4715  -- or 1 otherwise.
4716  --
4717  */
4718 
4719  /* update edges connected to e2's boundary from their end node */
4720  seledge.next_left = e2freenode * eid2;
4721  updedge.next_left = e2freenode * newedge.edge_id * e2sign;
4722  i = lwt_be_updateEdges(topo, &seledge, LWT_COL_EDGE_NEXT_LEFT,
4723  &updedge, LWT_COL_EDGE_NEXT_LEFT,
4724  NULL, 0);
4725  if ( i == -1 )
4726  {
4727  _lwt_release_edges(edges, nedges);
4728  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4729  return -1;
4730  }
4731 
4732  /* update edges connected to e2's boundary from their start node */
4733  seledge.next_right = e2freenode * eid2;
4734  updedge.next_right = e2freenode * newedge.edge_id * e2sign;
4735  i = lwt_be_updateEdges(topo, &seledge, LWT_COL_EDGE_NEXT_RIGHT,
4736  &updedge, LWT_COL_EDGE_NEXT_RIGHT,
4737  NULL, 0);
4738  if ( i == -1 )
4739  {
4740  _lwt_release_edges(edges, nedges);
4741  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4742  return -1;
4743  }
4744 
4745  if ( ! modEdge )
4746  {
4747  /* update edges connected to e1's boundary from their end node */
4748  seledge.next_left = e1freenode * eid1;
4749  updedge.next_left = e1freenode * newedge.edge_id;
4750  i = lwt_be_updateEdges(topo, &seledge, LWT_COL_EDGE_NEXT_LEFT,
4751  &updedge, LWT_COL_EDGE_NEXT_LEFT,
4752  NULL, 0);
4753  if ( i == -1 )
4754  {
4755  _lwt_release_edges(edges, nedges);
4756  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4757  return -1;
4758  }
4759 
4760  /* update edges connected to e1's boundary from their start node */
4761  seledge.next_right = e1freenode * eid1;
4762  updedge.next_right = e1freenode * newedge.edge_id;
4763  i = lwt_be_updateEdges(topo, &seledge, LWT_COL_EDGE_NEXT_RIGHT,
4764  &updedge, LWT_COL_EDGE_NEXT_RIGHT,
4765  NULL, 0);
4766  if ( i == -1 )
4767  {
4768  _lwt_release_edges(edges, nedges);
4769  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4770  return -1;
4771  }
4772  }
4773 
4774  /* delete the edges (only second on modEdge or both) */
4776  if ( i == -1 )
4777  {
4778  _lwt_release_edges(edges, nedges);
4779  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4780  return -1;
4781  }
4782  if ( ! modEdge ) {
4784  if ( i == -1 )
4785  {
4786  _lwt_release_edges(edges, nedges);
4787  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4788  return -1;
4789  }
4790  }
4791 
4792  _lwt_release_edges(edges, nedges);
4793 
4794  /* delete the common node */
4795  i = lwt_be_deleteNodesById( topo, &commonnode, 1 );
4796  if ( i == -1 )
4797  {
4798  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4799  return -1;
4800  }
4801 
4802  /*
4803  --
4804  -- NOT IN THE SPECS:
4805  -- Drop composition rows involving second
4806  -- edge, as the first edge took its space,
4807  -- and all affected TopoGeom have been previously checked
4808  -- for being composed by both edges.
4809  */
4810  if ( ! lwt_be_updateTopoGeomEdgeHeal(topo,
4811  eid1, eid2, newedge.edge_id) )
4812  {
4814  return -1;
4815  }
4816 
4817  return modEdge ? commonnode : newedge.edge_id;
4818 }
4819 
4820 LWT_ELEMID
4822 {
4823  return _lwt_HealEdges( topo, e1, e2, 1 );
4824 }
4825 
4826 LWT_ELEMID
4828 {
4829  return _lwt_HealEdges( topo, e1, e2, 0 );
4830 }
4831 
4832 LWT_ELEMID
4833 lwt_GetNodeByPoint(LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
4834 {
4835  LWT_ISO_NODE *elem;
4836  int num;
4837  int flds = LWT_COL_NODE_NODE_ID|LWT_COL_NODE_GEOM; /* geom not needed */
4838  LWT_ELEMID id = 0;
4839  POINT2D qp; /* query point */
4840 
4841  if ( ! getPoint2d_p(pt->point, 0, &qp) )
4842  {
4843  lwerror("Empty query point");
4844  return -1;
4845  }
4846  elem = lwt_be_getNodeWithinDistance2D(topo, pt, tol, &num, flds, 0);
4847  if ( num == -1 )
4848  {
4849  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4850  return -1;
4851  }
4852  else if ( num )
4853  {
4854  if ( num > 1 )
4855  {
4856  _lwt_release_nodes(elem, num);
4857  lwerror("Two or more nodes found");
4858  return -1;
4859  }
4860  id = elem[0].node_id;
4861  _lwt_release_nodes(elem, num);
4862  }
4863 
4864  return id;
4865 }
4866 
4867 LWT_ELEMID
4868 lwt_GetEdgeByPoint(LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
4869 {
4870  LWT_ISO_EDGE *elem;
4871  int num, i;
4872  int flds = LWT_COL_EDGE_EDGE_ID|LWT_COL_EDGE_GEOM; /* GEOM is not needed */
4873  LWT_ELEMID id = 0;
4874  LWGEOM *qp = lwpoint_as_lwgeom(pt); /* query point */
4875 
4876  if ( lwgeom_is_empty(qp) )
4877  {
4878  lwerror("Empty query point");
4879  return -1;
4880  }
4881  elem = lwt_be_getEdgeWithinDistance2D(topo, pt, tol, &num, flds, 0);
4882  if ( num == -1 )
4883  {
4884  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4885  return -1;
4886  }
4887  for (i=0; i<num;++i)
4888  {
4889  LWT_ISO_EDGE *e = &(elem[i]);
4890 #if 0
4891  LWGEOM* geom;
4892  double dist;
4893 
4894  if ( ! e->geom )
4895  {
4896  _lwt_release_edges(elem, num);
4897  lwnotice("Corrupted topology: edge %" LWTFMT_ELEMID
4898  " has null geometry", e->edge_id);
4899  continue;
4900  }
4901 
4902  /* Should we check for intersection not being on an endpoint
4903  * as documented ? */
4904  geom = lwline_as_lwgeom(e->geom);
4905  dist = lwgeom_mindistance2d_tolerance(geom, qp, tol);
4906  if ( dist > tol ) continue;
4907 #endif
4908 
4909  if ( id )
4910  {
4911  _lwt_release_edges(elem, num);
4912  lwerror("Two or more edges found");
4913  return -1;
4914  }
4915  else id = e->edge_id;
4916  }
4917 
4918  if ( num ) _lwt_release_edges(elem, num);
4919 
4920  return id;
4921 }
4922 
4923 LWT_ELEMID
4924 lwt_GetFaceByPoint(LWT_TOPOLOGY *topo, LWPOINT *pt, double tol)
4925 {
4926  LWT_ELEMID id = 0;
4927  LWT_ISO_EDGE *elem;
4928  int num, i;
4929  int flds = LWT_COL_EDGE_EDGE_ID |
4933  LWGEOM *qp = lwpoint_as_lwgeom(pt);
4934 
4935  id = lwt_be_getFaceContainingPoint(topo, pt);
4936  if ( id == -2 ) {
4937  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4938  return -1;
4939  }
4940 
4941  if ( id > 0 )
4942  {
4943  return id;
4944  }
4945  id = 0; /* or it'll be -1 for not found */
4946 
4947  LWDEBUG(1, "No face properly contains query point,"
4948  " looking for edges");
4949 
4950  /* Not in a face, may be in universe or on edge, let's check
4951  * for distance */
4952  /* NOTE: we never pass a tolerance of 0 to avoid ever using
4953  * ST_Within, which doesn't include endpoints matches */
4954  elem = lwt_be_getEdgeWithinDistance2D(topo, pt, tol?tol:1e-5, &num, flds, 0);
4955  if ( num == -1 )
4956  {
4957  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
4958  return -1;
4959  }
4960  for (i=0; i<num; ++i)
4961  {
4962  LWT_ISO_EDGE *e = &(elem[i]);
4963  LWT_ELEMID eface = 0;
4964  LWGEOM* geom;
4965  double dist;
4966 
4967  if ( ! e->geom )
4968  {
4969  _lwt_release_edges(elem, num);
4970  lwnotice("Corrupted topology: edge %" LWTFMT_ELEMID
4971  " has null geometry", e->edge_id);
4972  continue;
4973  }
4974 
4975  /* don't consider dangling edges */
4976  if ( e->face_left == e->face_right )
4977  {
4978  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID
4979  " is dangling, won't consider it", e->edge_id);
4980  continue;
4981  }
4982 
4983  geom = lwline_as_lwgeom(e->geom);
4984  dist = lwgeom_mindistance2d_tolerance(geom, qp, tol);
4985 
4986  LWDEBUGF(1, "Distance from edge %" LWTFMT_ELEMID
4987  " is %g (tol=%g)", e->edge_id, dist, tol);
4988 
4989  /* we won't consider edges too far */
4990  if ( dist > tol ) continue;
4991  if ( e->face_left == 0 ) {
4992  eface = e->face_right;
4993  }
4994  else if ( e->face_right == 0 ) {
4995  eface = e->face_left;
4996  }
4997  else {
4998  _lwt_release_edges(elem, num);
4999  lwerror("Two or more faces found");
5000  return -1;
5001  }
5002 
5003  if ( id && id != eface )
5004  {
5005  _lwt_release_edges(elem, num);
5006  lwerror("Two or more faces found"
5007 #if 0 /* debugging */
5008  " (%" LWTFMT_ELEMID
5009  " and %" LWTFMT_ELEMID ")", id, eface
5010 #endif
5011  );
5012  return -1;
5013  }
5014  else id = eface;
5015  }
5016  if ( num ) _lwt_release_edges(elem, num);
5017 
5018  return id;
5019 }
5020 
5021 /* Return the smallest delta that can perturbate
5022  * the given value */
5023 static inline double
5025 {
5026  double ret = 3.6 * pow(10, - ( 15 - log10(d?d:1.0) ) );
5027  return ret;
5028 }
5029 
5030 /* Return the smallest delta that can perturbate
5031  * the given point
5032 static inline double
5033 _lwt_minTolerancePoint2d( const POINT2D* p )
5034 {
5035  double max = FP_ABS(p->x);
5036  if ( max < FP_ABS(p->y) ) max = FP_ABS(p->y);
5037  return _lwt_minToleranceDouble(max);
5038 }
5039 */
5040 
5041 /* Return the smallest delta that can perturbate
5042  * the maximum absolute value of a geometry ordinate
5043  */
5044 static double
5046 {
5047  const GBOX* gbox;
5048  double max;
5049  double ret;
5050 
5051  gbox = lwgeom_get_bbox(g);
5052  if ( ! gbox ) return 0; /* empty */
5053  max = FP_ABS(gbox->xmin);
5054  if ( max < FP_ABS(gbox->xmax) ) max = FP_ABS(gbox->xmax);
5055  if ( max < FP_ABS(gbox->ymin) ) max = FP_ABS(gbox->ymin);
5056  if ( max < FP_ABS(gbox->ymax) ) max = FP_ABS(gbox->ymax);
5057 
5058  ret = _lwt_minToleranceDouble(max);
5059 
5060  return ret;
5061 }
5062 
5063 #define _LWT_MINTOLERANCE( topo, geom ) ( \
5064  topo->precision ? topo->precision : _lwt_minTolerance(geom) )
5065 
5066 typedef struct scored_pointer_t {
5067  void *ptr;
5068  double score;
5069 } scored_pointer;
5070 
5071 static int
5072 compare_scored_pointer(const void *si1, const void *si2)
5073 {
5074