PostGIS  2.3.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 5620 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, 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(), 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, LWT_TOPOLOGY_T::srid, LWGEOM::srid, LWLINE::srid, WKT_EXTENDED, GBOX::xmax, GBOX::xmin, GBOX::ymax, and GBOX::ymin.

Referenced by lwt_AddPolygon().

5621 {
5622  LWGEOM *geomsbuf[1];
5623  LWGEOM **geoms;
5624  int ngeoms;
5625  LWGEOM *noded, *tmp;
5626  LWCOLLECTION *col;
5627  LWT_ELEMID *ids;
5628  LWT_ISO_EDGE *edges;
5629  LWT_ISO_NODE *nodes;
5630  int num;
5631  int i;
5632  GBOX qbox;
5633 
5634  *nedges = -1; /* error condition, by default */
5635 
5636  /* Get tolerance, if 0 was given */
5637  if ( ! tol ) tol = _LWT_MINTOLERANCE( topo, (LWGEOM*)line );
5638  LWDEBUGF(1, "Working tolerance:%.15g", tol);
5639  LWDEBUGF(1, "Input line has srid=%d", line->srid);
5640 
5641  /* Remove consecutive vertices below given tolerance upfront */
5642  if ( tol )
5643  {{
5645  tmp = lwline_as_lwgeom(clean); /* NOTE: might collapse to non-simple */
5646  LWDEBUGG(1, tmp, "Repeated-point removed");
5647  }} else tmp=(LWGEOM*)line;
5648 
5649  /* 1. Self-node */
5650  noded = lwgeom_node((LWGEOM*)tmp);
5651  if ( tmp != (LWGEOM*)line ) lwgeom_free(tmp);
5652  if ( ! noded ) return NULL; /* should have called lwerror already */
5653  LWDEBUGG(1, noded, "Noded");
5654 
5655  qbox = *lwgeom_get_bbox( lwline_as_lwgeom(line) );
5656  LWDEBUGF(1, "Line BOX is %.15g %.15g, %.15g %.15g", qbox.xmin, qbox.ymin,
5657  qbox.xmax, qbox.ymax);
5658  gbox_expand(&qbox, tol);
5659  LWDEBUGF(1, "BOX expanded by %g is %.15g %.15g, %.15g %.15g",
5660  tol, qbox.xmin, qbox.ymin, qbox.xmax, qbox.ymax);
5661 
5662  /* 2. Node to edges falling within tol distance */
5663  edges = lwt_be_getEdgeWithinBox2D( topo, &qbox, &num, LWT_COL_EDGE_ALL, 0 );
5664  if ( num == -1 )
5665  {
5666  lwgeom_free(noded);
5667  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
5668  return NULL;
5669  }
5670  LWDEBUGF(1, "Line has %d points, its bbox intersects %d edges bboxes", line->points->npoints, num);
5671  if ( num )
5672  {{
5673  /* collect those whose distance from us is < tol */
5674  LWGEOM **nearby = lwalloc(sizeof(LWGEOM *)*num);
5675  int nn=0;
5676  for (i=0; i<num; ++i)
5677  {
5678  LW_ON_INTERRUPT(return NULL);
5679  LWT_ISO_EDGE *e = &(edges[i]);
5680  LWGEOM *g = lwline_as_lwgeom(e->geom);
5681  LWDEBUGF(2, "Computing distance from edge %d having %d points", i, e->geom->points->npoints);
5682  double dist = lwgeom_mindistance2d(g, noded);
5683  if ( dist >= tol ) continue; /* must be closer than tolerated */
5684  nearby[nn++] = g;
5685  }
5686  LWDEBUGF(2, "Found %d lines closer than tolerance (%g)", nn, tol);
5687  if ( nn )
5688  {{
5689  LWCOLLECTION *col;
5690  LWGEOM *iedges; /* just an alias for col */
5691  LWGEOM *snapped;
5692  LWGEOM *set1, *set2;
5693 
5694  LWDEBUGF(1, "Line intersects %d edges", nn);
5695 
5697  NULL, nn, nearby);
5698  iedges = lwcollection_as_lwgeom(col);
5699  LWDEBUGG(1, iedges, "Collected edges");
5700  LWDEBUGF(1, "Snapping noded, with srid=%d "
5701  "to interesecting edges, with srid=%d",
5702  noded->srid, iedges->srid);
5703  snapped = _lwt_toposnap(noded, iedges, tol);
5704  lwgeom_free(noded);
5705  LWDEBUGG(1, snapped, "Snapped");
5706  LWDEBUGF(1, "Diffing snapped, with srid=%d "
5707  "and interesecting edges, with srid=%d",
5708  snapped->srid, iedges->srid);
5709  noded = lwgeom_difference(snapped, iedges);
5710  LWDEBUGG(1, noded, "Differenced");
5711  LWDEBUGF(1, "Intersecting snapped, with srid=%d "
5712  "and interesecting edges, with srid=%d",
5713  snapped->srid, iedges->srid);
5714  set1 = lwgeom_intersection(snapped, iedges);
5715  LWDEBUGG(1, set1, "Intersected");
5716  lwgeom_free(snapped);
5717  LWDEBUGF(1, "Linemerging set1, with srid=%d", set1->srid);
5718  set2 = lwgeom_linemerge(set1);
5719  LWDEBUGG(1, set2, "Linemerged");
5720  LWDEBUGG(1, noded, "Noded");
5721  lwgeom_free(set1);
5722  LWDEBUGF(1, "Unioning noded, with srid=%d "
5723  "and set2, with srid=%d", noded->srid, set2->srid);
5724  set1 = lwgeom_union(noded, set2);
5725  lwgeom_free(set2);
5726  lwgeom_free(noded);
5727  noded = set1;
5728  LWDEBUGG(1, set1, "Unioned");
5729 
5730  /* will not release the geoms array */
5731  lwcollection_release(col);
5732  }}
5733  lwfree(nearby);
5734  _lwt_release_edges(edges, num);
5735  }}
5736 
5737  /* 2.1. Node with existing nodes within tol
5738  * TODO: check if we should be only considering _isolated_ nodes! */
5739  nodes = lwt_be_getNodeWithinBox2D( topo, &qbox, &num, LWT_COL_NODE_ALL, 0 );
5740  if ( num == -1 )
5741  {
5742  lwgeom_free(noded);
5743  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
5744  return NULL;
5745  }
5746  LWDEBUGF(1, "Line bbox intersects %d nodes bboxes", num);
5747  if ( num )
5748  {{
5749  /* collect those whose distance from us is < tol */
5750  LWGEOM **nearby = lwalloc(sizeof(LWGEOM *)*num);
5751  int nn=0;
5752  for (i=0; i<num; ++i)
5753  {
5754  LWT_ISO_NODE *n = &(nodes[i]);
5755  LWGEOM *g = lwpoint_as_lwgeom(n->geom);
5756  double dist = lwgeom_mindistance2d(g, noded);
5757  if ( dist >= tol ) continue; /* must be closer than tolerated */
5758  nearby[nn++] = g;
5759  }
5760  if ( nn )
5761  {{
5762  LWCOLLECTION *col;
5763  LWGEOM *inodes; /* just an alias for col */
5764  LWGEOM *tmp;
5765 
5766  LWDEBUGF(1, "Line intersects %d nodes", nn);
5767 
5769  NULL, nn, nearby);
5770  inodes = lwcollection_as_lwgeom(col);
5771 
5772  LWDEBUGG(1, inodes, "Collected nodes");
5773 
5774  /* TODO: consider snapping once against all elements
5775  * (rather than once with edges and once with nodes) */
5776  tmp = _lwt_toposnap(noded, inodes, tol);
5777  lwgeom_free(noded);
5778  noded = tmp;
5779  LWDEBUGG(1, noded, "Node-snapped");
5780 
5781  tmp = _lwt_split_by_nodes(noded, inodes);
5782  /* lwgeom_split(noded, inodes); */
5783  lwgeom_free(noded);
5784  noded = tmp;
5785  LWDEBUGG(1, noded, "Node-split");
5786 
5787  /* will not release the geoms array */
5788  lwcollection_release(col);
5789 
5790  /*
5791  -- re-node to account for ST_Snap introduced self-intersections
5792  -- See http://trac.osgeo.org/postgis/ticket/1714
5793  -- TODO: consider running UnaryUnion once after all noding
5794  */
5795  tmp = lwgeom_unaryunion(noded);
5796  lwgeom_free(noded);
5797  noded = tmp;
5798  LWDEBUGG(1, noded, "Unary-unioned");
5799 
5800  }}
5801  lwfree(nearby);
5802  _lwt_release_nodes(nodes, num);
5803  }}
5804 
5805  LWDEBUGG(1, noded, "Finally-noded");
5806 
5807  /* 3. For each (now-noded) segment, insert an edge */
5808  col = lwgeom_as_lwcollection(noded);
5809  if ( col )
5810  {
5811  LWDEBUG(1, "Noded line was a collection");
5812  geoms = col->geoms;
5813  ngeoms = col->ngeoms;
5814  }
5815  else
5816  {
5817  LWDEBUG(1, "Noded line was a single geom");
5818  geomsbuf[0] = noded;
5819  geoms = geomsbuf;
5820  ngeoms = 1;
5821  }
5822 
5823  LWDEBUGF(1, "Line was split into %d edges", ngeoms);
5824 
5825  /* TODO: refactor to first add all nodes (re-snapping edges if
5826  * needed) and then check all edges for existing already
5827  * ( so to save a DB scan for each edge to be added )
5828  */
5829  ids = lwalloc(sizeof(LWT_ELEMID)*ngeoms);
5830  num = 0;
5831  for ( i=0; i<ngeoms; ++i )
5832  {
5833  LWT_ELEMID id;
5834  LWGEOM *g = geoms[i];
5835  g->srid = noded->srid;
5836 
5837 #if POSTGIS_DEBUG_LEVEL > 0
5838  {
5839  size_t sz;
5840  char *wkt1 = lwgeom_to_wkt(g, WKT_EXTENDED, 15, &sz);
5841  LWDEBUGF(1, "Component %d of split line is: %s", i, wkt1);
5842  lwfree(wkt1);
5843  }
5844 #endif
5845 
5846  id = _lwt_AddLineEdge( topo, lwgeom_as_lwline(g), tol );
5847  LWDEBUGF(1, "_lwt_AddLineEdge returned %" LWTFMT_ELEMID, id);
5848  if ( id < 0 )
5849  {
5850  lwgeom_free(noded);
5851  lwfree(ids);
5852  return NULL;
5853  }
5854  if ( ! id )
5855  {
5856  LWDEBUGF(1, "Component %d of split line collapsed", i);
5857  continue;
5858  }
5859 
5860  LWDEBUGF(1, "Component %d of split line is edge %" LWTFMT_ELEMID,
5861  i, id);
5862  ids[num++] = id; /* TODO: skip duplicates */
5863  }
5864 
5865  LWDEBUGG(1, noded, "Noded before free");
5866  lwgeom_free(noded);
5867 
5868  /* TODO: XXX remove duplicated ids if not done before */
5869 
5870  *nedges = num;
5871  return ids;
5872 }
static void _lwt_release_nodes(LWT_ISO_NODE *nodes, int num_nodes)
Definition: lwgeom_topo.c:477
LWCOLLECTION * lwcollection_construct(uint8_t type, int srid, GBOX *bbox, uint32_t ngeoms, LWGEOM **geoms)
Definition: lwcollection.c:43
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:669
void lwfree(void *mem)
Definition: lwutil.c:242
int npoints
Definition: liblwgeom.h:370
void gbox_expand(GBOX *g, double d)
Move the box minimums down and the maximums up by the distance provided.
Definition: g_box.c:108
double xmax
Definition: liblwgeom.h:292
void lwgeom_free(LWGEOM *geom)
Definition: lwgeom.c:1063
#define MULTIPOINTTYPE
Definition: liblwgeom.h:87
LWLINE * geom
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#define LW_ON_INTERRUPT(x)
int32_t srid
Definition: liblwgeom.h:420
#define _LWT_MINTOLERANCE(topo, geom)
Definition: lwgeom_topo.c:4999
int32_t srid
Definition: liblwgeom.h:398
static LWT_ELEMID _lwt_AddLineEdge(LWT_TOPOLOGY *topo, LWLINE *edge, double tol)
Definition: lwgeom_topo.c:5426
double ymin
Definition: liblwgeom.h:293
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:262
double xmin
Definition: liblwgeom.h:291
LWGEOM * lwgeom_node(const LWGEOM *lwgeom_in)
const LWT_BE_IFACE * be_iface
LWGEOM ** geoms
Definition: liblwgeom.h:508
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:653
LWGEOM * lwgeom_difference(const LWGEOM *geom1, const LWGEOM *geom2)
#define LWT_COL_EDGE_ALL
double ymax
Definition: liblwgeom.h:294
LWLINE * lwgeom_as_lwline(const LWGEOM *lwgeom)
Definition: lwgeom.c:102
#define LWDEBUGG(level, geom, msg)
Definition: lwgeom_log.h:93
void lwcollection_release(LWCOLLECTION *lwcollection)
Definition: lwcollection.c:36
LWGEOM * lwline_remove_repeated_points(const LWLINE *in, double tolerance)
Definition: lwline.c:456
#define WKT_EXTENDED
Definition: liblwgeom.h:2057
#define LWT_COL_NODE_ALL
LWGEOM * lwgeom_unaryunion(const LWGEOM *geom1)
LWCOLLECTION * lwgeom_as_lwcollection(const LWGEOM *lwgeom)
Definition: lwgeom.c:156
static LWGEOM * _lwt_split_by_nodes(const LWGEOM *g, const LWGEOM *nodes)
Definition: lwgeom_topo.c:5598
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:467
double lwgeom_mindistance2d(const LWGEOM *lw1, const LWGEOM *lw2)
Function initialazing min distance calculation.
Definition: measures.c:202
LWGEOM * lwpoint_as_lwgeom(const LWPOINT *obj)
Definition: lwgeom.c:267
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:227
static LWGEOM * _lwt_toposnap(LWGEOM *src, LWGEOM *tgt, double tol)
Definition: lwgeom_topo.c:420
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
static LWT_ISO_EDGE * lwt_be_getEdgeWithinBox2D(const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
Definition: lwgeom_topo.c:179
static LWT_ISO_NODE * lwt_be_getNodeWithinBox2D(const LWT_TOPOLOGY *topo, const GBOX *box, int *numelems, int fields, int limit)
Definition: lwgeom_topo.c:171
const char * lwt_be_lastErrorMessage(const LWT_BE_IFACE *be)
Definition: lwgeom_topo.c:120
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:102
#define COLLECTIONTYPE
Definition: liblwgeom.h:90
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:44
LWGEOM * lwgeom_linemerge(const LWGEOM *geom1)
POINTARRAY * points
Definition: liblwgeom.h:421
LWGEOM * lwcollection_as_lwgeom(const LWCOLLECTION *obj)
Definition: lwgeom.c:232

Here is the call graph for this function:

Here is the caller graph for this function: