PostGIS  2.5.1dev-r@@SVN_REVISION@@

◆ _lwt_AddFaceSplit()

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

Definition at line 1856 of file lwgeom_topo.c.

References _lwt_GetInteriorEdgePoint(), _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, LWT_ISO_NODE::geom, LWT_ISO_EDGE::geom, getPoint2d_cp(), LW_INSIDE, lwalloc(), LWDEBUG, LWDEBUGF, lwerror(), lwfree(), lwgeom_geos_errmsg, 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, LWPOINT::point, ptarray_contains_point(), ptarray_isccw(), and LWPOLY::rings.

Referenced by _lwt_AddEdge().

1859 {
1860  int numfaceedges, i, j;
1861  int newface_outside;
1862  int num_signed_edge_ids;
1863  LWT_ELEMID *signed_edge_ids;
1864  LWT_ISO_EDGE *edges;
1865  LWT_ISO_EDGE *forward_edges = NULL;
1866  int forward_edges_count = 0;
1867  LWT_ISO_EDGE *backward_edges = NULL;
1868  int backward_edges_count = 0;
1869 
1870  signed_edge_ids = lwt_be_getRingEdges(topo, sedge,
1871  &num_signed_edge_ids, 0);
1872  if ( ! signed_edge_ids ) {
1873  lwerror("Backend error (no ring edges for edge %" LWTFMT_ELEMID "): %s",
1874  sedge, lwt_be_lastErrorMessage(topo->be_iface));
1875  return -2;
1876  }
1877  LWDEBUGF(1, "getRingEdges returned %d edges", num_signed_edge_ids);
1878 
1879  /* You can't get to the other side of an edge forming a ring */
1880  for (i=0; i<num_signed_edge_ids; ++i) {
1881  if ( signed_edge_ids[i] == -sedge ) {
1882  /* No split here */
1883  LWDEBUG(1, "not a ring");
1884  lwfree( signed_edge_ids );
1885  return 0;
1886  }
1887  }
1888 
1889  LWDEBUGF(1, "Edge %" LWTFMT_ELEMID " split face %" LWTFMT_ELEMID " (mbr_only:%d)",
1890  sedge, face, mbr_only);
1891 
1892  /* Construct a polygon using edges of the ring */
1893  LWPOLY *shell = _lwt_MakeRingShell(topo, signed_edge_ids,
1894  num_signed_edge_ids);
1895  if ( ! shell ) {
1896  lwfree( signed_edge_ids );
1897  /* ring_edges should be NULL */
1898  lwerror("Could not create ring shell: %s", lwt_be_lastErrorMessage(topo->be_iface));
1899  return -2;
1900  }
1901  const POINTARRAY *pa = shell->rings[0];
1902 
1903  int isccw = ptarray_isccw(pa);
1904  LWDEBUGF(1, "Ring of edge %" LWTFMT_ELEMID " is %sclockwise",
1905  sedge, isccw ? "counter" : "");
1906  const GBOX* shellbox = lwgeom_get_bbox(lwpoly_as_lwgeom(shell));
1907 
1908  if ( face == 0 )
1909  {
1910  /* Edge split the universe face */
1911  if ( ! isccw )
1912  {
1913  lwpoly_free(shell);
1914  lwfree( signed_edge_ids );
1915  /* Face on the left side of this ring is the universe face.
1916  * Next call (for the other side) should create the split face
1917  */
1918  LWDEBUG(1, "The left face of this clockwise ring is the universe, "
1919  "won't create a new face there");
1920  return -1;
1921  }
1922  }
1923 
1924  if ( mbr_only && face != 0 )
1925  {
1926  if ( isccw )
1927  {{
1928  LWT_ISO_FACE updface;
1929  updface.face_id = face;
1930  updface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
1931  int ret = lwt_be_updateFacesById( topo, &updface, 1 );
1932  if ( ret == -1 )
1933  {
1934  lwfree( signed_edge_ids );
1935  lwpoly_free(shell); /* NOTE: owns shellbox above */
1936  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1937  return -2;
1938  }
1939  if ( ret != 1 )
1940  {
1941  lwfree( signed_edge_ids );
1942  lwpoly_free(shell); /* NOTE: owns shellbox above */
1943  lwerror("Unexpected error: %d faces found when expecting 1", ret);
1944  return -2;
1945  }
1946  }}
1947  lwfree( signed_edge_ids );
1948  lwpoly_free(shell); /* NOTE: owns shellbox above */
1949  return -1; /* mbr only was requested */
1950  }
1951 
1952  LWT_ISO_FACE *oldface = NULL;
1953  LWT_ISO_FACE newface;
1954  newface.face_id = -1;
1955  if ( face != 0 && ! isccw)
1956  {{
1957  /* Face created an hole in an outer face */
1958  int nfaces = 1;
1959  oldface = lwt_be_getFaceById(topo, &face, &nfaces, LWT_COL_FACE_ALL);
1960  if ( nfaces == -1 )
1961  {
1962  lwfree( signed_edge_ids );
1963  lwpoly_free(shell); /* NOTE: owns shellbox */
1964  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1965  return -2;
1966  }
1967  if ( nfaces != 1 )
1968  {
1969  lwfree( signed_edge_ids );
1970  lwpoly_free(shell); /* NOTE: owns shellbox */
1971  lwerror("Unexpected error: %d faces found when expecting 1", nfaces);
1972  return -2;
1973  }
1974  newface.mbr = oldface->mbr;
1975  }}
1976  else
1977  {
1978  newface.mbr = (GBOX *)shellbox; /* const cast, we won't free it, later */
1979  }
1980 
1981  /* Insert the new face */
1982  int ret = lwt_be_insertFaces( topo, &newface, 1 );
1983  if ( ret == -1 )
1984  {
1985  lwfree( signed_edge_ids );
1986  lwpoly_free(shell); /* NOTE: owns shellbox */
1987  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
1988  return -2;
1989  }
1990  if ( ret != 1 )
1991  {
1992  lwfree( signed_edge_ids );
1993  lwpoly_free(shell); /* NOTE: owns shellbox */
1994  lwerror("Unexpected error: %d faces inserted when expecting 1", ret);
1995  return -2;
1996  }
1997  if ( oldface ) {
1998  newface.mbr = NULL; /* it is a reference to oldface mbr... */
1999  _lwt_release_faces(oldface, 1);
2000  }
2001 
2002  /* Update side location of new face edges */
2003 
2004  /* We want the new face to be on the left, if possible */
2005  if ( face != 0 && ! isccw ) { /* ring is clockwise in a real face */
2006  /* face shrinked, must update all non-contained edges and nodes */
2007  LWDEBUG(1, "New face is on the outside of the ring, updating rings in former shell");
2008  newface_outside = 1;
2009  /* newface is outside */
2010  } else {
2011  LWDEBUG(1, "New face is on the inside of the ring, updating forward edges in new ring");
2012  newface_outside = 0;
2013  /* newface is inside */
2014  }
2015 
2016  /* Update edges bounding the old face */
2017  /* (1) fetch all edges where left_face or right_face is = oldface */
2018  int fields = LWT_COL_EDGE_EDGE_ID |
2022  ;
2023  numfaceedges = 1;
2024  edges = lwt_be_getEdgeByFace( topo, &face, &numfaceedges, fields, newface.mbr );
2025  if ( numfaceedges == -1 ) {
2026  lwfree( signed_edge_ids );
2027  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2028  return -2;
2029  }
2030  LWDEBUGF(1, "lwt_be_getEdgeByFace returned %d edges", numfaceedges);
2031 
2032  if ( numfaceedges )
2033  {
2034  forward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
2035  forward_edges_count = 0;
2036  backward_edges = lwalloc(sizeof(LWT_ISO_EDGE)*numfaceedges);
2037  backward_edges_count = 0;
2038 
2039  /* (2) loop over the results and: */
2040  for ( i=0; i<numfaceedges; ++i )
2041  {
2042  LWT_ISO_EDGE *e = &(edges[i]);
2043  int found = 0;
2044  int contains;
2045  POINT2D ep;
2046 
2047  /* (2.1) skip edges whose ID is in the list of boundary edges ? */
2048  for ( j=0; j<num_signed_edge_ids; ++j )
2049  {
2050  int seid = signed_edge_ids[j];
2051  if ( seid == e->edge_id )
2052  {
2053  /* IDEA: remove entry from signed_edge_ids ? */
2054  LWDEBUGF(1, "Edge %d is a forward edge of the new ring", e->edge_id);
2055  forward_edges[forward_edges_count].edge_id = e->edge_id;
2056  forward_edges[forward_edges_count++].face_left = newface.face_id;
2057  found++;
2058  if ( found == 2 ) break;
2059  }
2060  else if ( -seid == e->edge_id )
2061  {
2062  /* IDEA: remove entry from signed_edge_ids ? */
2063  LWDEBUGF(1, "Edge %d is a backward edge of the new ring", e->edge_id);
2064  backward_edges[backward_edges_count].edge_id = e->edge_id;
2065  backward_edges[backward_edges_count++].face_right = newface.face_id;
2066  found++;
2067  if ( found == 2 ) break;
2068  }
2069  }
2070  if ( found ) continue;
2071 
2072  /* We need to check only a single point
2073  * (to avoid collapsed elements of the shell polygon
2074  * giving false positive).
2075  * The point but must not be an endpoint.
2076  */
2077  if ( ! _lwt_GetInteriorEdgePoint(e->geom, &ep) )
2078  {
2079  lwfree(signed_edge_ids);
2080  lwpoly_free(shell);
2081  lwfree(forward_edges); /* contents owned by edges */
2082  lwfree(backward_edges); /* contents owned by edges */
2083  _lwt_release_edges(edges, numfaceedges);
2084  lwerror("Could not find interior point for edge %d: %s",
2086  return -2;
2087  }
2088 
2089  /* IDEA: check that bounding box shortcut is taken, or use
2090  * shellbox to do it here */
2091  contains = ptarray_contains_point(pa, &ep) == LW_INSIDE;
2092  if ( contains == 2 )
2093  LWDEBUGF(1, "Edge %d %scontained in new ring", e->edge_id,
2094  (contains?"":"not "));
2095 
2096  /* (2.2) skip edges (NOT, if newface_outside) contained in shell */
2097  if ( newface_outside )
2098  {
2099  if ( contains )
2100  {
2101  LWDEBUGF(1, "Edge %d contained in an hole of the new face",
2102  e->edge_id);
2103  continue;
2104  }
2105  }
2106  else
2107  {
2108  if ( ! contains )
2109  {
2110  LWDEBUGF(1, "Edge %d not contained in the face shell",
2111  e->edge_id);
2112  continue;
2113  }
2114  }
2115 
2116  /* (2.3) push to forward_edges if left_face = oface */
2117  if ( e->face_left == face )
2118  {
2119  LWDEBUGF(1, "Edge %d has new face on the left side", e->edge_id);
2120  forward_edges[forward_edges_count].edge_id = e->edge_id;
2121  forward_edges[forward_edges_count++].face_left = newface.face_id;
2122  }
2123 
2124  /* (2.4) push to backward_edges if right_face = oface */
2125  if ( e->face_right == face )
2126  {
2127  LWDEBUGF(1, "Edge %d has new face on the right side", e->edge_id);
2128  backward_edges[backward_edges_count].edge_id = e->edge_id;
2129  backward_edges[backward_edges_count++].face_right = newface.face_id;
2130  }
2131  }
2132 
2133  /* Update forward edges */
2134  if ( forward_edges_count )
2135  {
2136  ret = lwt_be_updateEdgesById(topo, forward_edges,
2137  forward_edges_count,
2139  if ( ret == -1 )
2140  {
2141  lwfree( signed_edge_ids );
2142  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2143  return -2;
2144  }
2145  if ( ret != forward_edges_count )
2146  {
2147  lwfree( signed_edge_ids );
2148  lwerror("Unexpected error: %d edges updated when expecting %d",
2149  ret, forward_edges_count);
2150  return -2;
2151  }
2152  }
2153 
2154  /* Update backward edges */
2155  if ( backward_edges_count )
2156  {
2157  ret = lwt_be_updateEdgesById(topo, backward_edges,
2158  backward_edges_count,
2160  if ( ret == -1 )
2161  {
2162  lwfree( signed_edge_ids );
2163  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2164  return -2;
2165  }
2166  if ( ret != backward_edges_count )
2167  {
2168  lwfree( signed_edge_ids );
2169  lwerror("Unexpected error: %d edges updated when expecting %d",
2170  ret, backward_edges_count);
2171  return -2;
2172  }
2173  }
2174 
2175  lwfree(forward_edges);
2176  lwfree(backward_edges);
2177 
2178  }
2179 
2180  _lwt_release_edges(edges, numfaceedges);
2181 
2182  /* Update isolated nodes which are now in new face */
2183  int numisonodes = 1;
2185  LWT_ISO_NODE *nodes = lwt_be_getNodeByFace(topo, &face,
2186  &numisonodes, fields, newface.mbr);
2187  if ( numisonodes == -1 ) {
2188  lwfree( signed_edge_ids );
2189  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2190  return -2;
2191  }
2192  if ( numisonodes ) {
2193  LWT_ISO_NODE *updated_nodes = lwalloc(sizeof(LWT_ISO_NODE)*numisonodes);
2194  int nodes_to_update = 0;
2195  for (i=0; i<numisonodes; ++i)
2196  {
2197  LWT_ISO_NODE *n = &(nodes[i]);
2198  const POINT2D *pt = getPoint2d_cp(n->geom->point, 0);
2199  int contains = ptarray_contains_point(pa, pt) == LW_INSIDE;
2200  LWDEBUGF(1, "Node %d is %scontained in new ring, newface is %s",
2201  n->node_id, contains ? "" : "not ",
2202  newface_outside ? "outside" : "inside" );
2203  if ( newface_outside )
2204  {
2205  if ( contains )
2206  {
2207  LWDEBUGF(1, "Node %d contained in an hole of the new face",
2208  n->node_id);
2209  continue;
2210  }
2211  }
2212  else
2213  {
2214  if ( ! contains )
2215  {
2216  LWDEBUGF(1, "Node %d not contained in the face shell",
2217  n->node_id);
2218  continue;
2219  }
2220  }
2221  updated_nodes[nodes_to_update].node_id = n->node_id;
2222  updated_nodes[nodes_to_update++].containing_face =
2223  newface.face_id;
2224  LWDEBUGF(1, "Node %d will be updated", n->node_id);
2225  }
2226  _lwt_release_nodes(nodes, numisonodes);
2227  if ( nodes_to_update )
2228  {
2229  int ret = lwt_be_updateNodesById(topo, updated_nodes,
2230  nodes_to_update,
2232  if ( ret == -1 ) {
2233  lwfree( signed_edge_ids );
2234  lwerror("Backend error: %s", lwt_be_lastErrorMessage(topo->be_iface));
2235  return -2;
2236  }
2237  }
2238  lwfree(updated_nodes);
2239  }
2240 
2241  lwfree(signed_edge_ids);
2242  lwpoly_free(shell);
2243 
2244  return newface.face_id;
2245 }
static void _lwt_release_nodes(LWT_ISO_NODE *nodes, int num_nodes)
Definition: lwgeom_topo.c:467
static int _lwt_GetInteriorEdgePoint(const LWLINE *edge, POINT2D *ip)
Definition: lwgeom_topo.c:1710
static LWT_ISO_FACE * lwt_be_getFaceById(LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields)
Definition: lwgeom_topo.c:232
LWT_ELEMID face_left
#define LWT_COL_NODE_CONTAINING_FACE
static int lwt_be_insertFaces(LWT_TOPOLOGY *topo, LWT_ISO_FACE *face, int numelems)
Definition: lwgeom_topo.c:201
#define LWT_COL_EDGE_FACE_LEFT
LWT_ELEMID containing_face
static int lwt_be_updateEdgesById(LWT_TOPOLOGY *topo, const LWT_ISO_EDGE *edges, int numedges, int upd_fields)
Definition: lwgeom_topo.c:306
LWPOINT * geom
int ptarray_isccw(const POINTARRAY *pa)
Definition: ptarray.c:1028
void lwfree(void *mem)
Definition: lwutil.c:244
#define LWT_COL_EDGE_FACE_RIGHT
Datum contains(PG_FUNCTION_ARGS)
char lwgeom_geos_errmsg[LWGEOM_GEOS_ERRMSG_MAXSIZE]
LWLINE * geom
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
POINTARRAY * point
Definition: liblwgeom.h:413
LWGEOM * lwpoly_as_lwgeom(const LWPOLY *obj)
Definition: lwgeom.c:320
static LWT_ISO_EDGE * lwt_be_getEdgeByFace(LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields, const GBOX *box)
Definition: lwgeom_topo.c:246
static int lwt_be_updateFacesById(LWT_TOPOLOGY *topo, const LWT_ISO_FACE *faces, int numfaces)
Definition: lwgeom_topo.c:298
void lwpoly_free(LWPOLY *poly)
Definition: lwpoly.c:175
const LWT_BE_IFACE * be_iface
LWT_ELEMID face_id
static LWT_ISO_NODE * lwt_be_getNodeByFace(LWT_TOPOLOGY *topo, const LWT_ELEMID *ids, int *numelems, int fields, const GBOX *box)
Definition: lwgeom_topo.c:253
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:734
POINTARRAY ** rings
Definition: liblwgeom.h:459
LWT_ELEMID face_right
#define LW_INSIDE
Constants for point-in-polygon return values.
LWT_ELEMID node_id
LWT_ELEMID edge_id
static LWT_ELEMID * lwt_be_getRingEdges(LWT_TOPOLOGY *topo, LWT_ELEMID edge, int *numedges, int limit)
Definition: lwgeom_topo.c:380
static int lwt_be_updateNodesById(LWT_TOPOLOGY *topo, const LWT_ISO_NODE *nodes, int numnodes, int upd_fields)
Definition: lwgeom_topo.c:314
#define LWT_COL_EDGE_EDGE_ID
Edge fields.
#define LWT_COL_FACE_ALL
#define LWT_COL_NODE_NODE_ID
Node fields.
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:457
static LWPOLY * _lwt_MakeRingShell(LWT_TOPOLOGY *topo, LWT_ELEMID *signed_edge_ids, int num_signed_edge_ids)
Definition: lwgeom_topo.c:1743
#define LWT_COL_NODE_GEOM
int ptarray_contains_point(const POINTARRAY *pa, const POINT2D *pt)
Return 1 if the point is inside the POINTARRAY, -1 if it is outside, and 0 if it is on the boundary...
Definition: ptarray.c:734
LWT_INT64 LWT_ELEMID
Identifier of topology element.
static void _lwt_release_faces(LWT_ISO_FACE *faces, int num_faces)
Definition: lwgeom_topo.c:447
#define LWT_COL_EDGE_GEOM
void * lwalloc(size_t size)
Definition: lwutil.c:229
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
uint32_t e
Definition: geobuf.h:57
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:190
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:44
const POINT2D * getPoint2d_cp(const POINTARRAY *pa, uint32_t n)
Returns a POINT2D pointer into the POINTARRAY serialized_ptlist, suitable for reading from...
Definition: lwgeom_api.c:364
Here is the call graph for this function:
Here is the caller graph for this function: