PostGIS  2.5.0dev-r@@SVN_REVISION@@
static LWT_ELEMID _lwt_FindFaceContainingRing ( LWT_TOPOLOGY topo,
LWT_EDGERING ring,
LWT_EDGERING_ARRAY shells 
)
static

Definition at line 6747 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().

6749 {
6750  LWT_ELEMID foundInFace = -1;
6751  int i;
6752  const GBOX *minenv = NULL;
6753  POINT2D pt;
6754  const GBOX *testbox;
6755  GEOSGeometry *ghole;
6756 
6757  getPoint2d_p( ring->elems[0]->edge->geom->points, 0, &pt );
6758 
6759  testbox = _lwt_EdgeRingGetBbox(ring);
6760 
6761  /* Create a GEOS Point from a vertex of the hole ring */
6762  {
6763  LWPOINT *point = lwpoint_make2d(topo->srid, pt.x, pt.y);
6764  ghole = LWGEOM2GEOS( lwpoint_as_lwgeom(point), 1 );
6765  lwpoint_free(point);
6766  if ( ! ghole ) {
6767  lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
6768  return -1;
6769  }
6770  }
6771 
6772  /* Build STRtree of shell envelopes */
6773  if ( ! shells->tree )
6774  {
6775  static const int STRTREE_NODE_CAPACITY = 10;
6776  LWDEBUG(1, "Building STRtree");
6777  shells->tree = GEOSSTRtree_create(STRTREE_NODE_CAPACITY);
6778  if (shells->tree == NULL)
6779  {
6780  lwerror("Could not create GEOS STRTree: %s", lwgeom_geos_errmsg);
6781  return -1;
6782  }
6783  for (i=0; i<shells->size; ++i)
6784  {
6785  LWT_EDGERING *sring = shells->rings[i];
6786  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6787  LWDEBUGF(2, "GBOX of shell %p for edge %d is %g %g,%g %g",
6788  sring, sring->elems[0]->edge->edge_id, shellbox->xmin,
6789  shellbox->ymin, shellbox->xmax, shellbox->ymax);
6790  POINTARRAY *pa = ptarray_construct(0, 0, 2);
6791  POINT4D pt;
6792  LWLINE *diag;
6793  pt.x = shellbox->xmin;
6794  pt.y = shellbox->ymin;
6795  ptarray_set_point4d(pa, 0, &pt);
6796  pt.x = shellbox->xmax;
6797  pt.y = shellbox->ymax;
6798  ptarray_set_point4d(pa, 1, &pt);
6799  diag = lwline_construct(topo->srid, NULL, pa);
6800  /* Record just envelope in ggeom */
6801  /* making valid, probably not needed */
6802  sring->genv = LWGEOM2GEOS( lwline_as_lwgeom(diag), 1 );
6803  lwline_free(diag);
6804  GEOSSTRtree_insert(shells->tree, sring->genv, sring);
6805  }
6806  LWDEBUG(1, "STRtree build completed");
6807  }
6808 
6809  LWT_EDGERING_ARRAY candidates;
6810  LWT_EDGERING_ARRAY_INIT(&candidates);
6811  GEOSSTRtree_query(shells->tree, ghole, &_lwt_AccumulateCanditates, &candidates);
6812  LWDEBUGF(1, "Found %d candidate shells containing first point of ring's originating edge %d",
6813  candidates.size, ring->elems[0]->edge->edge_id * ( ring->elems[0]->left ? 1 : -1 ) );
6814 
6815  /* TODO: sort candidates by bounding box size */
6816 
6817  for (i=0; i<candidates.size; ++i)
6818  {
6819  LWT_EDGERING *sring = candidates.rings[i];
6820  const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
6821  int contains = 0;
6822 
6823  if ( sring->elems[0]->edge->edge_id == ring->elems[0]->edge->edge_id )
6824  {
6825  LWDEBUGF(1, "Shell %d is on other side of ring",
6826  _lwt_EdgeRingGetFace(sring));
6827  continue;
6828  }
6829 
6830  /* The hole envelope cannot equal the shell envelope */
6831  if ( gbox_same(shellbox, testbox) )
6832  {
6833  LWDEBUGF(1, "Bbox of shell %d equals that of hole ring",
6834  _lwt_EdgeRingGetFace(sring));
6835  continue;
6836  }
6837 
6838  /* Skip if ring box is not in shell box */
6839  if ( ! gbox_contains_2d(shellbox, testbox) )
6840  {
6841  LWDEBUGF(1, "Bbox of shell %d does not contain bbox of ring point",
6842  _lwt_EdgeRingGetFace(sring));
6843  continue;
6844  }
6845 
6846  /* Skip test if a containing shell was already found
6847  * and this shell's bbox is not contained in the other */
6848  if ( minenv && ! gbox_contains_2d(minenv, shellbox) )
6849  {
6850  LWDEBUGF(2, "Bbox of shell %d (face %d) not contained by bbox "
6851  "of last shell found to contain the point",
6852  i, _lwt_EdgeRingGetFace(sring));
6853  continue;
6854  }
6855 
6856  contains = _lwt_EdgeRingContainsPoint(sring, &pt);
6857  if ( contains )
6858  {
6859  /* Continue until all shells are tested, as we want to
6860  * use the one with the smallest bounding box */
6861  /* IDEA: sort shells by bbox size, stopping on first match */
6862  LWDEBUGF(1, "Shell %d contains hole of edge %d",
6863  _lwt_EdgeRingGetFace(sring),
6864  ring->elems[0]->edge->edge_id);
6865  minenv = shellbox;
6866  foundInFace = _lwt_EdgeRingGetFace(sring);
6867  }
6868  }
6869  if ( foundInFace == -1 ) foundInFace = 0;
6870 
6871  candidates.size = 0; /* Avoid destroying the actual shell rings */
6872  LWT_EDGERING_ARRAY_CLEAN(&candidates);
6873 
6874  GEOSGeom_destroy(ghole);
6875 
6876  return foundInFace;
6877 }
double x
Definition: liblwgeom.h:351
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:6234
double xmax
Definition: liblwgeom.h:292
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:6618
#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:6607
static const int STRTREE_NODE_CAPACITY
double x
Definition: liblwgeom.h:327
LWT_ISO_EDGE * edge
Definition: lwgeom_topo.c:6181
double ymin
Definition: liblwgeom.h:293
static LWT_ELEMID _lwt_EdgeRingGetFace(LWT_EDGERING *ring)
Definition: lwgeom_topo.c:6639
LWGEOM * lwline_as_lwgeom(const LWLINE *obj)
Definition: lwgeom.c:329
double xmin
Definition: liblwgeom.h:291
static void _lwt_AccumulateCanditates(void *item, void *userdata)
Definition: lwgeom_topo.c:6739
LWLINE * lwline_construct(int srid, GBOX *bbox, POINTARRAY *points)
Definition: lwline.c:42
#define LWT_EDGERING_ARRAY_CLEAN(a)
Definition: lwgeom_topo.c:6249
double ymax
Definition: liblwgeom.h:294
double y
Definition: liblwgeom.h:327
LWT_ELEMID edge_id
LWT_EDGERING_ELEM ** elems
Definition: lwgeom_topo.c:6191
GEOSGeometry * LWGEOM2GEOS(const LWGEOM *lwgeom, int autofix)
#define LWT_EDGERING_ARRAY_INIT(a)
Definition: lwgeom_topo.c:6240
int getPoint2d_p(const POINTARRAY *pa, uint32_t n, POINT2D *point)
Definition: lwgeom_api.c:338
GEOSGeometry * genv
Definition: lwgeom_topo.c:6198
LWGEOM * lwpoint_as_lwgeom(const LWPOINT *obj)
Definition: lwgeom.c:334
LWT_INT64 LWT_ELEMID
Identifier of topology element.
double y
Definition: liblwgeom.h:351
#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:6237
POINTARRAY * points
Definition: liblwgeom.h:421

Here is the call graph for this function:

Here is the caller graph for this function: