PostGIS  2.2.7dev-r@@SVN_REVISION@@
LWT_ELEMID* lwt_AddLine ( LWT_TOPOLOGY topo,
LWLINE line,
double  tol,
int *  nedges 
)

Adds a linestring to the topology.

The given line will snap to existing nodes or edges within given tolerance. Existing edges or faces may be split by the line.

Parameters
topothe topology to operate on
linethe line to add
tolsnap tolerance, the topology tolerance will be used if 0
nedgesoutput parameter, will be set to number of edges the line was split into, or -1 on error (liblwgeom error handler will be invoked with error message)
Returns
an array of <nedges> edge identifiers that sewed togheter will build up the input linestring (after snapping). Caller will need to free the array using lwfree(), if not null.

Definition at line 5590 of file lwgeom_topo.c.

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, 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(), lwt_be_getEdgeWithinBox2D(), lwt_be_getNodeWithinBox2D(), lwt_be_lastErrorMessage(), LWT_COL_EDGE_ALL, LWT_COL_NODE_ALL, LWTFMT_ELEMID, MULTIPOINTTYPE, LWCOLLECTION::ngeoms, LWT_TOPOLOGY_T::srid, LWGEOM::srid, LWLINE::srid, WKT_EXTENDED, GBOX::xmax, GBOX::xmin, GBOX::ymax, and GBOX::ymin.

Referenced by lwt_AddPolygon().

5591 {
5592  LWGEOM *geomsbuf[1];
5593  LWGEOM **geoms;
5594  int ngeoms;
5595  LWGEOM *noded, *tmp;
5596  LWCOLLECTION *col;
5597  LWT_ELEMID *ids;
5598  LWT_ISO_EDGE *edges;
5599  LWT_ISO_NODE *nodes;
5600  int num;
5601  int i;
5602  GBOX qbox;
5603 
5604  *nedges = -1; /* error condition, by default */
5605 
5606  /* Get tolerance, if 0 was given */
5607  if ( ! tol ) tol = _LWT_MINTOLERANCE( topo, (LWGEOM*)line );
5608  LWDEBUGF(1, "Working tolerance:%.15g", tol);
5609  LWDEBUGF(1, "Input line has srid=%d", line->srid);
5610 
5611  /* Remove consecutive vertices below given tolerance upfront */
5612  if ( tol )
5613  {{
5615  tmp = lwline_as_lwgeom(clean); /* NOTE: might collapse to non-simple */
5616  LWDEBUGG(1, tmp, "Repeated-point removed");
5617  }} else tmp=(LWGEOM*)line;
5618 
5619  /* 1. Self-node */
5620  noded = lwgeom_node((LWGEOM*)tmp);
5621  if ( tmp != (LWGEOM*)line ) lwgeom_free(tmp);
5622  if ( ! noded ) return NULL; /* should have called lwerror already */
5623  LWDEBUGG(1, noded, "Noded");
5624 
5625  qbox = *lwgeom_get_bbox( lwline_as_lwgeom(line) );
5626  LWDEBUGF(1, "Line BOX is %.15g %.15g, %.15g %.15g", qbox.xmin, qbox.ymin,
5627  qbox.xmax, qbox.ymax);
5628  gbox_expand(&qbox, tol);
5629  LWDEBUGF(1, "BOX expanded by %g is %.15g %.15g, %.15g %.15g",
5630  tol, qbox.xmin, qbox.ymin, qbox.xmax, qbox.ymax);
5631 
5632  /* 2. Node to edges falling within tol distance */
5633  edges = lwt_be_getEdgeWithinBox2D( topo, &qbox, &num, LWT_COL_EDGE_ALL, 0 );
5634  if ( num == -1 )
5635  {
5636  lwgeom_free(noded);
5637  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
5638  return NULL;
5639  }
5640  LWDEBUGF(1, "Line bbox intersects %d edges bboxes", num);
5641  if ( num )
5642  {{
5643  /* collect those whose distance from us is < tol */
5644  LWGEOM **nearby = lwalloc(sizeof(LWGEOM *)*num);
5645  int nn=0;
5646  for (i=0; i<num; ++i)
5647  {
5648  LWT_ISO_EDGE *e = &(edges[i]);
5649  LWGEOM *g = lwline_as_lwgeom(e->geom);
5650  double dist = lwgeom_mindistance2d(g, noded);
5651  if ( dist >= tol ) continue; /* must be closer than tolerated */
5652  nearby[nn++] = g;
5653  }
5654  if ( nn )
5655  {{
5656  LWCOLLECTION *col;
5657  LWGEOM *iedges; /* just an alias for col */
5658  LWGEOM *snapped;
5659  LWGEOM *set1, *set2;
5660 
5661  LWDEBUGF(1, "Line intersects %d edges", nn);
5662 
5664  NULL, nn, nearby);
5665  iedges = lwcollection_as_lwgeom(col);
5666  LWDEBUGG(1, iedges, "Collected edges");
5667  LWDEBUGF(1, "Snapping noded, with srid=%d "
5668  "to interesecting edges, with srid=%d",
5669  noded->srid, iedges->srid);
5670  snapped = _lwt_toposnap(noded, iedges, tol);
5671  lwgeom_free(noded);
5672  LWDEBUGG(1, snapped, "Snapped");
5673  LWDEBUGF(1, "Diffing snapped, with srid=%d "
5674  "and interesecting edges, with srid=%d",
5675  snapped->srid, iedges->srid);
5676  noded = lwgeom_difference(snapped, iedges);
5677  LWDEBUGG(1, noded, "Differenced");
5678  LWDEBUGF(1, "Intersecting snapped, with srid=%d "
5679  "and interesecting edges, with srid=%d",
5680  snapped->srid, iedges->srid);
5681  set1 = lwgeom_intersection(snapped, iedges);
5682  LWDEBUGG(1, set1, "Intersected");
5683  lwgeom_free(snapped);
5684  LWDEBUGF(1, "Linemerging set1, with srid=%d", set1->srid);
5685  set2 = lwgeom_linemerge(set1);
5686  LWDEBUGG(1, set2, "Linemerged");
5687  LWDEBUGG(1, noded, "Noded");
5688  lwgeom_free(set1);
5689  LWDEBUGF(1, "Unioning noded, with srid=%d "
5690  "and set2, with srid=%d", noded->srid, set2->srid);
5691  set1 = lwgeom_union(noded, set2);
5692  lwgeom_free(set2);
5693  lwgeom_free(noded);
5694  noded = set1;
5695  LWDEBUGG(1, set1, "Unioned");
5696 
5697  /* will not release the geoms array */
5698  lwcollection_release(col);
5699  }}
5700  lwfree(nearby);
5701  _lwt_release_edges(edges, num);
5702  }}
5703 
5704  /* 2.1. Node with existing nodes within tol
5705  * TODO: check if we should be only considering _isolated_ nodes! */
5706  nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &num, LWT_COL_NODE_ALL, 0 );
5707  if ( num == -1 )
5708  {
5709  lwgeom_free(noded);
5710  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
5711  return NULL;
5712  }
5713  LWDEBUGF(1, "Line bbox intersects %d nodes bboxes", num);
5714  if ( num )
5715  {{
5716  /* collect those whose distance from us is < tol */
5717  LWGEOM **nearby = lwalloc(sizeof(LWGEOM *)*num);
5718  int nn=0;
5719  for (i=0; i<num; ++i)
5720  {
5721  LWT_ISO_NODE *n = &(nodes[i]);
5722  LWGEOM *g = lwpoint_as_lwgeom(n->geom);
5723  double dist = lwgeom_mindistance2d(g, noded);
5724  if ( dist >= tol ) continue; /* must be closer than tolerated */
5725  nearby[nn++] = g;
5726  }
5727  if ( nn )
5728  {{
5729  LWCOLLECTION *col;
5730  LWGEOM *inodes; /* just an alias for col */
5731  LWGEOM *tmp;
5732 
5733  LWDEBUGF(1, "Line intersects %d nodes", nn);
5734 
5736  NULL, nn, nearby);
5737  inodes = lwcollection_as_lwgeom(col);
5738 
5739  LWDEBUGG(1, inodes, "Collected nodes");
5740 
5741  /* TODO: consider snapping once against all elements
5742  * (rather than once with edges and once with nodes) */
5743  tmp = _lwt_toposnap(noded, inodes, tol);
5744  lwgeom_free(noded);
5745  noded = tmp;
5746  LWDEBUGG(1, noded, "Node-snapped");
5747 
5748  tmp = _lwt_split_by_nodes(noded, inodes);
5749  /* lwgeom_split(noded, inodes); */
5750  lwgeom_free(noded);
5751  noded = tmp;
5752  LWDEBUGG(1, noded, "Node-split");
5753 
5754  /* will not release the geoms array */
5755  lwcollection_release(col);
5756 
5757  /*
5758  -- re-node to account for ST_Snap introduced self-intersections
5759  -- See http://trac.osgeo.org/postgis/ticket/1714
5760  -- TODO: consider running UnaryUnion once after all noding
5761  */
5762  tmp = lwgeom_unaryunion(noded);
5763  lwgeom_free(noded);
5764  noded = tmp;
5765  LWDEBUGG(1, noded, "Unary-unioned");
5766 
5767  }}
5768  lwfree(nearby);
5769  _lwt_release_nodes(nodes, num);
5770  }}
5771 
5772  LWDEBUGG(1, noded, "Finally-noded");
5773 
5774  /* 3. For each (now-noded) segment, insert an edge */
5775  col = lwgeom_as_lwcollection(noded);
5776  if ( col )
5777  {
5778  LWDEBUG(1, "Noded line was a collection");
5779  geoms = col->geoms;
5780  ngeoms = col->ngeoms;
5781  }
5782  else
5783  {
5784  LWDEBUG(1, "Noded line was a single geom");
5785  geomsbuf[0] = noded;
5786  geoms = geomsbuf;
5787  ngeoms = 1;
5788  }
5789 
5790  LWDEBUGF(1, "Line was split into %d edges", ngeoms);
5791 
5792  /* TODO: refactor to first add all nodes (re-snapping edges if
5793  * needed) and then check all edges for existing already
5794  * ( so to save a DB scan for each edge to be added )
5795  */
5796  ids = lwalloc(sizeof(LWT_ELEMID)*ngeoms);
5797  num = 0;
5798  for ( i=0; i<ngeoms; ++i )
5799  {
5800  LWT_ELEMID id;
5801  LWGEOM *g = geoms[i];
5802  g->srid = noded->srid;
5803 
5804 #if POSTGIS_DEBUG_LEVEL > 0
5805  {
5806  size_t sz;
5807  char *wkt1 = lwgeom_to_wkt(g, WKT_EXTENDED, 15, &sz);
5808  LWDEBUGF(1, "Component %d of split line is: %s", i, wkt1);
5809  lwfree(wkt1);
5810  }
5811 #endif
5812 
5813  id = _lwt_AddLineEdge( topo, lwgeom_as_lwline(g), tol );
5814  LWDEBUGF(1, "_lwt_AddLineEdge returned %" LWTFMT_ELEMID, id);
5815  if ( id < 0 )
5816  {
5817  lwgeom_free(noded);
5818  lwfree(ids);
5819  return NULL;
5820  }
5821  if ( ! id )
5822  {
5823  LWDEBUGF(1, "Component %d of split line collapsed", i);
5824  continue;
5825  }
5826 
5827  LWDEBUGF(1, "Component %d of split line is edge %" LWTFMT_ELEMID,
5828  i, id);
5829  ids[num++] = id; /* TODO: skip duplicates */
5830  }
5831 
5832  LWDEBUGG(1, noded, "Noded before free");
5833  lwgeom_free(noded);
5834 
5835  /* TODO: XXX remove duplicated ids if not done before */
5836 
5837  *nedges = num;
5838  return ids;
5839 }
static void _lwt_release_nodes(LWT_ISO_NODE *nodes, int num_nodes)
Definition: lwgeom_topo.c:481
#define LWDEBUGG(level, geom, msg)
Definition: lwgeom_topo.c:40
LWCOLLECTION * lwcollection_construct(uint8_t type, int srid, GBOX *bbox, uint32_t ngeoms, LWGEOM **geoms)
Definition: lwcollection.c:30
LWPOINT * geom
char * lwgeom_to_wkt(const LWGEOM *geom, uint8_t variant, int precision, size_t *size_out)
WKT emitter function.
Definition: lwout_wkt.c:655
void lwfree(void *mem)
Definition: lwutil.c:214
void gbox_expand(GBOX *g, double d)
Move the box minimums down and the maximums up by the distance provided.
Definition: g_box.c:93
double xmax
Definition: liblwgeom.h:277
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1050
#define MULTIPOINTTYPE
Definition: liblwgeom.h:73
LWLINE * geom
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:50
int32_t srid
Definition: liblwgeom.h:405
#define _LWT_MINTOLERANCE(topo, geom)
Definition: lwgeom_topo.c:4969
int32_t srid
Definition: liblwgeom.h:383
static LWT_ELEMID _lwt_AddLineEdge(LWT_TOPOLOGY *topo, LWLINE *edge, double tol)
Definition: lwgeom_topo.c:5396
double ymin
Definition: liblwgeom.h:278
LWGEOM * lwline_remove_repeated_points(LWLINE *in, double tolerance)
Definition: lwline.c:427
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:249
double xmin
Definition: liblwgeom.h:276
LWGEOM * lwgeom_node(const LWGEOM *lwgeom_in)
const LWT_BE_IFACE * be_iface
LWGEOM ** geoms
Definition: liblwgeom.h:493
LWGEOM * lwgeom_intersection(const LWGEOM *geom1, const LWGEOM *geom2)
const GBOX * lwgeom_get_bbox(const LWGEOM *lwgeom)
Get a non-empty geometry bounding box, computing and caching it if not already there.
Definition: lwgeom.c:640
LWGEOM * lwgeom_difference(const LWGEOM *geom1, const LWGEOM *geom2)
#define LWT_COL_EDGE_ALL
double ymax
Definition: liblwgeom.h:279
LWLINE * lwgeom_as_lwline(const LWGEOM *lwgeom)
Definition: lwgeom.c:89
void lwcollection_release(LWCOLLECTION *lwcollection)
Definition: lwcollection.c:23
#define WKT_EXTENDED
Definition: liblwgeom.h:1941
#define LWT_COL_NODE_ALL
LWGEOM * lwgeom_unaryunion(const LWGEOM *geom1)
LWCOLLECTION * lwgeom_as_lwcollection(const LWGEOM *lwgeom)
Definition: lwgeom.c:143
static LWGEOM * _lwt_split_by_nodes(const LWGEOM *g, const LWGEOM *nodes)
Definition: lwgeom_topo.c:5568
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:471
double lwgeom_mindistance2d(const LWGEOM *lw1, const LWGEOM *lw2)
Function initialazing min distance calculation.
Definition: measures.c:188
LWGEOM * lwpoint_as_lwgeom(const LWPOINT *obj)
Definition: lwgeom.c:254
LWT_INT64 LWT_ELEMID
Identifier of topology element.
LWGEOM * lwgeom_union(const LWGEOM *geom1, const LWGEOM *geom2)
void * lwalloc(size_t size)
Definition: lwutil.c:199
static LWGEOM * _lwt_toposnap(LWGEOM *src, LWGEOM *tgt, double tol)
Definition: lwgeom_topo.c:424
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:55
static LWT_ISO_EDGE * lwt_be_getEdgeWithinBox2D(const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
Definition: lwgeom_topo.c:183
static LWT_ISO_NODE * lwt_be_getNodeWithinBox2D(const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
Definition: lwgeom_topo.c:175
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 COLLECTIONTYPE
Definition: liblwgeom.h:76
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:36
LWGEOM * lwgeom_linemerge(const LWGEOM *geom1)
LWGEOM * lwcollection_as_lwgeom(const LWCOLLECTION *obj)
Definition: lwgeom.c:219

Here is the call graph for this function:

Here is the caller graph for this function: