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