_lwt_AddFaceSplit()

static LWT_ELEMID _lwt_AddFaceSplit ( LWT_TOPOLOGY *  topo, LWT_ELEMID  sedge, LWT_ELEMID  face, int  mbr_only  )

static

Definition at line 1893 of file lwgeom_topo.c.

{
  uint64_t numfaceedges, i, j;
  int newface_outside;
  uint64_t num_signed_edge_ids;
  LWT_ELEMID *signed_edge_ids;
  LWT_ISO_EDGE *edges;
  LWT_ISO_EDGE *forward_edges = NULL;
  int forward_edges_count = 0;
  LWT_ISO_EDGE *backward_edges = NULL;
  int backward_edges_count = 0;
 
  signed_edge_ids = lwt_be_getRingEdges(topo, sedge, &num_signed_edge_ids, 0);
  if (!signed_edge_ids)
  {
    //PGTOPO_BE_ERRORF("no ring edges for edge %" LWTFMT_ELEMID, sedge);
    PGTOPO_BE_ERROR();
    return -2;
  }
  LWDEBUGF(1, "getRingEdges returned %llu edges", num_signed_edge_ids);
 
  /* You can't get to the other side of an edge forming a ring */
  for (i=0; i<num_signed_edge_ids; ++i) {
    if ( signed_edge_ids[i] == -sedge ) {
      /* No split here */
      LWDEBUG(1, "not a ring");
      lwfree( signed_edge_ids );
      return 0;
    }
  }
 
  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " split face %" LWTFMT_ELEMID " (mbr_only:%d)",
           sedge, face, mbr_only);
 
  /*
   * Construct a polygon using edges of the ring
   *
   * NOTE: this possibly includes dangling edges
   *
   */
  LWPOLY *shell = _lwt_MakeRingShell(topo, signed_edge_ids,
                                     num_signed_edge_ids);
  if ( ! shell ) {
    lwfree( signed_edge_ids );
    /* ring_edges should be NULL */
    lwerror("Could not create ring shell: %s", lwt_be_lastErrorMessage(topo->be_iface));
    return -2;
  }
  const POINTARRAY *pa = shell->rings[0];
  if ( ! ptarray_is_closed_2d(pa) )
  {
    lwpoly_free(shell);
    lwfree( signed_edge_ids );
    lwerror("Corrupted topology: ring of edge %" LWTFMT_ELEMID
            " is geometrically not-closed", sedge);
    return -2;
  }
 
  int isccw = ptarray_isccw(pa);
  LWDEBUGF(1, "Ring of edge %" LWTFMT_ELEMID " is %sclockwise",
              sedge, isccw ? "counter" : "");
  const GBOX* shellbox = lwgeom_get_bbox(lwpoly_as_lwgeom(shell));
 
  if ( face == 0 )
  {
    /* Edge split the universe face */
    if ( ! isccw )
    {
      lwpoly_free(shell);
      lwfree( signed_edge_ids );
      /* Face on the left side of this ring is the universe face.
       * Next call (for the other side) should create the split face
       */
      LWDEBUG(1, "The left face of this clockwise ring is the universe, "
                 "won't create a new face there");
      return -1;
    }
  }
 
  if ( mbr_only && face != 0 )
  {
    if ( isccw )
    {{
      LWT_ISO_FACE updface;
      updface.face_id = face;
      updface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
      int ret = lwt_be_updateFacesById( topo, &updface, 1 );
      if ( ret == -1 )
      {
        lwfree( signed_edge_ids );
        lwpoly_free(shell); /* NOTE: owns shellbox above */
        PGTOPO_BE_ERROR();
        return -2;
      }
      if ( ret != 1 )
      {
        lwfree( signed_edge_ids );
        lwpoly_free(shell); /* NOTE: owns shellbox above */
        lwerror("Unexpected error: %d faces found when expecting 1", ret);
        return -2;
      }
    }}
    lwfree( signed_edge_ids );
    lwpoly_free(shell); /* NOTE: owns shellbox above */
    return -1; /* mbr only was requested */
  }
 
  LWT_ISO_FACE *oldface = NULL;
  LWT_ISO_FACE newface;
  newface.face_id = -1;
  if ( face != 0 && ! isccw)
  {{
    /* Face created an hole in an outer face */
    uint64_t nfaces = 1;
    oldface = lwt_be_getFaceById(topo, &face, &nfaces, LWT_COL_FACE_ALL);
    if (nfaces == UINT64_MAX)
    {
      lwfree( signed_edge_ids );
      lwpoly_free(shell); /* NOTE: owns shellbox */
      PGTOPO_BE_ERROR();
      return -2;
    }
    if ( nfaces != 1 )
    {
      lwfree( signed_edge_ids );
      lwpoly_free(shell); /* NOTE: owns shellbox */
      lwerror("Unexpected error: %" PRIu64 " faces found when expecting 1", nfaces);
      return -2;
    }
    newface.mbr = oldface->mbr;
  }}
  else
  {
    newface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
  }
 
  /* Insert the new face */
  int ret = lwt_be_insertFaces( topo, &newface, 1 );
  if ( ret == -1 )
  {
    lwfree( signed_edge_ids );
    lwpoly_free(shell); /* NOTE: owns shellbox */
    PGTOPO_BE_ERROR();
    return -2;
  }
  if ( ret != 1 )
  {
    lwfree( signed_edge_ids );
    lwpoly_free(shell); /* NOTE: owns shellbox */
    lwerror("Unexpected error: %d faces inserted when expecting 1", ret);
    return -2;
  }
  if ( oldface ) {
    newface.mbr = NULL; /* it is a reference to oldface mbr... */
    _lwt_release_faces(oldface, 1);
  }
 
  /* Update side location of new face edges */
 
  /* We want the new face to be on the left, if possible */
  if ( face != 0 && ! isccw ) { /* ring is clockwise in a real face */
    /* face shrunk, must update all non-contained edges and nodes */
    LWDEBUG(1, "New face is on the outside of the ring, updating rings in former shell");
    newface_outside = 1;
    /* newface is outside */
  } else {
    LWDEBUG(1, "New face is on the inside of the ring, updating forward edges in new ring");
    newface_outside = 0;
    /* newface is inside */
  }
 
  /* Update edges bounding the old face */
  /* (1) fetch all edges where left_face or right_face is = oldface */
  int fields = LWT_COL_EDGE_EDGE_ID |
               LWT_COL_EDGE_FACE_LEFT |
               LWT_COL_EDGE_FACE_RIGHT |
               LWT_COL_EDGE_GEOM
               ;
  numfaceedges = 1;
  edges = lwt_be_getEdgeByFace( topo, &face, &numfaceedges, fields, newface.mbr );
  if (numfaceedges == UINT64_MAX)
  {
    lwfree(signed_edge_ids);
    PGTOPO_BE_ERROR();
    return -2;
  }
  LWDEBUGF(1, "_lwt_AddFaceSplit: lwt_be_getEdgeByFace(%" LWTFMT_ELEMID ") returned %llu edges", face, numfaceedges);
 
  if ( numfaceedges )
  {
    forward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
    forward_edges_count = 0;
    backward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
    backward_edges_count = 0;
 
    /* (2) loop over the results and: */
    for ( i=0; i<numfaceedges; ++i )
    {
      LWT_ISO_EDGE *e = &(edges[i]);
      int found = 0;
      int contains;
      POINT2D ep;
 
      /* (2.1) skip edges whose ID is in the list of boundary edges */
      for ( j=0; j<num_signed_edge_ids; ++j )
      {
        int seid = signed_edge_ids[j]; /* signed ring edge id */
        if ( seid == e->edge_id )
        {
          /* IDEA: remove entry from signed_edge_ids, to speed next loop ? */
          LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " is a known forward edge of the new ring", e->edge_id);
          forward_edges[forward_edges_count].edge_id = e->edge_id;
          forward_edges[forward_edges_count++].face_left = newface.face_id;
          found++;
          if ( found == 2 ) break; /* both edge sides are found on the ring */
        }
        else if ( -seid == e->edge_id )
        {
          /* IDEA: remove entry from signed_edge_ids, to speed next loop ? */
          LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " is a known backward edge of the new ring", e->edge_id);
          backward_edges[backward_edges_count].edge_id = e->edge_id;
          backward_edges[backward_edges_count++].face_right = newface.face_id;
          found++;
          if ( found == 2 ) break; /* both edge sides are found on the ring */
        }
      }
      if ( found ) continue;
      LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " is not a known edge of the new ring", e->edge_id);
 
      /* Check if the edge is now binding a different face */
 
      if ( ! getPoint2d_p(e->geom->points, 0, &ep) )
      {
        lwfree(signed_edge_ids);
        lwpoly_free(shell);
        lwfree(forward_edges); /* contents owned by edges */
        lwfree(backward_edges); /* contents owned by edges */
        _lwt_release_edges(edges, numfaceedges);
        lwerror("Edge %" LWTFMT_ELEMID " is empty", e->edge_id);
        return -2;
      }
 
      contains = gbox_contains_point2d(shellbox, &ep) == LW_TRUE ? LW_INSIDE : LW_OUTSIDE;
      contains = contains == LW_INSIDE ? ptarray_contains_point(pa, &ep) : contains;
 
      LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " first point %s new ring",
          e->edge_id, (contains == LW_INSIDE ? "inside" :
           contains == LW_OUTSIDE ? "outside" : "on boundary of"));
 
      /* (2.2) skip edges (NOT, if newface_outside) contained in ring */
      if ( newface_outside )
      {
        if ( contains != LW_OUTSIDE )
        {
          LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " not outside of the new ring, not updating it",
                      e->edge_id);
          continue;
        }
      }
      else
      {
        if ( contains != LW_INSIDE )
        {
          LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " not inside the new ring, not updating it",
                      e->edge_id);
          continue;
        }
      }
 
      /* (2.3) push to forward_edges if left_face = oface */
      if ( e->face_left == face )
      {
        LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " has new face on the left side", e->edge_id);
        forward_edges[forward_edges_count].edge_id = e->edge_id;
        forward_edges[forward_edges_count++].face_left = newface.face_id;
      }
 
      /* (2.4) push to backward_edges if right_face = oface */
      if ( e->face_right == face )
      {
        LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " has new face on the right side", e->edge_id);
        backward_edges[backward_edges_count].edge_id = e->edge_id;
        backward_edges[backward_edges_count++].face_right = newface.face_id;
      }
    }
 
    /* Update forward edges */
    if ( forward_edges_count )
    {
      ret = lwt_be_updateEdgesById(topo, forward_edges,
                                   forward_edges_count,
                                   LWT_COL_EDGE_FACE_LEFT);
      if ( ret == -1 )
      {
        lwfree( signed_edge_ids );
        PGTOPO_BE_ERROR();
        return -2;
      }
      if ( ret != forward_edges_count )
      {
        lwfree( signed_edge_ids );
        lwerror("Unexpected error: %d edges updated when expecting %d",
                ret, forward_edges_count);
        return -2;
      }
    }
 
    /* Update backward edges */
    if ( backward_edges_count )
    {
      ret = lwt_be_updateEdgesById(topo, backward_edges,
                                   backward_edges_count,
                                   LWT_COL_EDGE_FACE_RIGHT);
      if ( ret == -1 )
      {
        lwfree( signed_edge_ids );
        PGTOPO_BE_ERROR();
        return -2;
      }
      if ( ret != backward_edges_count )
      {
        lwfree( signed_edge_ids );
        lwerror("Unexpected error: %d edges updated when expecting %d",
                ret, backward_edges_count);
        return -2;
      }
    }
 
    lwfree(forward_edges);
    lwfree(backward_edges);
 
    _lwt_release_edges(edges, numfaceedges);
  }
 
  /* Update isolated nodes which are now in new face */
  uint64_t numisonodes = 1;
  fields = LWT_COL_NODE_NODE_ID | LWT_COL_NODE_GEOM;
  LWT_ISO_NODE *nodes = lwt_be_getNodeByFace(topo, &face,
                                             &numisonodes, fields, newface.mbr);
  if (numisonodes == UINT64_MAX)
  {
    lwfree(signed_edge_ids);
    PGTOPO_BE_ERROR();
    return -2;
  }
  if ( numisonodes ) {
    LWT_ISO_NODE *updated_nodes = lwalloc(sizeof(LWT_ISO_NODE)*numisonodes);
    int nodes_to_update = 0;
    for (i=0; i<numisonodes; ++i)
    {
      LWT_ISO_NODE *n = &(nodes[i]);
      const POINT2D *pt = getPoint2d_cp(n->geom->point, 0);
      int contains = ptarray_contains_point(pa, pt) == LW_INSIDE;
      LWDEBUGF(1, "Node %" LWTFMT_ELEMID " is %scontained in new ring, newface is %s",
                  n->node_id, contains ? "" : "not ",
                  newface_outside ? "outside" : "inside" );
      if ( newface_outside )
      {
        if ( contains )
        {
          LWDEBUGF(1, "Node %" LWTFMT_ELEMID " contained in an hole of the new face",
                      n->node_id);
          continue;
        }
      }
      else
      {
        if ( ! contains )
        {
          LWDEBUGF(1, "Node %" LWTFMT_ELEMID " not contained in the face shell",
                      n->node_id);
          continue;
        }
      }
      updated_nodes[nodes_to_update].node_id = n->node_id;
      updated_nodes[nodes_to_update++].containing_face =
                                       newface.face_id;
      LWDEBUGF(1, "Node %" LWTFMT_ELEMID " will be updated", n->node_id);
    }
    _lwt_release_nodes(nodes, numisonodes);
    if ( nodes_to_update )
    {
      int ret = lwt_be_updateNodesById(topo, updated_nodes,
                                       nodes_to_update,
                                       LWT_COL_NODE_CONTAINING_FACE);
      if ( ret == -1 ) {
        lwfree( signed_edge_ids );
        PGTOPO_BE_ERROR();
        return -2;
      }
    }
    lwfree(updated_nodes);
  }
 
  lwfree(signed_edge_ids);
  lwpoly_free(shell);
 
  return newface.face_id;
}

References _lwt_MakeRingShell(), _lwt_release_edges(), _lwt_release_faces(), _lwt_release_nodes(), LWT_TOPOLOGY_T::be_iface, LWT_ISO_NODE::containing_face, contains(), LWT_ISO_EDGE::edge_id, LWT_ISO_FACE::face_id, LWT_ISO_EDGE::face_left, LWT_ISO_EDGE::face_right, gbox_contains_point2d(), LWT_ISO_NODE::geom, LWT_ISO_EDGE::geom, getPoint2d_cp(), getPoint2d_p(), LW_INSIDE, LW_OUTSIDE, LW_TRUE, lwalloc(), LWDEBUG, LWDEBUGF, lwerror(), lwfree(), lwgeom_get_bbox(), lwpoly_as_lwgeom(), lwpoly_free(), lwt_be_getEdgeByFace(), lwt_be_getFaceById(), lwt_be_getNodeByFace(), lwt_be_getRingEdges(), lwt_be_insertFaces(), lwt_be_lastErrorMessage(), lwt_be_updateEdgesById(), lwt_be_updateFacesById(), lwt_be_updateNodesById(), LWT_COL_EDGE_EDGE_ID, LWT_COL_EDGE_FACE_LEFT, LWT_COL_EDGE_FACE_RIGHT, LWT_COL_EDGE_GEOM, LWT_COL_FACE_ALL, LWT_COL_NODE_CONTAINING_FACE, LWT_COL_NODE_GEOM, LWT_COL_NODE_NODE_ID, LWTFMT_ELEMID, LWT_ISO_FACE::mbr, LWT_ISO_NODE::node_id, PGTOPO_BE_ERROR, LWPOINT::point, LWLINE::points, ptarray_contains_point(), ptarray_is_closed_2d(), ptarray_isccw(), and LWPOLY::rings.

Referenced by _lwt_AddEdge(), and _lwt_SnapEdgeToExistingNode().

Here is the call graph for this function:

Here is the caller graph for this function: