_lwt_AddLine()

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

static

Definition at line 5517 of file lwgeom_topo.c.

{
  LWGEOM *geomsbuf[1];
  LWGEOM **geoms;
  int ngeoms;
  LWGEOM *noded, *tmp;
  LWCOLLECTION *col;
  LWT_ELEMID *ids;
  LWT_ISO_EDGE *edges;
  LWT_ISO_NODE *nodes;
  int num, numedges=0, numnodes=0;
  int i;
  GBOX qbox;
 
  *nedges = -1; /* error condition, by default */
 
  /* Get tolerance, if 0 was given */
  if ( ! tol ) 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. Node to edges falling within tol distance */
  edges = lwt_be_getEdgeWithinBox2D( topo, &qbox, &numedges, LWT_COL_EDGE_ALL, 0 );
  if ( numedges == -1 )
  {
    lwgeom_free(noded);
    lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
    return NULL;
  }
  LWDEBUGF(1, "Line has %d points, its bbox intersects %d edges bboxes",
    line->points->npoints, numedges);
  if ( numedges )
  {{
    /* collect those whose distance from us is < tol */
    nearbycount += numedges;
    nearby = lwalloc(nearbycount * 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);
      LWDEBUGF(2, "Computing distance from edge %d having %d points", i, e->geom->points->npoints);
      double dist = lwgeom_mindistance2d(g, noded);
      /* must be closer than tolerated, unless distance is zero */
      if ( dist && dist >= tol ) continue;
      nearby[nearbyindex++] = g;
    }
    LWDEBUGF(2, "Found %d lines closer than tolerance (%g)", nearbyindex, tol);
    if ( nearbyindex )
    {{
      LWCOLLECTION *col;
      LWGEOM *iedges; /* just an alias for col */
      LWGEOM *snapped;
      LWGEOM *set1, *set2;
 
      LWDEBUGF(1, "Line intersects %d edges", nearbyindex);
 
      col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
                                   NULL, nearbyindex, nearby);
      iedges = lwcollection_as_lwgeom(col);
      LWDEBUGG(1, iedges, "Collected edges");
      LWDEBUGF(1, "Snapping noded, with srid=%d "
                  "to interesecting edges, with srid=%d",
                  noded->srid, iedges->srid);
      snapped = _lwt_toposnap(noded, iedges, tol);
      lwgeom_free(noded);
      LWDEBUGG(1, snapped, "Snapped");
      LWDEBUGF(1, "Diffing snapped, with srid=%d "
                  "and interesecting edges, with srid=%d",
                  snapped->srid, iedges->srid);
      noded = lwgeom_difference(snapped, iedges);
      LWDEBUGG(1, noded, "Differenced");
      LWDEBUGF(1, "Intersecting snapped, with srid=%d "
                  "and interesecting edges, with srid=%d",
                  snapped->srid, iedges->srid);
      set1 = lwgeom_intersection(snapped, iedges);
      LWDEBUGG(1, set1, "Intersected");
      lwgeom_free(snapped);
      LWDEBUGF(1, "Linemerging set1, with srid=%d", set1->srid);
      set2 = lwgeom_linemerge(set1);
      LWDEBUGG(1, set2, "Linemerged");
      LWDEBUGG(1, noded, "Noded");
      lwgeom_free(set1);
      LWDEBUGF(1, "Unioning noded, with srid=%d "
                  "and set2, with srid=%d", noded->srid, set2->srid);
      set1 = lwgeom_union(noded, set2);
      lwgeom_free(set2);
      lwgeom_free(noded);
      noded = set1;
      LWDEBUGG(1, set1, "Unioned");
 
      /* will not release the geoms array */
      lwcollection_release(col);
    }}
  }}
 
  /* 2.1. Node with existing nodes within tol
   * TODO: check if we should be only considering _isolated_ nodes! */
  nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &numnodes, LWT_COL_NODE_ALL, 0 );
  if ( numnodes == -1 )
  {
    lwgeom_free(noded);
    lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
    return NULL;
  }
  LWDEBUGF(1, "Line bbox intersects %d nodes bboxes", numnodes);
  int nearbyedgecount = nearbyindex;
  if ( numnodes )
  {{
    /* collect those whose distance from us is < tol */
    nearbycount = nearbyindex + 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]);
      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 ) continue;
      nearby[nearbyindex++] = g;
      ++nn;
    }
  }}
 
  LWDEBUGF(1, "Number of nearby elements is %d", nearbyindex);
 
  if ( numnodes )
  {{
    LWCOLLECTION *col;
    LWGEOM *elems;
 
    col = lwcollection_construct(COLLECTIONTYPE, topo->srid,
                                 NULL, nearbyindex, 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");
 
    /* will not release the geoms array */
    lwcollection_release(col);
 
    if ( numnodes )
    {{
      col = lwcollection_construct(MULTIPOINTTYPE, topo->srid,
                             NULL, nearbyindex-nearbyedgecount,
                             nearby + nearbyedgecount);
      LWGEOM *inodes = lwcollection_as_lwgeom(col);
      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);
    }}
 
    /*
    -- 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");
 
  }}
 
  LWDEBUG(1, "Freeing up nearby elements");
 
  if ( nearby ) lwfree(nearby);
  if ( nodes ) _lwt_release_nodes(nodes, numnodes);
  if ( edges ) _lwt_release_edges(edges, numedges);
 
  LWDEBUGG(1, 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 )
  {
    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 %d of split line is: %s", i, wkt1);
      lwfree(wkt1);
    }
#endif
 
    id = _lwt_AddLineEdge( topo, lwgeom_as_lwline(g), tol, handleFaceSplit );
    LWDEBUGF(1, "_lwt_AddLineEdge returned %" LWTFMT_ELEMID, id);
    if ( id < 0 )
    {
      lwgeom_free(noded);
      lwfree(ids);
      return NULL;
    }
    if ( ! id )
    {
      LWDEBUGF(1, "Component %d of split line collapsed", i);
      continue;
    }
 
    LWDEBUGF(1, "Component %d of split line is edge %" LWTFMT_ELEMID,
                  i, id);
    ids[num++] = id; /* TODO: skip duplicates */
  }
 
  LWDEBUGG(1, 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(), LWT_TOPOLOGY_T::be_iface, COLLECTIONTYPE, gbox_expand(), LWT_ISO_NODE::geom, LWT_ISO_EDGE::geom, LWCOLLECTION::geoms, LW_ON_INTERRUPT, lwalloc(), lwcollection_as_lwgeom(), lwcollection_construct(), lwcollection_release(), LWDEBUG, LWDEBUGF, LWDEBUGG, lwerror(), lwfree(), lwgeom_as_lwcollection(), lwgeom_as_lwline(), lwgeom_difference(), lwgeom_free(), lwgeom_get_bbox(), lwgeom_intersection(), lwgeom_linemerge(), lwgeom_mindistance2d(), lwgeom_node(), lwgeom_to_wkt(), lwgeom_unaryunion(), lwgeom_union(), lwline_as_lwgeom(), lwline_remove_repeated_points(), lwpoint_as_lwgeom(), lwrealloc(), lwt_be_getEdgeWithinBox2D(), lwt_be_getNodeWithinBox2D(), lwt_be_lastErrorMessage(), LWT_COL_EDGE_ALL, LWT_COL_NODE_ALL, LWTFMT_ELEMID, MULTIPOINTTYPE, LWCOLLECTION::ngeoms, POINTARRAY::npoints, LWLINE::points, LWGEOM::srid, LWLINE::srid, LWT_TOPOLOGY_T::srid, WKT_EXTENDED, GBOX::xmax, GBOX::xmin, 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: