PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ _lwt_FindFaceContainingRing()

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

Definition at line 6545 of file lwgeom_topo.c.

6547 {
6548  LWT_ELEMID foundInFace = -1;
6549  int i;
6550  const GBOX *minenv = NULL;
6551  POINT2D pt;
6552  const GBOX *testbox;
6553  GEOSGeometry *ghole;
6554 
6555  getPoint2d_p( ring->elems[0]->edge->geom->points, 0, &pt );
6556 
6557  testbox = _lwt_EdgeRingGetBbox(ring);
6558 
6559  /* Create a GEOS Point from a vertex of the hole ring */
6560  {
6561  LWPOINT *point = lwpoint_make2d(topo->srid, pt.x, pt.y);
6562  ghole = LWGEOM2GEOS( lwpoint_as_lwgeom(point), 1 );
6563  lwpoint_free(point);
6564  if ( ! ghole ) {
6565  lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
6566  return -1;
6567  }
6568  }
6569 
6570  /* Build STRtree of shell envelopes */
6571  if ( ! shells->tree )
6572  {
6573  static const int STRTREE_NODE_CAPACITY = 10;
6574  LWDEBUG(1, "Building STRtree");
6575  shells->tree = GEOSSTRtree_create(STRTREE_NODE_CAPACITY);
6576  if (shells->tree == NULL)
6577  {
6578  lwerror("Could not create GEOS STRTree: %s", lwgeom_geos_errmsg);
6579  return -1;
6580  }
6581  for (i=0; i<shells->size; ++i)
6582  {
6583  LWT_EDGERING *sring = shells->rings[i];
6584  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6585  LWDEBUGF(2, "GBOX of shell %p for edge %d is %g %g,%g %g",
6586  sring, sring->elems[0]->edge->edge_id, shellbox->xmin,
6587  shellbox->ymin, shellbox->xmax, shellbox->ymax);
6588  POINTARRAY *pa = ptarray_construct(0, 0, 2);
6589  POINT4D pt;
6590  LWLINE *diag;
6591  pt.x = shellbox->xmin;
6592  pt.y = shellbox->ymin;
6593  ptarray_set_point4d(pa, 0, &pt);
6594  pt.x = shellbox->xmax;
6595  pt.y = shellbox->ymax;
6596  ptarray_set_point4d(pa, 1, &pt);
6597  diag = lwline_construct(topo->srid, NULL, pa);
6598  /* Record just envelope in ggeom */
6599  /* making valid, probably not needed */
6600  sring->genv = LWGEOM2GEOS( lwline_as_lwgeom(diag), 1 );
6601  lwline_free(diag);
6602  GEOSSTRtree_insert(shells->tree, sring->genv, sring);
6603  }
6604  LWDEBUG(1, "STRtree build completed");
6605  }
6606 
6607  LWT_EDGERING_ARRAY candidates;
6608  LWT_EDGERING_ARRAY_INIT(&candidates);
6609  GEOSSTRtree_query(shells->tree, ghole, &_lwt_AccumulateCanditates, &candidates);
6610  LWDEBUGF(1, "Found %d candidate shells containing first point of ring's originating edge %d",
6611  candidates.size, ring->elems[0]->edge->edge_id * ( ring->elems[0]->left ? 1 : -1 ) );
6612 
6613  /* TODO: sort candidates by bounding box size */
6614 
6615  for (i=0; i<candidates.size; ++i)
6616  {
6617  LWT_EDGERING *sring = candidates.rings[i];
6618  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6619  int contains = 0;
6620 
6621  if ( sring->elems[0]->edge->edge_id == ring->elems[0]->edge->edge_id )
6622  {
6623  LWDEBUGF(1, "Shell %d is on other side of ring",
6624  _lwt_EdgeRingGetFace(sring));
6625  continue;
6626  }
6627 
6628  /* The hole envelope cannot equal the shell envelope */
6629  if ( gbox_same(shellbox, testbox) )
6630  {
6631  LWDEBUGF(1, "Bbox of shell %d equals that of hole ring",
6632  _lwt_EdgeRingGetFace(sring));
6633  continue;
6634  }
6635 
6636  /* Skip if ring box is not in shell box */
6637  if ( ! gbox_contains_2d(shellbox, testbox) )
6638  {
6639  LWDEBUGF(1, "Bbox of shell %d does not contain bbox of ring point",
6640  _lwt_EdgeRingGetFace(sring));
6641  continue;
6642  }
6643 
6644  /* Skip test if a containing shell was already found
6645  * and this shell's bbox is not contained in the other */
6646  if ( minenv && ! gbox_contains_2d(minenv, shellbox) )
6647  {
6648  LWDEBUGF(2, "Bbox of shell %d (face %d) not contained by bbox "
6649  "of last shell found to contain the point",
6650  i, _lwt_EdgeRingGetFace(sring));
6651  continue;
6652  }
6653 
6654  contains = _lwt_EdgeRingContainsPoint(sring, &pt);
6655  if ( contains )
6656  {
6657  /* Continue until all shells are tested, as we want to
6658  * use the one with the smallest bounding box */
6659  /* IDEA: sort shells by bbox size, stopping on first match */
6660  LWDEBUGF(1, "Shell %d contains hole of edge %d",
6661  _lwt_EdgeRingGetFace(sring),
6662  ring->elems[0]->edge->edge_id);
6663  minenv = shellbox;
6664  foundInFace = _lwt_EdgeRingGetFace(sring);
6665  }
6666  }
6667  if ( foundInFace == -1 ) foundInFace = 0;
6668 
6669  candidates.size = 0; /* Avoid destroying the actual shell rings */
6670  LWT_EDGERING_ARRAY_CLEAN(&candidates);
6671 
6672  GEOSGeom_destroy(ghole);
6673 
6674  return foundInFace;
6675 }
int gbox_same(const GBOX *g1, const GBOX *g2)
Check if 2 given Gbox are the same.
Definition: g_box.c:171
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
char lwgeom_geos_errmsg[LWGEOM_GEOS_ERRMSG_MAXSIZE]
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, uint8_t autofix)
LWPOINT * lwpoint_make2d(int srid, double x, double y)
Definition: lwpoint.c:163
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:330
void lwpoint_free(LWPOINT *pt)
Definition: lwpoint.c:213
int getPoint2d_p(const POINTARRAY *pa, uint32_t n, POINT2D *point)
Definition: lwgeom_api.c:348
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
LWGEOM * lwpoint_as_lwgeom(const LWPOINT *obj)
Definition: lwgeom.c:335
LWLINE * lwline_construct(int srid, GBOX *bbox, POINTARRAY *points)
Definition: lwline.c:42
void ptarray_set_point4d(POINTARRAY *pa, uint32_t n, const POINT4D *p4d)
Definition: lwgeom_api.c:435
void lwline_free(LWLINE *line)
Definition: lwline.c:76
LWT_INT64 LWT_ELEMID
Identifier of topology element.
static const int STRTREE_NODE_CAPACITY
#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
static int _lwt_EdgeRingContainsPoint(LWT_EDGERING *ring, POINT2D *p)
Definition: lwgeom_topo.c:6405
static LWT_ELEMID _lwt_EdgeRingGetFace(LWT_EDGERING *ring)
Definition: lwgeom_topo.c:6437
static GBOX * _lwt_EdgeRingGetBbox(LWT_EDGERING *ring)
Definition: lwgeom_topo.c:6416
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6038
static void _lwt_AccumulateCanditates(void *item, void *userdata)
Definition: lwgeom_topo.c:6537
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6047
Datum contains(PG_FUNCTION_ARGS)
double ymax
Definition: liblwgeom.h:298
double xmax
Definition: liblwgeom.h:296
double ymin
Definition: liblwgeom.h:297
double xmin
Definition: liblwgeom.h:295
POINTARRAY * points
Definition: liblwgeom.h:425
GEOSSTRtree * tree
Definition: lwgeom_topo.c:6035
LWT_EDGERING ** rings
Definition: lwgeom_topo.c:6032
LWT_ISO_EDGE * edge
Definition: lwgeom_topo.c:5979
GEOSGeometry * genv
Definition: lwgeom_topo.c:5996
LWT_EDGERING_ELEM ** elems
Definition: lwgeom_topo.c:5989
LWLINE * geom
LWT_ELEMID edge_id
double y
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:355
double y
Definition: liblwgeom.h:355

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().

Here is the call graph for this function:
Here is the caller graph for this function: