_lwt_AddEdge()

static LWT_ELEMID _lwt_AddEdge ( LWT_TOPOLOGY *  topo, LWT_ELEMID  start_node, LWT_ELEMID  end_node, LWLINE *  geom, int  skipChecks, int  modFace  )

static

Parameters

modFace

can be 0 - have two new faces replace a split face 1 - modify a split face, adding a new one -1 - do not check at all for face splitting

Definition at line 2303 of file lwgeom_topo.c.

{
  LWT_ISO_EDGE newedge;
  LWGEOM *cleangeom;
  edgeend span; /* start point analysis */
  edgeend epan; /* end point analysis */
  POINT2D p1, pn, p2;
  POINTARRAY *pa;
  LWT_ELEMID node_ids[2];
  const LWPOINT *start_node_geom = NULL;
  const LWPOINT *end_node_geom = NULL;
  uint64_t num_nodes;
  LWT_ISO_NODE *endpoints;
  uint64_t i;
  LWT_ELEMID prev_left;
  LWT_ELEMID prev_right;
  LWT_ISO_EDGE seledge;
  LWT_ISO_EDGE updedge;
 
  if ( ! skipChecks )
  {
    /* curve must be simple */
    if ( ! lwgeom_is_simple(lwline_as_lwgeom(geom)) )
    {
      lwerror("SQL/MM Spatial exception - curve not simple");
      return -1;
    }
  }
 
  newedge.start_node = start_node;
  newedge.end_node = end_node;
  newedge.geom = geom;
  newedge.face_left = -1;
  newedge.face_right = -1;
  /* TODO: should do the repeated points removal in 2D space */
  cleangeom = lwgeom_remove_repeated_points( lwline_as_lwgeom(geom), 0 );
 
  pa = lwgeom_as_lwline(cleangeom)->points;
  if ( pa->npoints < 2 ) {
    lwgeom_free(cleangeom);
    lwerror("Invalid edge (no two distinct vertices exist)");
    return -1;
  }
 
  /* Initialize endpoint info (some of that ) */
  span.cwFace = span.ccwFace =
  epan.cwFace = epan.ccwFace = -1;
 
  /* Compute azimuth of first edge end on start node */
  getPoint2d_p(pa, 0, &p1);
  if ( ! _lwt_FirstDistinctVertex2D(pa, &p1, 0, 1, &pn) )
  {
    lwgeom_free(cleangeom);
    lwerror("Invalid edge (no two distinct vertices exist)");
    return -1;
  }
  if ( ! azimuth_pt_pt(&p1, &pn, &span.myaz) ) {
    lwgeom_free(cleangeom);
    lwerror("error computing azimuth of first edgeend [%.15g %.15g,%.15g %.15g]",
            p1.x, p1.y, pn.x, pn.y);
    return -1;
  }
  LWDEBUGF(1, "edge's start node is %g,%g", p1.x, p1.y);
 
  /* Compute azimuth of last edge end on end node */
  getPoint2d_p(pa, pa->npoints-1, &p2);
  if ( ! _lwt_FirstDistinctVertex2D(pa, &p2, pa->npoints-1, -1, &pn) )
  {
    lwgeom_free(cleangeom);
    /* This should never happen as we checked the edge while computing first edgend */
    lwerror("Invalid clean edge (no two distinct vertices exist) - should not happen");
    return -1;
  }
  lwgeom_free(cleangeom);
  if ( ! azimuth_pt_pt(&p2, &pn, &epan.myaz) ) {
    lwerror("error computing azimuth of last edgeend [%.15g %.15g,%.15g %.15g]",
            p2.x, p2.y, pn.x, pn.y);
    return -1;
  }
  LWDEBUGF(1, "edge's end node is %g,%g", p2.x, p2.y);
 
  /*
   * Check endpoints existence, match with Curve geometry
   * and get face information (if any)
   */
 
  if ( start_node != end_node ) {
    num_nodes = 2;
    node_ids[0] = start_node;
    node_ids[1] = end_node;
  } else {
    num_nodes = 1;
    node_ids[0] = start_node;
  }
 
  endpoints = lwt_be_getNodeById( topo, node_ids, &num_nodes, LWT_COL_NODE_ALL );
  if (num_nodes == UINT64_MAX)
  {
    PGTOPO_BE_ERROR();
    return -1;
  }
  for ( i=0; i<num_nodes; ++i )
  {
    LWT_ISO_NODE* node = &(endpoints[i]);
    if ( modFace != -1 && node->containing_face != -1 )
    {
      if ( newedge.face_left == -1 )
      {
        newedge.face_left = newedge.face_right = node->containing_face;
      }
      else if ( newedge.face_left != node->containing_face )
      {
        _lwt_release_nodes(endpoints, num_nodes);
        lwerror("SQL/MM Spatial exception - geometry crosses an edge"
                " (endnodes in faces %" LWTFMT_ELEMID " and %" LWTFMT_ELEMID ")",
                newedge.face_left, node->containing_face);
      }
    }
 
    LWDEBUGF(1, "Node %" LWTFMT_ELEMID ", with geom %p (looking for %"
             LWTFMT_ELEMID " and %" LWTFMT_ELEMID ")",
             node->node_id, node->geom, start_node, end_node);
    if ( node->node_id == start_node ) {
      start_node_geom = node->geom;
    }
    if ( node->node_id == end_node ) {
      end_node_geom = node->geom;
    }
  }
 
  if ( ! skipChecks )
  {
    if ( ! start_node_geom )
    {
      if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
      lwerror("SQL/MM Spatial exception - non-existent node");
      return -1;
    }
    else
    {
      pa = start_node_geom->point;
      getPoint2d_p(pa, 0, &pn);
      if ( ! P2D_SAME_STRICT(&pn, &p1) )
      {
        if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
        lwerror("SQL/MM Spatial exception"
                " - start node not geometry start point."
                //" - start node not geometry start point (%g,%g != %g,%g).", pn.x, pn.y, p1.x, p1.y
        );
        return -1;
      }
    }
 
    if ( ! end_node_geom )
    {
      if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
      lwerror("SQL/MM Spatial exception - non-existent node");
      return -1;
    }
    else
    {
      pa = end_node_geom->point;
      getPoint2d_p(pa, 0, &pn);
      if ( ! P2D_SAME_STRICT(&pn, &p2) )
      {
        if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
        lwerror("SQL/MM Spatial exception"
                " - end node not geometry end point."
                //" - end node not geometry end point (%g,%g != %g,%g).", pn.x, pn.y, p2.x, p2.y
        );
        return -1;
      }
    }
 
    if ( num_nodes ) _lwt_release_nodes(endpoints, num_nodes);
 
    if ( _lwt_CheckEdgeCrossing( topo, start_node, end_node, geom, 0 ) )
      return -1;
 
  } /* ! skipChecks */
 
  /*
   * All checks passed, time to prepare the new edge
   */
 
  newedge.edge_id = lwt_be_getNextEdgeId( topo );
  if ( newedge.edge_id == -1 ) {
    PGTOPO_BE_ERROR();
    return -1;
  }
 
  /* Find adjacent edges to each endpoint */
  int isclosed = start_node == end_node;
  int found;
  found = _lwt_FindAdjacentEdges( topo, start_node, &span,
                                  isclosed ? &epan : NULL, -1 );
  if ( found ) {
    span.was_isolated = 0;
    newedge.next_right = span.nextCW ? span.nextCW : -newedge.edge_id;
    prev_left = span.nextCCW ? -span.nextCCW : newedge.edge_id;
    LWDEBUGF(1, "New edge %" LWTFMT_ELEMID " is connected on start node, "
                "next_right is %" LWTFMT_ELEMID
                ", prev_left is %" LWTFMT_ELEMID,
                newedge.edge_id, newedge.next_right, prev_left);
    if ( modFace != -1 )
    {
      if ( newedge.face_right == -1 ) {
        newedge.face_right = span.cwFace;
      }
      if ( newedge.face_left == -1 ) {
        newedge.face_left = span.ccwFace;
      }
    }
  } else {
    span.was_isolated = 1;
    newedge.next_right = isclosed ? -newedge.edge_id : newedge.edge_id;
    prev_left = isclosed ? newedge.edge_id : -newedge.edge_id;
    LWDEBUGF(1, "New edge %" LWTFMT_ELEMID " is isolated on start node, "
                "next_right is %" LWTFMT_ELEMID
                ", prev_left is %" LWTFMT_ELEMID,
                newedge.edge_id, newedge.next_right, prev_left);
  }
 
  found = _lwt_FindAdjacentEdges( topo, end_node, &epan,
                                  isclosed ? &span : NULL, -1 );
  if ( found ) {
    epan.was_isolated = 0;
    newedge.next_left = epan.nextCW ? epan.nextCW : newedge.edge_id;
    prev_right = epan.nextCCW ? -epan.nextCCW : -newedge.edge_id;
    LWDEBUGF(1, "New edge %" LWTFMT_ELEMID " is connected on end node, "
                "next_left is %" LWTFMT_ELEMID
                ", prev_right is %" LWTFMT_ELEMID,
                newedge.edge_id, newedge.next_left, prev_right);
    if ( modFace != -1 )
    {
      if ( newedge.face_right == -1 ) {
        newedge.face_right = span.ccwFace;
      } else if ( newedge.face_right != epan.ccwFace ) {
        /* side-location conflict */
        lwerror("Side-location conflict: "
                "new edge starts in face"
                 " %" LWTFMT_ELEMID " and ends in face"
                 " %" LWTFMT_ELEMID,
                newedge.face_right, epan.ccwFace
        );
        return -1;
      }
      if ( newedge.face_left == -1 ) {
        newedge.face_left = span.cwFace;
      } else if ( newedge.face_left != epan.cwFace ) {
        /* side-location conflict */
        lwerror("Side-location conflict: "
                "new edge starts in face"
                 " %" LWTFMT_ELEMID " and ends in face"
                 " %" LWTFMT_ELEMID,
                newedge.face_left, epan.cwFace
        );
        return -1;
      }
    }
  } else {
    epan.was_isolated = 1;
    newedge.next_left = isclosed ? newedge.edge_id : -newedge.edge_id;
    prev_right = isclosed ? -newedge.edge_id : newedge.edge_id;
    LWDEBUGF(1, "New edge %" LWTFMT_ELEMID " is isolated on end node, "
                "next_left is %" LWTFMT_ELEMID
                ", prev_right is %" LWTFMT_ELEMID,
                newedge.edge_id, newedge.next_left, prev_right);
  }
 
  /*
   * If we don't have faces setup by now we must have encountered
   * a malformed topology (no containing_face on isolated nodes, no
   * left/right faces on adjacent edges or mismatching values)
   */
  if ( modFace > -1 )
  {
    if ( newedge.face_left != newedge.face_right )
    {
      lwerror("Left(%" LWTFMT_ELEMID ")/right(%" LWTFMT_ELEMID ")"
              " faces mismatch: invalid topology ?",
              newedge.face_left, newedge.face_right);
      return -1;
    }
    else if ( newedge.face_left == -1 )
    {
      lwerror("Could not derive edge face from linked primitives:"
              " invalid topology ?");
      return -1;
    }
  }
 
  /*
   * Insert the new edge, and update all linking
   */
 
  int ret = lwt_be_insertEdges(topo, &newedge, 1);
  if ( ret == -1 ) {
    PGTOPO_BE_ERROR();
    return -1;
  } else if ( ret == 0 ) {
    lwerror("Insertion of split edge failed (no reason)");
    return -1;
  }
 
  int updfields;
 
  /* Link prev_left to us
   * (if it's not us already) */
  if ( llabs(prev_left) != newedge.edge_id )
  {
    if ( prev_left > 0 )
    {
      /* its next_left_edge is us */
      updfields = LWT_COL_EDGE_NEXT_LEFT;
      updedge.next_left = newedge.edge_id;
      seledge.edge_id = prev_left;
    }
    else
    {
      /* its next_right_edge is us */
      updfields = LWT_COL_EDGE_NEXT_RIGHT;
      updedge.next_right = newedge.edge_id;
      seledge.edge_id = -prev_left;
    }
 
    ret = lwt_be_updateEdges(topo,
        &seledge, LWT_COL_EDGE_EDGE_ID,
        &updedge, updfields,
        NULL, 0);
    if ( ret == -1 ) {
      PGTOPO_BE_ERROR();
      return -1;
    }
  }
 
  /* Link prev_right to us
   * (if it's not us already) */
  if ( llabs(prev_right) != newedge.edge_id )
  {
    if ( prev_right > 0 )
    {
      /* its next_left_edge is -us */
      updfields = LWT_COL_EDGE_NEXT_LEFT;
      updedge.next_left = -newedge.edge_id;
      seledge.edge_id = prev_right;
    }
    else
    {
      /* its next_right_edge is -us */
      updfields = LWT_COL_EDGE_NEXT_RIGHT;
      updedge.next_right = -newedge.edge_id;
      seledge.edge_id = -prev_right;
    }
 
    ret = lwt_be_updateEdges(topo,
        &seledge, LWT_COL_EDGE_EDGE_ID,
        &updedge, updfields,
        NULL, 0);
    if ( ret == -1 ) {
      PGTOPO_BE_ERROR();
      return -1;
    }
  }
 
  /* NOT IN THE SPECS...
   * set containing_face = null for start_node and end_node
   * if they where isolated
   *
   */
  LWT_ISO_NODE updnode, selnode;
  updnode.containing_face = -1;
  if ( span.was_isolated )
  {
    selnode.node_id = start_node;
    ret = lwt_be_updateNodes(topo,
        &selnode, LWT_COL_NODE_NODE_ID,
        &updnode, LWT_COL_NODE_CONTAINING_FACE,
        NULL, 0);
    if ( ret == -1 ) {
      PGTOPO_BE_ERROR();
      return -1;
    }
  }
  if ( epan.was_isolated )
  {
    selnode.node_id = end_node;
    ret = lwt_be_updateNodes(topo,
        &selnode, LWT_COL_NODE_NODE_ID,
        &updnode, LWT_COL_NODE_CONTAINING_FACE,
        NULL, 0);
    if ( ret == -1 ) {
      PGTOPO_BE_ERROR();
      return -1;
    }
  }
 
  /* Check face splitting, if required */
 
  if ( modFace > -1 ) {
 
  if ( ! isclosed && ( epan.was_isolated || span.was_isolated ) )
  {
    LWDEBUG(1, "New edge is dangling, so it cannot split any face");
    return newedge.edge_id; /* no split */
  }
 
  int newface1 = -1;
 
  /* IDEA: avoid building edge ring if input is closed, which means we
   *       know in advance it splits a face */
 
  if ( ! modFace )
  {
    newface1 = _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 0 );
    if ( newface1 == 0 ) {
      LWDEBUG(1, "New edge does not split any face");
      return newedge.edge_id; /* no split */
    }
  }
 
  int newface = _lwt_AddFaceSplit( topo, newedge.edge_id,
                                   newedge.face_left, 0 );
  if ( modFace )
  {
    if ( newface == 0 ) {
      LWDEBUG(1, "New edge does not split any face");
      return newedge.edge_id; /* no split */
    }
 
    if ( newface < 0 )
    {
      /* face on the left is the universe face */
      /* must be forming a maximal ring in universal face */
      newface = _lwt_AddFaceSplit( topo, -newedge.edge_id,
                                   newedge.face_left, 0 );
      if ( newface < 0 ) return newedge.edge_id; /* no split */
    }
    else
    {
      _lwt_AddFaceSplit( topo, -newedge.edge_id, newedge.face_left, 1 );
    }
  }
 
  /*
   * Update topogeometries, if needed
   */
  if ( newedge.face_left != 0 )
  {
    ret = lwt_be_updateTopoGeomFaceSplit(topo, newedge.face_left,
                                         newface, newface1);
    if ( ret == 0 ) {
      PGTOPO_BE_ERROR();
      return -1;
    }
 
    if ( ! modFace )
    {
      /* drop old face from the face table */
      ret = lwt_be_deleteFacesById(topo, &(newedge.face_left), 1);
      if ( ret == -1 ) {
        PGTOPO_BE_ERROR();
        return -1;
      }
    }
  }
 
  } // end of face split checking
 
  return newedge.edge_id;
}

References _lwt_AddFaceSplit(), _lwt_CheckEdgeCrossing(), _lwt_FindAdjacentEdges(), _lwt_FirstDistinctVertex2D(), _lwt_release_nodes(), azimuth_pt_pt(), 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_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_STRICT, PGTOPO_BE_ERROR, LWPOINT::point, LWLINE::points, LWT_ISO_EDGE::start_node, edgeend_t::was_isolated, POINT2D::x, and POINT2D::y.

Referenced by _lwt_AddLineEdge(), lwt_AddEdgeModFace(), and lwt_AddEdgeNewFaces().

Here is the call graph for this function:

Here is the caller graph for this function: