PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ lwt_Polygonize()

int lwt_Polygonize ( LWT_TOPOLOGY topo)

Definition at line 6702 of file lwgeom_topo.c.

6703 {
6704  /*
6705  Fetch all edges
6706  Sort edges by edge_id
6707  Mark all edges' left and right face as -1
6708  Iteratively:
6709  Fetch next edge with left or right face == -1
6710  For each side with face == -1:
6711  Find ring on its side
6712  If ring is CCW:
6713  create a new face, assign to the ring edges' appropriate side
6714  If ring is CW (face needs to be same of external):
6715  assign a negative face_id the ring edges' appropriate side
6716  Now for each edge with a negative face_id on the side:
6717  Find containing face (mbr cache and all)
6718  Update with id of containing face
6719  */
6720 
6721  const LWT_BE_IFACE *iface = topo->be_iface;
6722  LWT_ISO_EDGE *edge;
6723  int numfaces = -1;
6724  LWT_ISO_EDGE_TABLE edgetable;
6725  LWT_EDGERING_ARRAY holes, shells;
6726  int i;
6727  int err = 0;
6728 
6729  LWT_EDGERING_ARRAY_INIT(&holes);
6730  LWT_EDGERING_ARRAY_INIT(&shells);
6731 
6732  initGEOS(lwnotice, lwgeom_geos_error);
6733 
6734  /*
6735  Check if Topology already contains some Face
6736  (ignoring the Universal Face)
6737  */
6738  numfaces = _lwt_CheckFacesExist(topo);
6739  if ( numfaces != 0 ) {
6740  if ( numfaces > 0 ) {
6741  /* Faces exist */
6742  lwerror("Polygonize: face table is not empty.");
6743  }
6744  /* Backend error, message should have been printed already */
6745  return -1;
6746  }
6747 
6748 
6749  edgetable.edges = _lwt_FetchAllEdges(topo, &(edgetable.size));
6750  if ( ! edgetable.edges ) {
6751  if (edgetable.size == 0) {
6752  /* not an error: no Edges */
6753  return 0;
6754  }
6755  /* error should have been printed already */
6756  return -1;
6757  }
6758 
6759  /* Sort edges by ID (to allow btree searches) */
6760  qsort(edgetable.edges, edgetable.size, sizeof(LWT_ISO_EDGE), compare_iso_edges_by_id);
6761 
6762  /* Mark all edges as unvisited */
6763  for (i=0; i<edgetable.size; ++i)
6764  edgetable.edges[i].face_left = edgetable.edges[i].face_right = -1;
6765 
6766  i = 0;
6767  while (1)
6768  {
6769  i = _lwt_FetchNextUnvisitedEdge(topo, &edgetable, i);
6770  if ( i < 0 ) break; /* end of unvisited */
6771  edge = &(edgetable.edges[i]);
6772 
6773  LWT_ELEMID newface = -1;
6774 
6775  LWDEBUGF(1, "Next face-missing edge has id:%d, face_left:%d, face_right:%d",
6776  edge->edge_id, edge->face_left, edge->face_right);
6777  if ( edge->face_left == -1 )
6778  {
6779  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, 1, &edgetable,
6780  &holes, &shells, &newface);
6781  if ( err ) break;
6782  LWDEBUGF(1, "New face on the left of edge %d is %d",
6783  edge->edge_id, newface);
6784  edge->face_left = newface;
6785  }
6786  if ( edge->face_right == -1 )
6787  {
6788  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, -1, &edgetable,
6789  &holes, &shells, &newface);
6790  if ( err ) break;
6791  LWDEBUGF(1, "New face on the right of edge %d is %d",
6792  edge->edge_id, newface);
6793  edge->face_right = newface;
6794  }
6795  }
6796 
6797  if ( err )
6798  {
6799  _lwt_release_edges(edgetable.edges, edgetable.size);
6800  LWT_EDGERING_ARRAY_CLEAN( &holes );
6801  LWT_EDGERING_ARRAY_CLEAN( &shells );
6802  lwerror("Errors fetching or registering face-missing edges: %s",
6803  lwt_be_lastErrorMessage(iface));
6804  return -1;
6805  }
6806 
6807  LWDEBUGF(1, "Found %d holes and %d shells", holes.size, shells.size);
6808 
6809  /* TODO: sort holes by pt.x, sort shells by bbox.xmin */
6810 
6811  /* Assign shells to holes */
6812  for (i=0; i<holes.size; ++i)
6813  {
6814  LWT_ELEMID containing_face;
6815  LWT_EDGERING *ring = holes.rings[i];
6816 
6817  containing_face = _lwt_FindFaceContainingRing(topo, ring, &shells);
6818  LWDEBUGF(1, "Ring %d contained by face %" LWTFMT_ELEMID, i, containing_face);
6819  if ( containing_face == -1 )
6820  {
6821  _lwt_release_edges(edgetable.edges, edgetable.size);
6822  LWT_EDGERING_ARRAY_CLEAN( &holes );
6823  LWT_EDGERING_ARRAY_CLEAN( &shells );
6824  lwerror("Errors finding face containing ring: %s",
6825  lwt_be_lastErrorMessage(iface));
6826  return -1;
6827  }
6828  int ret = _lwt_UpdateEdgeRingSideFace(topo, holes.rings[i], containing_face);
6829  if ( ret )
6830  {
6831  _lwt_release_edges(edgetable.edges, edgetable.size);
6832  LWT_EDGERING_ARRAY_CLEAN( &holes );
6833  LWT_EDGERING_ARRAY_CLEAN( &shells );
6834  lwerror("Errors updating edgering side face: %s",
6835  lwt_be_lastErrorMessage(iface));
6836  return -1;
6837  }
6838  }
6839 
6840  LWDEBUG(1, "All holes assigned, cleaning up");
6841 
6842  _lwt_release_edges(edgetable.edges, edgetable.size);
6843 
6844  /* delete all shell and hole EDGERINGS */
6845  LWT_EDGERING_ARRAY_CLEAN( &holes );
6846  LWT_EDGERING_ARRAY_CLEAN( &shells );
6847 
6848  return 0;
6849 }
void lwgeom_geos_error(const char *fmt,...)
LWT_INT64 LWT_ELEMID
Identifier of topology element.
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
void lwnotice(const char *fmt,...)
Write a notice out to the notice handler.
Definition: lwutil.c:177
const char * lwt_be_lastErrorMessage(const LWT_BE_IFACE *be)
Definition: lwgeom_topo.c:120
static int _lwt_UpdateEdgeRingSideFace(LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_ELEMID face)
Definition: lwgeom_topo.c:6166
static int _lwt_CheckFacesExist(LWT_TOPOLOGY *topo)
Definition: lwgeom_topo.c:6683
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6038
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:6470
static LWT_ELEMID _lwt_FindFaceContainingRing(LWT_TOPOLOGY *topo, LWT_EDGERING *ring, LWT_EDGERING_ARRAY *shells)
Definition: lwgeom_topo.c:6545
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6047
static LWT_ISO_EDGE * _lwt_FetchAllEdges(LWT_TOPOLOGY *topo, int *numedges)
Definition: lwgeom_topo.c:6141
static int compare_iso_edges_by_id(const void *si1, const void *si2)
Definition: lwgeom_topo.c:5953
static int _lwt_FetchNextUnvisitedEdge(__attribute__((__unused__)) LWT_TOPOLOGY *topo, LWT_ISO_EDGE_TABLE *etab, int from)
Definition: lwgeom_topo.c:6130
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:44
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:457
LWT_EDGERING ** rings
Definition: lwgeom_topo.c:6032
LWT_ISO_EDGE * edges
Definition: lwgeom_topo.c:5948
LWT_ELEMID face_right
LWT_ELEMID face_left
LWT_ELEMID edge_id
const LWT_BE_IFACE * be_iface

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, and LWT_EDGERING_ARRAY_T::size.

Here is the call graph for this function: