PostGIS  2.5.0dev-r@@SVN_REVISION@@
int lwt_Polygonize ( LWT_TOPOLOGY topo)

Definition at line 6904 of file lwgeom_topo.c.

References _lwt_CheckFacesExist(), _lwt_FetchAllEdges(), _lwt_FetchNextUnvisitedEdge(), _lwt_FindFaceContainingRing(), _lwt_RegisterFaceOnEdgeSide(), _lwt_release_edges(), _lwt_UpdateEdgeRingSideFace(), LWT_TOPOLOGY_T::be_iface, compare_iso_edges_by_id(), LWT_ISO_EDGE::edge_id, LWT_ISO_EDGE_TABLE_T::edges, LWT_ISO_EDGE::face_left, LWT_ISO_EDGE::face_right, LWDEBUG, LWDEBUGF, lwerror(), lwgeom_geos_error(), lwnotice(), lwt_be_lastErrorMessage(), LWT_EDGERING_ARRAY_CLEAN, LWT_EDGERING_ARRAY_INIT, LWTFMT_ELEMID, LWT_EDGERING_ARRAY_T::rings, LWT_ISO_EDGE_TABLE_T::size, LWT_EDGERING_ARRAY_T::size, and while().

6905 {
6906  /*
6907  Fetch all edges
6908  Sort edges by edge_id
6909  Mark all edges' left and right face as -1
6910  Iteratively:
6911  Fetch next edge with left or right face == -1
6912  For each side with face == -1:
6913  Find ring on its side
6914  If ring is CCW:
6915  create a new face, assign to the ring edges' appropriate side
6916  If ring is CW (face needs to be same of external):
6917  assign a negative face_id the ring edges' appropriate side
6918  Now for each edge with a negative face_id on the side:
6919  Find containing face (mbr cache and all)
6920  Update with id of containing face
6921  */
6922 
6923  const LWT_BE_IFACE *iface = topo->be_iface;
6924  LWT_ISO_EDGE *edge;
6925  int numfaces = -1;
6926  LWT_ISO_EDGE_TABLE edgetable;
6927  LWT_EDGERING_ARRAY holes, shells;
6928  int i;
6929  int err = 0;
6930 
6931  LWT_EDGERING_ARRAY_INIT(&holes);
6932  LWT_EDGERING_ARRAY_INIT(&shells);
6933 
6934  initGEOS(lwnotice, lwgeom_geos_error);
6935 
6936  /*
6937  Check if Topology already contains some Face
6938  (ignoring the Universal Face)
6939  */
6940  numfaces = _lwt_CheckFacesExist(topo);
6941  if ( numfaces != 0 ) {
6942  if ( numfaces > 0 ) {
6943  /* Faces exist */
6944  lwerror("Polygonize: face table is not empty.");
6945  }
6946  /* Backend error, message should have been printed already */
6947  return -1;
6948  }
6949 
6950 
6951  edgetable.edges = _lwt_FetchAllEdges(topo, &(edgetable.size));
6952  if ( ! edgetable.edges ) {
6953  if (edgetable.size == 0) {
6954  /* not an error: no Edges */
6955  return 0;
6956  }
6957  /* error should have been printed already */
6958  return -1;
6959  }
6960 
6961  /* Sort edges by ID (to allow btree searches) */
6962  qsort(edgetable.edges, edgetable.size, sizeof(LWT_ISO_EDGE), compare_iso_edges_by_id);
6963 
6964  /* Mark all edges as unvisited */
6965  for (i=0; i<edgetable.size; ++i)
6966  edgetable.edges[i].face_left = edgetable.edges[i].face_right = -1;
6967 
6968  i = 0;
6969  while (1)
6970  {
6971  i = _lwt_FetchNextUnvisitedEdge(topo, &edgetable, i);
6972  if ( i < 0 ) break; /* end of unvisited */
6973  edge = &(edgetable.edges[i]);
6974 
6975  LWT_ELEMID newface = -1;
6976 
6977  LWDEBUGF(1, "Next face-missing edge has id:%d, face_left:%d, face_right:%d",
6978  edge->edge_id, edge->face_left, edge->face_right);
6979  if ( edge->face_left == -1 )
6980  {
6981  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, 1, &edgetable,
6982  &holes, &shells, &newface);
6983  if ( err ) break;
6984  LWDEBUGF(1, "New face on the left of edge %d is %d",
6985  edge->edge_id, newface);
6986  edge->face_left = newface;
6987  }
6988  if ( edge->face_right == -1 )
6989  {
6990  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, -1, &edgetable,
6991  &holes, &shells, &newface);
6992  if ( err ) break;
6993  LWDEBUGF(1, "New face on the right of edge %d is %d",
6994  edge->edge_id, newface);
6995  edge->face_right = newface;
6996  }
6997  }
6998 
6999  if ( err )
7000  {
7001  _lwt_release_edges(edgetable.edges, edgetable.size);
7002  LWT_EDGERING_ARRAY_CLEAN( &holes );
7003  LWT_EDGERING_ARRAY_CLEAN( &shells );
7004  lwerror("Errors fetching or registering face-missing edges: %s",
7005  lwt_be_lastErrorMessage(iface));
7006  return -1;
7007  }
7008 
7009  LWDEBUGF(1, "Found %d holes and %d shells", holes.size, shells.size);
7010 
7011  /* TODO: sort holes by pt.x, sort shells by bbox.xmin */
7012 
7013  /* Assign shells to holes */
7014  for (i=0; i<holes.size; ++i)
7015  {
7016  LWT_ELEMID containing_face;
7017  LWT_EDGERING *ring = holes.rings[i];
7018 
7019  containing_face = _lwt_FindFaceContainingRing(topo, ring, &shells);
7020  LWDEBUGF(1, "Ring %d contained by face %" LWTFMT_ELEMID, i, containing_face);
7021  if ( containing_face == -1 )
7022  {
7023  _lwt_release_edges(edgetable.edges, edgetable.size);
7024  LWT_EDGERING_ARRAY_CLEAN( &holes );
7025  LWT_EDGERING_ARRAY_CLEAN( &shells );
7026  lwerror("Errors finding face containing ring: %s",
7027  lwt_be_lastErrorMessage(iface));
7028  return -1;
7029  }
7030  int ret = _lwt_UpdateEdgeRingSideFace(topo, holes.rings[i], containing_face);
7031  if ( ret )
7032  {
7033  _lwt_release_edges(edgetable.edges, edgetable.size);
7034  LWT_EDGERING_ARRAY_CLEAN( &holes );
7035  LWT_EDGERING_ARRAY_CLEAN( &shells );
7036  lwerror("Errors updating edgering side face: %s",
7037  lwt_be_lastErrorMessage(iface));
7038  return -1;
7039  }
7040  }
7041 
7042  LWDEBUG(1, "All holes assigned, cleaning up");
7043 
7044  _lwt_release_edges(edgetable.edges, edgetable.size);
7045 
7046  /* delete all shell and hole EDGERINGS */
7047  LWT_EDGERING_ARRAY_CLEAN( &holes );
7048  LWT_EDGERING_ARRAY_CLEAN( &shells );
7049 
7050  return 0;
7051 }
LWT_ELEMID face_left
static int _lwt_RegisterFaceOnEdgeSide(LWT_TOPOLOGY *topo, LWT_ISO_EDGE *edge, int side, LWT_ISO_EDGE_TABLE *edges, LWT_EDGERING_ARRAY *holes, LWT_EDGERING_ARRAY *shells, LWT_ELEMID *registered)
Definition: lwgeom_topo.c:6672
void lwnotice(const char *fmt,...)
Write a notice out to the notice handler.
Definition: lwutil.c:177
LWT_EDGERING ** rings
Definition: lwgeom_topo.c:6234
static int _lwt_FetchNextUnvisitedEdge(LWT_TOPOLOGY *topo, LWT_ISO_EDGE_TABLE *etab, int from)
Definition: lwgeom_topo.c:6332
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
static int _lwt_UpdateEdgeRingSideFace(LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_ELEMID face)
Definition: lwgeom_topo.c:6368
LWT_ISO_EDGE * edges
Definition: lwgeom_topo.c:6150
static int compare_iso_edges_by_id(const void *si1, const void *si2)
Definition: lwgeom_topo.c:6155
void lwgeom_geos_error(const char *fmt,...)
static LWT_ELEMID _lwt_FindFaceContainingRing(LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_EDGERING_ARRAY *shells)
Definition: lwgeom_topo.c:6747
const LWT_BE_IFACE * be_iface
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6249
while(1)
Definition: lwin_wkt_lex.c:914
LWT_ELEMID face_right
static LWT_ISO_EDGE * _lwt_FetchAllEdges(LWT_TOPOLOGY *topo, int *numedges)
Definition: lwgeom_topo.c:6343
LWT_ELEMID edge_id
static int _lwt_CheckFacesExist(LWT_TOPOLOGY *topo)
Definition: lwgeom_topo.c:6885
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6240
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:457
LWT_INT64 LWT_ELEMID
Identifier of topology element.
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
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

Here is the call graph for this function: