PostGIS  2.5.0beta2dev-r@@SVN_REVISION@@

◆ _lwt_FindFaceContainingRing()

static LWT_ELEMID _lwt_FindFaceContainingRing ( LWT_TOPOLOGY topo,
LWT_EDGERING ring,
LWT_EDGERING_ARRAY shells 
)
static

Definition at line 6517 of file lwgeom_topo.c.

References _lwt_AccumulateCanditates(), _lwt_EdgeRingContainsPoint(), _lwt_EdgeRingGetBbox(), _lwt_EdgeRingGetFace(), contains(), LWT_EDGERING_ELEM_T::edge, LWT_ISO_EDGE::edge_id, LWT_EDGERING_T::elems, gbox_contains_2d(), gbox_same(), LWT_EDGERING_T::genv, LWT_ISO_EDGE::geom, getPoint2d_p(), LWT_EDGERING_ELEM_T::left, LWDEBUG, LWDEBUGF, lwerror(), LWGEOM2GEOS(), lwgeom_geos_errmsg, lwline_as_lwgeom(), lwline_construct(), lwline_free(), lwpoint_as_lwgeom(), lwpoint_free(), lwpoint_make2d(), LWT_EDGERING_ARRAY_CLEAN, LWT_EDGERING_ARRAY_INIT, LWLINE::points, ptarray_construct(), ptarray_set_point4d(), LWT_EDGERING_ARRAY_T::rings, LWT_EDGERING_ARRAY_T::size, LWT_TOPOLOGY_T::srid, STRTREE_NODE_CAPACITY, LWT_EDGERING_ARRAY_T::tree, POINT2D::x, POINT4D::x, GBOX::xmax, GBOX::xmin, POINT2D::y, POINT4D::y, GBOX::ymax, and GBOX::ymin.

Referenced by lwt_Polygonize().

6519 {
6520  LWT_ELEMID foundInFace = -1;
6521  int i;
6522  const GBOX *minenv = NULL;
6523  POINT2D pt;
6524  const GBOX *testbox;
6525  GEOSGeometry *ghole;
6526 
6527  getPoint2d_p( ring->elems[0]->edge->geom->points, 0, &pt );
6528 
6529  testbox = _lwt_EdgeRingGetBbox(ring);
6530 
6531  /* Create a GEOS Point from a vertex of the hole ring */
6532  {
6533  LWPOINT *point = lwpoint_make2d(topo->srid, pt.x, pt.y);
6534  ghole = LWGEOM2GEOS( lwpoint_as_lwgeom(point), 1 );
6535  lwpoint_free(point);
6536  if ( ! ghole ) {
6537  lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
6538  return -1;
6539  }
6540  }
6541 
6542  /* Build STRtree of shell envelopes */
6543  if ( ! shells->tree )
6544  {
6545  static const int STRTREE_NODE_CAPACITY = 10;
6546  LWDEBUG(1, "Building STRtree");
6547  shells->tree = GEOSSTRtree_create(STRTREE_NODE_CAPACITY);
6548  if (shells->tree == NULL)
6549  {
6550  lwerror("Could not create GEOS STRTree: %s", lwgeom_geos_errmsg);
6551  return -1;
6552  }
6553  for (i=0; i<shells->size; ++i)
6554  {
6555  LWT_EDGERING *sring = shells->rings[i];
6556  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6557  LWDEBUGF(2, "GBOX of shell %p for edge %d is %g %g,%g %g",
6558  sring, sring->elems[0]->edge->edge_id, shellbox->xmin,
6559  shellbox->ymin, shellbox->xmax, shellbox->ymax);
6560  POINTARRAY *pa = ptarray_construct(0, 0, 2);
6561  POINT4D pt;
6562  LWLINE *diag;
6563  pt.x = shellbox->xmin;
6564  pt.y = shellbox->ymin;
6565  ptarray_set_point4d(pa, 0, &pt);
6566  pt.x = shellbox->xmax;
6567  pt.y = shellbox->ymax;
6568  ptarray_set_point4d(pa, 1, &pt);
6569  diag = lwline_construct(topo->srid, NULL, pa);
6570  /* Record just envelope in ggeom */
6571  /* making valid, probably not needed */
6572  sring->genv = LWGEOM2GEOS( lwline_as_lwgeom(diag), 1 );
6573  lwline_free(diag);
6574  GEOSSTRtree_insert(shells->tree, sring->genv, sring);
6575  }
6576  LWDEBUG(1, "STRtree build completed");
6577  }
6578 
6579  LWT_EDGERING_ARRAY candidates;
6580  LWT_EDGERING_ARRAY_INIT(&candidates);
6581  GEOSSTRtree_query(shells->tree, ghole, &_lwt_AccumulateCanditates, &candidates);
6582  LWDEBUGF(1, "Found %d candidate shells containing first point of ring's originating edge %d",
6583  candidates.size, ring->elems[0]->edge->edge_id * ( ring->elems[0]->left ? 1 : -1 ) );
6584 
6585  /* TODO: sort candidates by bounding box size */
6586 
6587  for (i=0; i<candidates.size; ++i)
6588  {
6589  LWT_EDGERING *sring = candidates.rings[i];
6590  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6591  int contains = 0;
6592 
6593  if ( sring->elems[0]->edge->edge_id == ring->elems[0]->edge->edge_id )
6594  {
6595  LWDEBUGF(1, "Shell %d is on other side of ring",
6596  _lwt_EdgeRingGetFace(sring));
6597  continue;
6598  }
6599 
6600  /* The hole envelope cannot equal the shell envelope */
6601  if ( gbox_same(shellbox, testbox) )
6602  {
6603  LWDEBUGF(1, "Bbox of shell %d equals that of hole ring",
6604  _lwt_EdgeRingGetFace(sring));
6605  continue;
6606  }
6607 
6608  /* Skip if ring box is not in shell box */
6609  if ( ! gbox_contains_2d(shellbox, testbox) )
6610  {
6611  LWDEBUGF(1, "Bbox of shell %d does not contain bbox of ring point",
6612  _lwt_EdgeRingGetFace(sring));
6613  continue;
6614  }
6615 
6616  /* Skip test if a containing shell was already found
6617  * and this shell's bbox is not contained in the other */
6618  if ( minenv && ! gbox_contains_2d(minenv, shellbox) )
6619  {
6620  LWDEBUGF(2, "Bbox of shell %d (face %d) not contained by bbox "
6621  "of last shell found to contain the point",
6622  i, _lwt_EdgeRingGetFace(sring));
6623  continue;
6624  }
6625 
6626  contains = _lwt_EdgeRingContainsPoint(sring, &pt);
6627  if ( contains )
6628  {
6629  /* Continue until all shells are tested, as we want to
6630  * use the one with the smallest bounding box */
6631  /* IDEA: sort shells by bbox size, stopping on first match */
6632  LWDEBUGF(1, "Shell %d contains hole of edge %d",
6633  _lwt_EdgeRingGetFace(sring),
6634  ring->elems[0]->edge->edge_id);
6635  minenv = shellbox;
6636  foundInFace = _lwt_EdgeRingGetFace(sring);
6637  }
6638  }
6639  if ( foundInFace == -1 ) foundInFace = 0;
6640 
6641  candidates.size = 0; /* Avoid destroying the actual shell rings */
6642  LWT_EDGERING_ARRAY_CLEAN(&candidates);
6643 
6644  GEOSGeom_destroy(ghole);
6645 
6646  return foundInFace;
6647 }
double x
Definition: liblwgeom.h:354
POINTARRAY * ptarray_construct(char hasz, char hasm, uint32_t npoints)
Construct an empty pointarray, allocating storage and setting the npoints, but not filling in any inf...
Definition: ptarray.c:62
LWPOINT * lwpoint_make2d(int srid, double x, double y)
Definition: lwpoint.c:163
LWT_EDGERING ** rings
Definition: lwgeom_topo.c:6004
double xmax
Definition: liblwgeom.h:295
void lwpoint_free(LWPOINT *pt)
Definition: lwpoint.c:213
void lwline_free(LWLINE *line)
Definition: lwline.c:76
Datum contains(PG_FUNCTION_ARGS)
char lwgeom_geos_errmsg[LWGEOM_GEOS_ERRMSG_MAXSIZE]
void ptarray_set_point4d(POINTARRAY *pa, uint32_t n, const POINT4D *p4d)
Definition: lwgeom_api.c:425
LWLINE * geom
static GBOX * _lwt_EdgeRingGetBbox(LWT_EDGERING *ring)
Definition: lwgeom_topo.c:6388
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
int gbox_contains_2d(const GBOX *g1, const GBOX *g2)
Return LW_TRUE if the first GBOX contains the second on the 2d plane, LW_FALSE otherwise.
Definition: g_box.c:346
static int _lwt_EdgeRingContainsPoint(LWT_EDGERING *ring, POINT2D *p)
Definition: lwgeom_topo.c:6377
static const int STRTREE_NODE_CAPACITY
double x
Definition: liblwgeom.h:330
LWT_ISO_EDGE * edge
Definition: lwgeom_topo.c:5951
double ymin
Definition: liblwgeom.h:296
static LWT_ELEMID _lwt_EdgeRingGetFace(LWT_EDGERING *ring)
Definition: lwgeom_topo.c:6409
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:330
double xmin
Definition: liblwgeom.h:294
static void _lwt_AccumulateCanditates(void *item, void *userdata)
Definition: lwgeom_topo.c:6509
LWLINE * lwline_construct(int srid, GBOX *bbox, POINTARRAY *points)
Definition: lwline.c:42
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6019
double ymax
Definition: liblwgeom.h:297
double y
Definition: liblwgeom.h:330
LWT_ELEMID edge_id
LWT_EDGERING_ELEM ** elems
Definition: lwgeom_topo.c:5961
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, uint8_t autofix)
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6010
int getPoint2d_p(const POINTARRAY *pa, uint32_t n, POINT2D *point)
Definition: lwgeom_api.c:338
GEOSGeometry * genv
Definition: lwgeom_topo.c:5968
LWGEOM * lwpoint_as_lwgeom(const LWPOINT *obj)
Definition: lwgeom.c:335
LWT_INT64 LWT_ELEMID
Identifier of topology element.
double y
Definition: liblwgeom.h:354
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
int gbox_same(const GBOX *g1, const GBOX *g2)
Check if 2 given Gbox are the same.
Definition: g_box.c:171
void lwerror(const char *fmt,...)
Write a notice out to the error handler.
Definition: lwutil.c:190
GEOSSTRtree * tree
Definition: lwgeom_topo.c:6007
POINTARRAY * points
Definition: liblwgeom.h:424
Here is the call graph for this function:
Here is the caller graph for this function: