PostGIS  3.0.0dev-r@@SVN_REVISION@@

◆ lwt_Polygonize()

int lwt_Polygonize ( LWT_TOPOLOGY topo)

Definition at line 6673 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, and LWT_EDGERING_ARRAY_T::size.

6674 {
6675  /*
6676  Fetch all edges
6677  Sort edges by edge_id
6678  Mark all edges' left and right face as -1
6679  Iteratively:
6680  Fetch next edge with left or right face == -1
6681  For each side with face == -1:
6682  Find ring on its side
6683  If ring is CCW:
6684  create a new face, assign to the ring edges' appropriate side
6685  If ring is CW (face needs to be same of external):
6686  assign a negative face_id the ring edges' appropriate side
6687  Now for each edge with a negative face_id on the side:
6688  Find containing face (mbr cache and all)
6689  Update with id of containing face
6690  */
6691 
6692  const LWT_BE_IFACE *iface = topo->be_iface;
6693  LWT_ISO_EDGE *edge;
6694  int numfaces = -1;
6695  LWT_ISO_EDGE_TABLE edgetable;
6696  LWT_EDGERING_ARRAY holes, shells;
6697  int i;
6698  int err = 0;
6699 
6700  LWT_EDGERING_ARRAY_INIT(&holes);
6701  LWT_EDGERING_ARRAY_INIT(&shells);
6702 
6703  initGEOS(lwnotice, lwgeom_geos_error);
6704 
6705  /*
6706  Check if Topology already contains some Face
6707  (ignoring the Universal Face)
6708  */
6709  numfaces = _lwt_CheckFacesExist(topo);
6710  if ( numfaces != 0 ) {
6711  if ( numfaces > 0 ) {
6712  /* Faces exist */
6713  lwerror("Polygonize: face table is not empty.");
6714  }
6715  /* Backend error, message should have been printed already */
6716  return -1;
6717  }
6718 
6719 
6720  edgetable.edges = _lwt_FetchAllEdges(topo, &(edgetable.size));
6721  if ( ! edgetable.edges ) {
6722  if (edgetable.size == 0) {
6723  /* not an error: no Edges */
6724  return 0;
6725  }
6726  /* error should have been printed already */
6727  return -1;
6728  }
6729 
6730  /* Sort edges by ID (to allow btree searches) */
6731  qsort(edgetable.edges, edgetable.size, sizeof(LWT_ISO_EDGE), compare_iso_edges_by_id);
6732 
6733  /* Mark all edges as unvisited */
6734  for (i=0; i<edgetable.size; ++i)
6735  edgetable.edges[i].face_left = edgetable.edges[i].face_right = -1;
6736 
6737  i = 0;
6738  while (1)
6739  {
6740  i = _lwt_FetchNextUnvisitedEdge(topo, &edgetable, i);
6741  if ( i < 0 ) break; /* end of unvisited */
6742  edge = &(edgetable.edges[i]);
6743 
6744  LWT_ELEMID newface = -1;
6745 
6746  LWDEBUGF(1, "Next face-missing edge has id:%d, face_left:%d, face_right:%d",
6747  edge->edge_id, edge->face_left, edge->face_right);
6748  if ( edge->face_left == -1 )
6749  {
6750  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, 1, &edgetable,
6751  &holes, &shells, &newface);
6752  if ( err ) break;
6753  LWDEBUGF(1, "New face on the left of edge %d is %d",
6754  edge->edge_id, newface);
6755  edge->face_left = newface;
6756  }
6757  if ( edge->face_right == -1 )
6758  {
6759  err = _lwt_RegisterFaceOnEdgeSide(topo, edge, -1, &edgetable,
6760  &holes, &shells, &newface);
6761  if ( err ) break;
6762  LWDEBUGF(1, "New face on the right of edge %d is %d",
6763  edge->edge_id, newface);
6764  edge->face_right = newface;
6765  }
6766  }
6767 
6768  if ( err )
6769  {
6770  _lwt_release_edges(edgetable.edges, edgetable.size);
6771  LWT_EDGERING_ARRAY_CLEAN( &holes );
6772  LWT_EDGERING_ARRAY_CLEAN( &shells );
6773  lwerror("Errors fetching or registering face-missing edges: %s",
6774  lwt_be_lastErrorMessage(iface));
6775  return -1;
6776  }
6777 
6778  LWDEBUGF(1, "Found %d holes and %d shells", holes.size, shells.size);
6779 
6780  /* TODO: sort holes by pt.x, sort shells by bbox.xmin */
6781 
6782  /* Assign shells to holes */
6783  for (i=0; i<holes.size; ++i)
6784  {
6785  LWT_ELEMID containing_face;
6786  LWT_EDGERING *ring = holes.rings[i];
6787 
6788  containing_face = _lwt_FindFaceContainingRing(topo, ring, &shells);
6789  LWDEBUGF(1, "Ring %d contained by face %" LWTFMT_ELEMID, i, containing_face);
6790  if ( containing_face == -1 )
6791  {
6792  _lwt_release_edges(edgetable.edges, edgetable.size);
6793  LWT_EDGERING_ARRAY_CLEAN( &holes );
6794  LWT_EDGERING_ARRAY_CLEAN( &shells );
6795  lwerror("Errors finding face containing ring: %s",
6796  lwt_be_lastErrorMessage(iface));
6797  return -1;
6798  }
6799  int ret = _lwt_UpdateEdgeRingSideFace(topo, holes.rings[i], containing_face);
6800  if ( ret )
6801  {
6802  _lwt_release_edges(edgetable.edges, edgetable.size);
6803  LWT_EDGERING_ARRAY_CLEAN( &holes );
6804  LWT_EDGERING_ARRAY_CLEAN( &shells );
6805  lwerror("Errors updating edgering side face: %s",
6806  lwt_be_lastErrorMessage(iface));
6807  return -1;
6808  }
6809  }
6810 
6811  LWDEBUG(1, "All holes assigned, cleaning up");
6812 
6813  _lwt_release_edges(edgetable.edges, edgetable.size);
6814 
6815  /* delete all shell and hole EDGERINGS */
6816  LWT_EDGERING_ARRAY_CLEAN( &holes );
6817  LWT_EDGERING_ARRAY_CLEAN( &shells );
6818 
6819  return 0;
6820 }
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:6441
void lwnotice(const char *fmt,...)
Write a notice out to the notice handler.
Definition: lwutil.c:177
LWT_EDGERING ** rings
Definition: lwgeom_topo.c:6003
#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:6137
LWT_ISO_EDGE * edges
Definition: lwgeom_topo.c:5919
static int _lwt_FetchNextUnvisitedEdge(__attribute__((__unused__)) LWT_TOPOLOGY *topo, LWT_ISO_EDGE_TABLE *etab, int from)
Definition: lwgeom_topo.c:6101
static int compare_iso_edges_by_id(const void *si1, const void *si2)
Definition: lwgeom_topo.c:5924
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:6516
const LWT_BE_IFACE * be_iface
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6018
LWT_ELEMID face_right
static LWT_ISO_EDGE * _lwt_FetchAllEdges(LWT_TOPOLOGY *topo, int *numedges)
Definition: lwgeom_topo.c:6112
LWT_ELEMID edge_id
static int _lwt_CheckFacesExist(LWT_TOPOLOGY *topo)
Definition: lwgeom_topo.c:6654
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6009
static void _lwt_release_edges(LWT_ISO_EDGE *edges, int num_edges)
Definition: lwgeom_topo.c:456
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:119
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
#define LWTFMT_ELEMID
Definition: lwgeom_topo.c:43
Here is the call graph for this function: