PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ lwt_Polygonize()

int lwt_Polygonize ( LWT_TOPOLOGY topo)

Definition at line 6674 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.

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