PostGIS  2.2.7dev-r@@SVN_REVISION@@
static LWT_ELEMID _lwt_AddEdge ( LWT_TOPOLOGY topo,
LWT_ELEMID  start_node,
LWT_ELEMID  end_node,
LWLINE geom,
int  skipChecks,
int  modFace 
)
static

Definition at line 2333 of file lwgeom_topo.c.

References _lwt_AddFaceSplit(), _lwt_CheckEdgeCrossing(), _lwt_FindAdjacentEdges(), _lwt_release_nodes(), azimuth_pt_pt(), LWT_TOPOLOGY_T::be_iface, edgeend_t::ccwFace, LWT_ISO_NODE::containing_face, edgeend_t::cwFace, LWT_ISO_EDGE::edge_id, LWT_ISO_EDGE::end_node, LWT_ISO_EDGE::face_left, LWT_ISO_EDGE::face_right, LWT_ISO_NODE::geom, LWT_ISO_EDGE::geom, getPoint2d_p(), LWDEBUG, LWDEBUGF, lwerror(), lwgeom_as_lwline(), lwgeom_free(), lwgeom_is_simple(), lwgeom_remove_repeated_points(), lwline_as_lwgeom(), lwt_be_deleteFacesById(), lwt_be_getNextEdgeId(), lwt_be_getNodeById(), lwt_be_insertEdges(), lwt_be_lastErrorMessage(), lwt_be_updateEdges(), lwt_be_updateNodes(), lwt_be_updateTopoGeomFaceSplit(), LWT_COL_EDGE_EDGE_ID, LWT_COL_EDGE_NEXT_LEFT, LWT_COL_EDGE_NEXT_RIGHT, LWT_COL_NODE_ALL, LWT_COL_NODE_CONTAINING_FACE, LWT_COL_NODE_NODE_ID, LWTFMT_ELEMID, edgeend_t::myaz, LWT_ISO_EDGE::next_left, LWT_ISO_EDGE::next_right, edgeend_t::nextCCW, edgeend_t::nextCW, LWT_ISO_NODE::node_id, POINTARRAY::npoints, p2d_same(), LWPOINT::point, LWLINE::points, LWT_ISO_EDGE::start_node, edgeend_t::was_isolated, POINT2D::x, and POINT2D::y.

Referenced by lwt_AddEdgeModFace(), and lwt_AddEdgeNewFaces().

2336 {
2337  LWT_ISO_EDGE newedge;
2338  LWGEOM *cleangeom;
2339  edgeend span; /* start point analisys */
2340  edgeend epan; /* end point analisys */
2341  POINT2D p1, pn, p2;
2342  POINTARRAY *pa;
2343  LWT_ELEMID node_ids[2];
2344  const LWPOINT *start_node_geom = NULL;
2345  const LWPOINT *end_node_geom = NULL;
2346  int num_nodes;
2347  LWT_ISO_NODE *endpoints;
2348  int i;
2349  int prev_left;
2350  int prev_right;
2351  LWT_ISO_EDGE seledge;
2352  LWT_ISO_EDGE updedge;
2353 
2354  if ( ! skipChecks )
2355  {
2356  /* curve must be simple */
2357  if ( ! lwgeom_is_simple(lwline_as_lwgeom(geom)) )
2358  {
2359  lwerror("SQL/MM Spatial exception - curve not simple");
2360  return -1;
2361  }
2362  }
2363 
2364  newedge.start_node = start_node;
2365  newedge.end_node = end_node;
2366  newedge.geom = geom;
2367  newedge.face_left = -1;
2368  newedge.face_right = -1;
2369  cleangeom = lwgeom_remove_repeated_points( lwline_as_lwgeom(geom), 0 );
2370 
2371  pa = lwgeom_as_lwline(cleangeom)->points;
2372  if ( pa->npoints < 2 ) {
2373  lwgeom_free(cleangeom);
2374  lwerror("Invalid edge (no two distinct vertices exist)");
2375  return -1;
2376  }
2377 
2378  /* Initialize endpoint info (some of that ) */
2379  span.cwFace = span.ccwFace =
2380  epan.cwFace = epan.ccwFace = -1;
2381 
2382  /* Compute azimut of first edge end on start node */
2383  getPoint2d_p(pa, 0, &p1);
2384  getPoint2d_p(pa, 1, &pn);
2385  if ( p2d_same(&p1, &pn) ) {
2386  lwgeom_free(cleangeom);
2387  /* Can still happen, for 2-point lines */
2388  lwerror("Invalid edge (no two distinct vertices exist)");
2389  return -1;
2390  }
2391  if ( ! azimuth_pt_pt(&p1, &pn, &span.myaz) ) {
2392  lwgeom_free(cleangeom);
2393  lwerror("error computing azimuth of first edgeend [%g,%g-%g,%g]",
2394  p1.x, p1.y, pn.x, pn.y);
2395  return -1;
2396  }
2397  LWDEBUGF(1, "edge's start node is %g,%g", p1.x, p1.y);
2398 
2399  /* Compute azimuth of last edge end on end node */
2400  getPoint2d_p(pa, pa->npoints-1, &p2);
2401  getPoint2d_p(pa, pa->npoints-2, &pn);
2402  lwgeom_free(cleangeom);
2403  if ( ! azimuth_pt_pt(&p2, &pn, &epan.myaz) ) {
2404  lwerror("error computing azimuth of last edgeend [%g,%g-%g,%g]",
2405  p2.x, p2.y, pn.x, pn.y);
2406  return -1;
2407  }
2408  LWDEBUGF(1, "edge's end node is %g,%g", p2.x, p2.y);
2409 
2410  /*
2411  * Check endpoints existance, match with Curve geometry
2412  * and get face information (if any)
2413  */
2414 
2415  if ( start_node != end_node ) {
2416  num_nodes = 2;
2417  node_ids[0] = start_node;
2418  node_ids[1] = end_node;
2419  } else {
2420  num_nodes = 1;
2421  node_ids[0] = start_node;
2422  }
2423 
2424  endpoints = lwt_be_getNodeById( topo, node_ids, &num_nodes, LWT_COL_NODE_ALL );
2425  if ( num_nodes < 0 ) {
2426  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2427  return -1;
2428  }
2429  for ( i=0; i<num_nodes; ++i )
2430  {
2431  LWT_ISO_NODE* node = &(endpoints[i]);
2432  if ( node->containing_face != -1 )
2433  {
2434  if ( newedge.face_left == -1 )
2435  {
2436  newedge.face_left = newedge.face_right = node->containing_face;
2437  }
2438  else if ( newedge.face_left != node->containing_face )
2439  {
2440  _lwt_release_nodes(endpoints, num_nodes);
2441  lwerror("SQL/MM Spatial exception - geometry crosses an edge"
2442  " (endnodes in faces %" LWTFMT_ELEMID " and %" LWTFMT_ELEMID ")",
2443  newedge.face_left, node->containing_face);
2444  }
2445  }
2446 
2447  LWDEBUGF(1, "Node %d, with geom %p (looking for %d and %d)",
2448  node->node_id, node->geom, start_node, end_node);
2449  if ( node->node_id == start_node ) {
2450  start_node_geom = node->geom;
2451  }
2452  if ( node->node_id == end_node ) {
2453  end_node_geom = node->geom;
2454  }
2455  }
2456 
2457  if ( ! skipChecks )
2458  {
2459  if ( ! start_node_geom )
2460  {
2461  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2462  lwerror("SQL/MM Spatial exception - non-existent node");
2463  return -1;
2464  }
2465  else
2466  {
2467  pa = start_node_geom->point;
2468  getPoint2d_p(pa, 0, &pn);
2469  if ( ! p2d_same(&pn, &p1) )
2470  {
2471  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2472  lwerror("SQL/MM Spatial exception"
2473  " - start node not geometry start point."
2474  //" - start node not geometry start point (%g,%g != %g,%g).", pn.x, pn.y, p1.x, p1.y
2475  );
2476  return -1;
2477  }
2478  }
2479 
2480  if ( ! end_node_geom )
2481  {
2482  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2483  lwerror("SQL/MM Spatial exception - non-existent node");
2484  return -1;
2485  }
2486  else
2487  {
2488  pa = end_node_geom->point;
2489  getPoint2d_p(pa, 0, &pn);
2490  if ( ! p2d_same(&pn, &p2) )
2491  {
2492  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2493  lwerror("SQL/MM Spatial exception"
2494  " - end node not geometry end point."
2495  //" - end node not geometry end point (%g,%g != %g,%g).", pn.x, pn.y, p2.x, p2.y
2496  );
2497  return -1;
2498  }
2499  }
2500 
2501  if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
2502 
2503  if ( _lwt_CheckEdgeCrossing( topo, start_node, end_node, geom, 0 ) )
2504  return -1;
2505 
2506  } /* ! skipChecks */
2507 
2508  /*
2509  * All checks passed, time to prepare the new edge
2510  */
2511 
2512  newedge.edge_id = lwt_be_getNextEdgeId( topo );
2513  if ( newedge.edge_id == -1 ) {
2514  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2515  return -1;
2516  }
2517 
2518  /* Find adjacent edges to each endpoint */
2519  int isclosed = start_node == end_node;
2520  int found;
2521  found = _lwt_FindAdjacentEdges( topo, start_node, &span,
2522  isclosed ? &epan : NULL, -1 );
2523  if ( found ) {
2524  span.was_isolated = 0;
2525  newedge.next_right = span.nextCW ? span.nextCW : -newedge.edge_id;
2526  prev_left = span.nextCCW ? -span.nextCCW : newedge.edge_id;
2527  LWDEBUGF(1, "New edge %d is connected on start node, "
2528  "next_right is %d, prev_left is %d",
2529  newedge.edge_id, newedge.next_right, prev_left);
2530  if ( newedge.face_right == -1 ) {
2531  newedge.face_right = span.cwFace;
2532  }
2533  if ( newedge.face_left == -1 ) {
2534  newedge.face_left = span.ccwFace;
2535  }
2536  } else {
2537  span.was_isolated = 1;
2538  newedge.next_right = isclosed ? -newedge.edge_id : newedge.edge_id;
2539  prev_left = isclosed ? newedge.edge_id : -newedge.edge_id;
2540  LWDEBUGF(1, "New edge %d is isolated on start node, "
2541  "next_right is %d, prev_left is %d",
2542  newedge.edge_id, newedge.next_right, prev_left);
2543  }
2544 
2545  found = _lwt_FindAdjacentEdges( topo, end_node, &epan,
2546  isclosed ? &span : NULL, -1 );
2547  if ( found ) {
2548  epan.was_isolated = 0;
2549  newedge.next_left = epan.nextCW ? epan.nextCW : newedge.edge_id;
2550  prev_right = epan.nextCCW ? -epan.nextCCW : -newedge.edge_id;
2551  LWDEBUGF(1, "New edge %d is connected on end node, "
2552  "next_left is %d, prev_right is %d",
2553  newedge.edge_id, newedge.next_left, prev_right);
2554  if ( newedge.face_right == -1 ) {
2555  newedge.face_right = span.ccwFace;
2556  }
2557  if ( newedge.face_left == -1 ) {
2558  newedge.face_left = span.cwFace;
2559  }
2560  } else {
2561  epan.was_isolated = 1;
2562  newedge.next_left = isclosed ? newedge.edge_id : -newedge.edge_id;
2563  prev_right = isclosed ? -newedge.edge_id : newedge.edge_id;
2564  LWDEBUGF(1, "New edge %d is isolated on end node, "
2565  "next_left is %d, prev_right is %d",
2566  newedge.edge_id, newedge.next_left, prev_right);
2567  }
2568 
2569  /*
2570  * If we don't have faces setup by now we must have encountered
2571  * a malformed topology (no containing_face on isolated nodes, no
2572  * left/right faces on adjacent edges or mismatching values)
2573  */
2574  if ( newedge.face_left != newedge.face_right )
2575  {
2576  lwerror("Left(%" LWTFMT_ELEMID ")/right(%" LWTFMT_ELEMID ")"
2577  "faces mismatch: invalid topology ?",
2578  newedge.face_left, newedge.face_right);
2579  return -1;
2580  }
2581  else if ( newedge.face_left == -1 )
2582  {
2583  lwerror("Could not derive edge face from linked primitives:"
2584  " invalid topology ?");
2585  return -1;
2586  }
2587 
2588  /*
2589  * Insert the new edge, and update all linking
2590  */
2591 
2592  int ret = lwt_be_insertEdges(topo, &newedge, 1);
2593  if ( ret == -1 ) {
2594  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2595  return -1;
2596  } else if ( ret == 0 ) {
2597  lwerror("Insertion of split edge failed (no reason)");
2598  return -1;
2599  }
2600 
2601  int updfields;
2602 
2603  /* Link prev_left to us
2604  * (if it's not us already) */
2605  if ( llabs(prev_left) != newedge.edge_id )
2606  {
2607  if ( prev_left > 0 )
2608  {
2609  /* its next_left_edge is us */
2610  updfields = LWT_COL_EDGE_NEXT_LEFT;
2611  updedge.next_left = newedge.edge_id;
2612  seledge.edge_id = prev_left;
2613  }
2614  else
2615  {
2616  /* its next_right_edge is us */
2617  updfields = LWT_COL_EDGE_NEXT_RIGHT;
2618  updedge.next_right = newedge.edge_id;
2619  seledge.edge_id = -prev_left;
2620  }
2621 
2622  ret = lwt_be_updateEdges(topo,
2623  &seledge, LWT_COL_EDGE_EDGE_ID,
2624  &updedge, updfields,
2625  NULL, 0);
2626  if ( ret == -1 ) {
2627  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2628  return -1;
2629  }
2630  }
2631 
2632  /* Link prev_right to us
2633  * (if it's not us already) */
2634  if ( llabs(prev_right) != newedge.edge_id )
2635  {
2636  if ( prev_right > 0 )
2637  {
2638  /* its next_left_edge is -us */
2639  updfields = LWT_COL_EDGE_NEXT_LEFT;
2640  updedge.next_left = -newedge.edge_id;
2641  seledge.edge_id = prev_right;
2642  }
2643  else
2644  {
2645  /* its next_right_edge is -us */
2646  updfields = LWT_COL_EDGE_NEXT_RIGHT;
2647  updedge.next_right = -newedge.edge_id;
2648  seledge.edge_id = -prev_right;
2649  }
2650 
2651  ret = lwt_be_updateEdges(topo,
2652  &seledge, LWT_COL_EDGE_EDGE_ID,
2653  &updedge, updfields,
2654  NULL, 0);
2655  if ( ret == -1 ) {
2656  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2657  return -1;
2658  }
2659  }
2660 
2661  /* NOT IN THE SPECS...
2662  * set containing_face = null for start_node and end_node
2663  * if they where isolated
2664  *
2665  */
2666  LWT_ISO_NODE updnode, selnode;
2667  updnode.containing_face = -1;
2668  if ( span.was_isolated )
2669  {
2670  selnode.node_id = start_node;
2671  ret = lwt_be_updateNodes(topo,
2672  &selnode, LWT_COL_NODE_NODE_ID,
2673  &updnode, LWT_COL_NODE_CONTAINING_FACE,
2674  NULL, 0);
2675  if ( ret == -1 ) {
2676  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2677  return -1;
2678  }
2679  }
2680  if ( epan.was_isolated )
2681  {
2682  selnode.node_id = end_node;
2683  ret = lwt_be_updateNodes(topo,
2684  &selnode, LWT_COL_NODE_NODE_ID,
2685  &updnode, LWT_COL_NODE_CONTAINING_FACE,
2686  NULL, 0);
2687  if ( ret == -1 ) {
2688  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2689  return -1;
2690  }
2691  }
2692 
2693  /* Check face splitting */
2694 
2695  if ( ! isclosed && ( epan.was_isolated || span.was_isolated ) )
2696  {
2697  LWDEBUG(1, "New edge is dangling, so it cannot split any face");
2698  return newedge.edge_id; /* no split */
2699  }
2700 
2701  int newface1 = -1;
2702 
2703  /* IDEA: avoid building edge ring if input is closed, which means we
2704  * know in advance it splits a face */
2705 
2706  if ( ! modFace )
2707  {
2708  newface1 = _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 0 );
2709  if ( newface1 == 0 ) {
2710  LWDEBUG(1, "New edge does not split any face");
2711  return newedge.edge_id; /* no split */
2712  }
2713  }
2714 
2715  int newface = _lwt_AddFaceSplit( topo, newedge.edge_id,
2716  newedge.face_left, 0 );
2717  if ( modFace )
2718  {
2719  if ( newface == 0 ) {
2720  LWDEBUG(1, "New edge does not split any face");
2721  return newedge.edge_id; /* no split */
2722  }
2723 
2724  if ( newface < 0 )
2725  {
2726  /* face on the left is the universe face */
2727  /* must be forming a maximal ring in universal face */
2728  newface = _lwt_AddFaceSplit( topo, -newedge.edge_id,
2729  newedge.face_left, 0 );
2730  if ( newface < 0 ) return newedge.edge_id; /* no split */
2731  }
2732  else
2733  {
2734  _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 1 );
2735  }
2736  }
2737 
2738  /*
2739  * Update topogeometries, if needed
2740  */
2741  if ( newedge.face_left != 0 )
2742  {
2743  ret = lwt_be_updateTopoGeomFaceSplit(topo, newedge.face_left,
2744  newface, newface1);
2745  if ( ret == 0 ) {
2746  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2747  return -1;
2748  }
2749 
2750  if ( ! modFace )
2751  {
2752  /* drop old face from the face table */
2753  ret = lwt_be_deleteFacesById(topo, &(newedge.face_left), 1);
2754  if ( ret == -1 ) {
2755  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2756  return -1;
2757  }
2758  }
2759  }
2760 
2761  return newedge.edge_id;
2762 }
static int _lwt_CheckEdgeCrossing(LWT_TOPOLOGY *topo, LWT_ELEMID start_node, LWT_ELEMID end_node, const LWLINE *geom, LWT_ELEMID myself)
Definition: lwgeom_topo.c:593
static void _lwt_release_nodes(LWT_ISO_NODE *nodes, int num_nodes)
Definition: lwgeom_topo.c:481
LWT_ELEMID face_left
#define LWT_COL_NODE_CONTAINING_FACE
LWT_ELEMID containing_face
LWPOINT * geom
int npoints
Definition: liblwgeom.h:355
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1050
static int lwt_be_updateTopoGeomFaceSplit(LWT_TOPOLOGY *topo, LWT_ELEMID split_face, LWT_ELEMID new_face1, LWT_ELEMID new_face2)
Definition: lwgeom_topo.c:347
LWT_ELEMID cwFace
Definition: lwgeom_topo.c:1395
LWLINE * geom
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
static LWT_ELEMID _lwt_AddFaceSplit(LWT_TOPOLOGY *topo, LWT_ELEMID sedge, LWT_ELEMID face, int mbr_only)
Definition: lwgeom_topo.c:1769
LWT_ELEMID nextCCW
Definition: lwgeom_topo.c:1397
POINTARRAY * point
Definition: liblwgeom.h:395
static int lwt_be_updateNodes(LWT_TOPOLOGY *topo, const LWT_ISO_NODE *sel_node, int sel_fields, const LWT_ISO_NODE *upd_node, int upd_fields, const LWT_ISO_NODE *exc_node, int exc_fields)
Definition: lwgeom_topo.c:290
LWT_ELEMID next_left
double x
Definition: liblwgeom.h:312
int p2d_same(const POINT2D *p1, const POINT2D *p2)
Definition: lwalgorithm.c:35
LWGEOM * lwgeom_remove_repeated_points(LWGEOM *in, double tolerance)
Remove repeated points!
Definition: lwgeom.c:1407
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:249
int lwt_be_updateEdges(LWT_TOPOLOGY *topo, const LWT_ISO_EDGE *sel_edge, int sel_fields, const LWT_ISO_EDGE *upd_edge, int upd_fields, const LWT_ISO_EDGE *exc_edge, int exc_fields)
Definition: lwgeom_topo.c:278
double myaz
Definition: lwgeom_topo.c:1401
const LWT_BE_IFACE * be_iface
LWT_ELEMID face_right
LWT_ELEMID node_id
double y
Definition: liblwgeom.h:312
LWT_ELEMID edge_id
int getPoint2d_p(const POINTARRAY *pa, int n, POINT2D *point)
Definition: lwgeom_api.c:448
static int lwt_be_deleteFacesById(const LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int numelems)
Definition: lwgeom_topo.c:211
LWLINE * lwgeom_as_lwline(const LWGEOM *lwgeom)
Definition: lwgeom.c:89
LWT_ELEMID ccwFace
Definition: lwgeom_topo.c:1399
LWT_ELEMID lwt_be_getNextEdgeId(LWT_TOPOLOGY *topo)
Definition: lwgeom_topo.c:223
#define LWT_COL_EDGE_EDGE_ID
Edge fields.
#define LWT_COL_NODE_NODE_ID
Node fields.
#define LWT_COL_EDGE_NEXT_LEFT
static int _lwt_FindAdjacentEdges(LWT_TOPOLOGY *topo, LWT_ELEMID node, edgeend *data, edgeend *other, int myedge_id)
Definition: lwgeom_topo.c:1511
int lwt_be_insertEdges(LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edge, int numelems)
Definition: lwgeom_topo.c:272
#define LWT_COL_NODE_ALL
#define LWT_COL_EDGE_NEXT_RIGHT
LWT_ELEMID start_node
int lwgeom_is_simple(const LWGEOM *lwgeom)
LWT_ELEMID next_right
LWT_INT64 LWT_ELEMID
Identifier of topology element.
LWT_ISO_NODE * lwt_be_getNodeById(LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
Definition: lwgeom_topo.c:160
int was_isolated
Definition: lwgeom_topo.c:1400
LWT_ELEMID nextCW
Definition: lwgeom_topo.c:1393
LWT_ELEMID end_node
int azimuth_pt_pt(const POINT2D *p1, const POINT2D *p2, double *ret)
Compute the azimuth of segment AB in radians.
Definition: measures.c:2411
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
const char * lwt_be_lastErrorMessage(const LWT_BE_IFACE *be)
Definition: lwgeom_topo.c:124
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:74
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:36
POINTARRAY * points
Definition: liblwgeom.h:406

Here is the call graph for this function:

Here is the caller graph for this function: