_lwt_AddLine()

static LWT_ELEMID * _lwt_AddLine ( LWT_TOPOLOGY *  topo, LWLINE *  line, double  tol, int *  nedges, int  handleFaceSplit, int  maxNewEdges  )

static

Definition at line 7253 of file lwgeom_topo.c.

{
  LWGEOM *geomsbuf[1];
  LWGEOM **geoms;
  uint32_t ngeoms;
  LWGEOM *noded, *tmp;
  LWCOLLECTION *col;
  LWT_ELEMID *ids;
  LWT_ISO_EDGE *edges;
  LWT_ISO_NODE *nodes;
  uint64_t num, numedges = 0, numnodes = 0;
  int num_new_edges = 0;
  uint64_t i;
  GBOX qbox;
  int forward;
  int input_was_closed = 0;
  POINT4D originalStartPoint;
 
  if ( lwline_is_empty(line) )
  {
    *nedges = 0;
    return NULL;
  }
 
  if ( lwline_is_closed(line) )
  {
    input_was_closed = 1;
    getPoint4d_p( line->points, 0, &originalStartPoint);
    LWDEBUGF(1, "Input line is closed, original point is %g,%g", originalStartPoint.x, originalStartPoint.y);
  }
 
  *nedges = -1; /* error condition, by default */
 
  /* Get tolerance, if 0 was given */
  if ( tol == -1 ) tol = _LWT_MINTOLERANCE( topo, (LWGEOM*)line );
  LWDEBUGF(1, "Working tolerance:%.15g", tol);
  LWDEBUGF(1, "Input line has srid=%d", line->srid);
 
  /* Remove consecutive vertices below given tolerance upfront */
  if ( tol )
  {{
    LWLINE *clean = lwgeom_as_lwline(lwline_remove_repeated_points(line, tol));
    tmp = lwline_as_lwgeom(clean); /* NOTE: might collapse to non-simple */
    LWDEBUGG(1, tmp, "Repeated-point removed");
  }} else tmp=(LWGEOM*)line;
 
  /* 1. Self-node */
  noded = lwgeom_node((LWGEOM*)tmp);
  if ( tmp != (LWGEOM*)line ) lwgeom_free(tmp);
  if ( ! noded ) return NULL; /* should have called lwerror already */
  LWDEBUGG(1, noded, "Noded");
 
  qbox = *lwgeom_get_bbox( lwline_as_lwgeom(line) );
  LWDEBUGF(1, "Line BOX is %.15g %.15g, %.15g %.15g", qbox.xmin, qbox.ymin,
                                          qbox.xmax, qbox.ymax);
  gbox_expand(&qbox, tol);
  LWDEBUGF(1, "BOX expanded by %g is %.15g %.15g, %.15g %.15g",
              tol, qbox.xmin, qbox.ymin, qbox.xmax, qbox.ymax);
 
  LWGEOM **nearby = 0;
  int nearbyindex = 0;
  int nearbycount = 0;
 
  /* 2.0. Find edges falling within tol distance */
  edges = lwt_be_getEdgeWithinBox2D( topo, &qbox, &numedges, LWT_COL_EDGE_ALL, 0 );
  if (numedges == UINT64_MAX)
  {
    lwgeom_free(noded);
    PGTOPO_BE_ERROR();
    return NULL;
  }
  LWDEBUGF(1, "Line has %u points, its bbox intersects %llu edges bboxes",
    line->points->npoints, numedges);
  if ( numedges )
  {{
    /* TODO: compute earlier for reuse later ? */
    GEOSGeometry *noded_g = LWGEOM2GEOS(noded, 0);
    /* collect those whose distance from us is < tol */
    nearbycount += numedges;
    nearby = lwalloc(numedges * sizeof(LWGEOM *));
    for (i=0; i<numedges; ++i)
    {{
      LW_ON_INTERRUPT(return NULL);
      LWT_ISO_EDGE *e = &(edges[i]);
      LWGEOM *g = lwline_as_lwgeom(e->geom);
      GEOSGeometry *edge_g = LWGEOM2GEOS(g, 0);
      LWDEBUGF(2, "Computing distance from edge %" LWTFMT_ELEMID " with %u points", i, e->geom->points->npoints);
      double dist;
      if ( 0 == GEOSDistanceIndexed(edge_g, noded_g, &dist) ) {
        GEOSGeom_destroy(edge_g);
        GEOSGeom_destroy(noded_g);
        lwgeom_free(noded);
        lwerror("GEOSDistanceIndexed error: %s", lwgeom_geos_errmsg);
        return NULL;
      }
      GEOSGeom_destroy(edge_g);
      if ( dist && dist >= tol ) continue;
      nearby[nearbyindex++] = g;
    }}
    LWDEBUGF(1, "Found %d edges closer than tolerance (%g)", nearbyindex, tol);
    GEOSGeom_destroy(noded_g);
  }}
  int nearbyedgecount = nearbyindex;
 
  /* 2.1. Find isolated nodes falling within tol distance
   *
   * TODO: add backend-interface support for only getting isolated nodes
   */
  nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &numnodes, LWT_COL_NODE_ALL, 0 );
  if (numnodes == UINT64_MAX)
  {
    lwgeom_free(noded);
    PGTOPO_BE_ERROR();
    return NULL;
  }
  LWDEBUGF(1, "Line bbox intersects %llu nodes bboxes", numnodes);
  if ( numnodes )
  {{
    /* collect those whose distance from us is < tol */
    nearbycount = nearbyedgecount + numnodes;
    nearby = nearby ?
        lwrealloc(nearby, nearbycount * sizeof(LWGEOM *))
        :
        lwalloc(nearbycount * sizeof(LWGEOM *))
        ;
    int nn = 0;
    for (i=0; i<numnodes; ++i)
    {
      LWT_ISO_NODE *n = &(nodes[i]);
      if ( n->containing_face == -1 ) continue; /* skip not-isolated nodes */
      LWGEOM *g = lwpoint_as_lwgeom(n->geom);
      double dist = lwgeom_mindistance2d(g, noded);
      /* must be closer than tolerated, unless distance is zero */
      if ( dist && dist >= tol )
      {
        LWDEBUGF(1, "Node %" LWTFMT_ELEMID " is %g units away, we tolerate only %g", n->node_id, dist, tol);
        continue;
      }
      nearby[nearbyindex++] = g;
      nn = nn + 1;
    }
    LWDEBUGF(1, "Found %d isolated nodes closer than tolerance (%g)", nn, tol);
  }}
  int nearbynodecount = nearbyindex - nearbyedgecount;
  nearbycount = nearbyindex;
 
  LWDEBUGF(1, "Number of nearby elements is %d", nearbycount);
 
  /* 2.2. Snap to nearby elements */
  if ( nearbycount )
  {{
    LWCOLLECTION *col;
    LWGEOM *elems;
 
    col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
                                 NULL, nearbycount, nearby);
    elems = lwcollection_as_lwgeom(col);
 
    LWDEBUGG(1, elems, "Collected nearby elements");
 
    tmp = _lwt_toposnap(noded, elems, tol);
    lwgeom_free(noded);
    noded = tmp;
    LWDEBUGG(1, noded, "Elements-snapped");
    if ( input_was_closed )
    {{
      /* Recompute start point in case it moved */
      LWLINE *scrolled = lwgeom_as_lwline(noded);
      if (scrolled)
      {
        getPoint4d_p( scrolled->points, 0, &originalStartPoint);
        LWDEBUGF(1, "Closed input line start point after snap %g,%g", originalStartPoint.x, originalStartPoint.y);
      }
    }}
 
    /* will not release the geoms array */
    lwcollection_release(col);
 
    /*
    -- re-node to account for ST_Snap introduced self-intersections
    -- See http://trac.osgeo.org/postgis/ticket/1714
    -- TODO: consider running UnaryUnion once after all noding
    */
    tmp = lwgeom_unaryunion(noded);
    lwgeom_free(noded);
    noded = tmp;
    LWDEBUGG(1, noded, "Unary-unioned");
  }}
 
  /* 2.3. Node with nearby edges */
  if ( nearbyedgecount )
  {{
    LWCOLLECTION *col;
    LWGEOM *iedges; /* just an alias for col */
    LWGEOM *diff, *xset;
 
    LWDEBUGF(1, "Line intersects %d edges", nearbyedgecount);
 
    col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
                                 NULL, nearbyedgecount, nearby);
    iedges = lwcollection_as_lwgeom(col);
    LWDEBUGG(1, iedges, "Collected edges");
 
    LWDEBUGF(1, "Diffing noded, with srid=%d "
                "and intersecting edges, with srid=%d",
                noded->srid, iedges->srid);
    diff = lwgeom_difference(noded, iedges);
    LWDEBUGG(1, diff, "Differenced");
 
    LWDEBUGF(1, "Intersecting noded, with srid=%d "
                "and intersecting edges, with srid=%d",
                noded->srid, iedges->srid);
    xset = lwgeom_intersection(noded, iedges);
    LWDEBUGG(1, xset, "Intersected");
    lwgeom_free(noded);
 
    /* We linemerge here because INTERSECTION, as of GEOS 3.8,
     * will result in shared segments being output as multiple
     * lines rather than a single line. Example:
 
          INTERSECTION(
            'LINESTRING(0 0, 5 0, 8 0, 10 0,12 0)',
            'LINESTRING(5 0, 8 0, 10 0)'
          )
          ==
          MULTILINESTRING((5 0,8 0),(8 0,10 0))
 
     * We will re-split in a subsequent step, by splitting
     * the final line with pre-existing nodes
     */
    LWDEBUG(1, "Linemerging intersection");
    tmp = lwgeom_linemerge(xset);
    LWDEBUGG(1, tmp, "Linemerged");
    lwgeom_free(xset);
    xset = tmp;
 
    /*
     * Here we union the (linemerged) intersection with
     * the difference (new lines)
     */
    LWDEBUG(1, "Unioning difference and (linemerged) intersection");
    noded = lwgeom_union(diff, xset);
    LWDEBUGG(1, noded, "Diff-Xset Unioned");
    lwgeom_free(xset);
    lwgeom_free(diff);
 
    /* will not release the geoms array */
    lwcollection_release(col);
 
    if ( input_was_closed )
    {{
      LWLINE *scrolled = lwgeom_as_lwline(noded);
      if (scrolled) {
        if ( lwline_is_closed(scrolled) ) {
          ptarray_scroll_in_place(scrolled->points, &originalStartPoint);
        }
        else {
          LWDEBUGG(1, lwline_as_lwgeom(scrolled), "Closed input became non closed");
        }
      }
      else {
        LWDEBUGG(1, noded, "Diff-Xset Unioned cannot be scrolled");
      }
    }}
 
 
  }}
 
 
  /* 2.4. Split by pre-existing nodes
   *
   * Pre-existing nodes are isolated nodes AND endpoints
   * of intersecting edges
   */
  if ( nearbyedgecount )
  {
    nearbycount += nearbyedgecount * 2; /* make space for endpoints */
    nearby = lwrealloc(nearby, nearbycount * sizeof(LWGEOM *));
    for (int i=0; i<nearbyedgecount; i++)
    {
      LWLINE *edge = lwgeom_as_lwline(nearby[i]);
      LWPOINT *startNode = lwline_get_lwpoint(edge, 0);
      LWPOINT *endNode = lwline_get_lwpoint(edge, edge->points->npoints-1);
      /* TODO: only add if within distance to noded AND if not duplicated */
      nearby[nearbyindex++] = lwpoint_as_lwgeom(startNode);
      nearbynodecount++;
      nearby[nearbyindex++] = lwpoint_as_lwgeom(endNode);
      nearbynodecount++;
    }
  }
  if ( nearbynodecount )
  {
    col = lwcollection_construct(MULTIPOINTTYPE, topo->srid,
                             NULL, nearbynodecount,
                             nearby + nearbyedgecount);
    LWGEOM *inodes = lwcollection_as_lwgeom(col);
    /* TODO: use lwgeom_split of lwgeom_union ... */
    tmp = _lwt_split_by_nodes(noded, inodes);
    lwgeom_free(noded);
    noded = tmp;
    LWDEBUGG(1, noded, "Node-split");
    /* will not release the geoms array */
    lwcollection_release(col);
  }
 
 
  LWDEBUG(1, "Freeing up nearby elements");
 
  /* TODO: free up endpoints of nearbyedges */
  if ( nearby ) lwfree(nearby);
  if ( nodes ) _lwt_release_nodes(nodes, numnodes);
  if ( edges ) _lwt_release_edges(edges, numedges);
 
  LWDEBUGG(2, noded, "Finally-noded");
 
  /* 3. For each (now-noded) segment, insert an edge */
  col = lwgeom_as_lwcollection(noded);
  if ( col )
  {
    LWDEBUG(1, "Noded line was a collection");
    geoms = col->geoms;
    ngeoms = col->ngeoms;
  }
  else
  {
    LWDEBUG(1, "Noded line was a single geom");
    geomsbuf[0] = noded;
    geoms = geomsbuf;
    ngeoms = 1;
  }
 
  LWDEBUGF(1, "Line was split into %d edges", ngeoms);
 
  /* TODO: refactor to first add all nodes (re-snapping edges if
   * needed) and then check all edges for existing already
   * ( so to save a DB scan for each edge to be added )
   */
  ids = lwalloc(sizeof(LWT_ELEMID)*ngeoms);
  num = 0;
  for ( i=0; i<ngeoms; ++i )
  {
    int edgeNewEdges;
    LWT_ELEMID id;
    LWGEOM *g = geoms[i];
    g->srid = noded->srid;
 
#if POSTGIS_DEBUG_LEVEL > 0
    {
      size_t sz;
      char *wkt1 = lwgeom_to_wkt(g, WKT_EXTENDED, 15, &sz);
      LWDEBUGF(1, "Component %llu of split line is: %s", i, wkt1);
      lwfree(wkt1);
    }
#endif
 
    forward = -1; /* will be set to either 0 or 1 if the edge already existed */
    id = _lwt_AddLineEdge( topo, lwgeom_as_lwline(g), tol, handleFaceSplit, &forward, &edgeNewEdges );
    num_new_edges += edgeNewEdges;
    /* if forward is still == -1 this was NOT an existing edge ? */
    if ( forward == -1 )
    {
      ++num_new_edges;
    }
 
    LWDEBUGF(1, "_lwt_AddLineEdge returned %" LWTFMT_ELEMID
      " (forward ? %d), reported to create %d new edges (total new edges: %d)",
      id, forward, edgeNewEdges, num_new_edges);
    if ( id < 0 )
    {
      lwgeom_free(noded);
      lwfree(ids);
      return NULL;
    }
 
    if ( maxNewEdges >= 0 && num_new_edges > maxNewEdges )
    {
      lwgeom_free(noded);
      lwfree(ids);
      lwerror("Adding line to topology requires creating more edges than the requested limit of %d", maxNewEdges);
      return NULL;
    }
 
    if ( ! id )
    {
      LWDEBUGF(1, "Component %llu of split line collapsed", i);
      continue;
    }
 
    LWDEBUGF(1, "Component %llu of split line is %s edge %" LWTFMT_ELEMID,
                  i, forward ? "forward" : "backward", id);
    ids[num++] = forward ? id : -id; /* TODO: skip duplicates */
  }
 
  LWDEBUGG(2, noded, "Noded before free");
  lwgeom_free(noded);
 
  /* TODO: XXX remove duplicated ids if not done before */
 
  *nedges = num;
  return ids;
}

References _lwt_AddLineEdge(), _LWT_MINTOLERANCE, _lwt_release_edges(), _lwt_release_nodes(), _lwt_split_by_nodes(), _lwt_toposnap(), COLLECTIONTYPE, LWT_ISO_NODE::containing_face, gbox_expand(), LWT_ISO_NODE::geom, LWT_ISO_EDGE::geom, LWCOLLECTION::geoms, getPoint4d_p(), LW_ON_INTERRUPT, lwalloc(), lwcollection_as_lwgeom(), lwcollection_construct(), lwcollection_release(), LWDEBUG, LWDEBUGF, LWDEBUGG, lwerror(), lwfree(), LWGEOM2GEOS(), lwgeom_as_lwcollection(), lwgeom_as_lwline(), lwgeom_difference(), lwgeom_free(), lwgeom_geos_errmsg, lwgeom_get_bbox(), lwgeom_intersection(), lwgeom_linemerge(), lwgeom_mindistance2d(), lwgeom_node(), lwgeom_to_wkt(), lwgeom_unaryunion(), lwgeom_union(), lwline_as_lwgeom(), lwline_get_lwpoint(), lwline_is_closed(), lwline_is_empty(), lwline_remove_repeated_points(), lwpoint_as_lwgeom(), lwrealloc(), lwt_be_getEdgeWithinBox2D(), lwt_be_getNodeWithinBox2D(), LWT_COL_EDGE_ALL, LWT_COL_NODE_ALL, LWTFMT_ELEMID, MULTIPOINTTYPE, LWCOLLECTION::ngeoms, LWT_ISO_NODE::node_id, POINTARRAY::npoints, PGTOPO_BE_ERROR, LWLINE::points, ptarray_scroll_in_place(), LWGEOM::srid, LWLINE::srid, LWT_TOPOLOGY_T::srid, WKT_EXTENDED, POINT4D::x, GBOX::xmax, GBOX::xmin, POINT4D::y, GBOX::ymax, and GBOX::ymin.

Referenced by lwt_AddLine(), and lwt_AddLineNoFace().

Here is the call graph for this function:

Here is the caller graph for this function: