_lwt_FindFaceContainingRing()

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

static

Definition at line 6620 of file lwgeom_topo.c.

{
  LWT_ELEMID foundInFace = -1;
  int i;
  const GBOX *minenv = NULL;
  POINT2D pt;
  const GBOX *testbox;
  GEOSGeometry *ghole;
 
  getPoint2d_p( ring->elems[0]->edge->geom->points, 0, &pt );
 
  testbox = _lwt_EdgeRingGetBbox(ring);
 
  /* Create a GEOS Point from a vertex of the hole ring */
  {
    LWPOINT *point = lwpoint_make2d(topo->srid, pt.x, pt.y);
    ghole = LWGEOM2GEOS( lwpoint_as_lwgeom(point), 1 );
    lwpoint_free(point);
    if ( ! ghole ) {
      lwerror("Could not convert edge geometry to GEOS: %s", lwgeom_geos_errmsg);
      return -1;
    }
  }
 
  /* Build STRtree of shell envelopes */
  if ( ! shells->tree )
  {
    static const int STRTREE_NODE_CAPACITY = 10;
    LWDEBUG(1, "Building STRtree");
          shells->tree = GEOSSTRtree_create(STRTREE_NODE_CAPACITY);
    if (shells->tree == NULL)
    {
      lwerror("Could not create GEOS STRTree: %s", lwgeom_geos_errmsg);
      return -1;
    }
    for (i=0; i<shells->size; ++i)
    {
      LWT_EDGERING *sring = shells->rings[i];
      const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
      LWDEBUGF(2, "GBOX of shell %p for edge %d is %g %g,%g %g",
        sring, sring->elems[0]->edge->edge_id, shellbox->xmin,
        shellbox->ymin, shellbox->xmax, shellbox->ymax);
      POINTARRAY *pa = ptarray_construct(0, 0, 2);
      POINT4D pt;
      LWLINE *diag;
      pt.x = shellbox->xmin;
      pt.y = shellbox->ymin;
      ptarray_set_point4d(pa, 0, &pt);
      pt.x = shellbox->xmax;
      pt.y = shellbox->ymax;
      ptarray_set_point4d(pa, 1, &pt);
      diag = lwline_construct(topo->srid, NULL, pa);
      /* Record just envelope in ggeom */
      /* making valid, probably not needed */
      sring->genv = LWGEOM2GEOS( lwline_as_lwgeom(diag), 1 );
      lwline_free(diag);
      GEOSSTRtree_insert(shells->tree, sring->genv, sring);
    }
    LWDEBUG(1, "STRtree build completed");
  }
 
  LWT_EDGERING_ARRAY candidates;
  LWT_EDGERING_ARRAY_INIT(&candidates);
        GEOSSTRtree_query(shells->tree, ghole, &_lwt_AccumulateCanditates, &candidates);
  LWDEBUGF(1, "Found %d candidate shells containing first point of ring's originating edge %d",
          candidates.size, ring->elems[0]->edge->edge_id * ( ring->elems[0]->left ? 1 : -1 ) );
 
  /* TODO: sort candidates by bounding box size */
 
  for (i=0; i<candidates.size; ++i)
  {
    LWT_EDGERING *sring = candidates.rings[i];
    const GBOX* shellbox = _lwt_EdgeRingGetBbox(sring);
    int contains = 0;
 
    if ( sring->elems[0]->edge->edge_id == ring->elems[0]->edge->edge_id )
    {
      LWDEBUGF(1, "Shell %d is on other side of ring",
               _lwt_EdgeRingGetFace(sring));
      continue;
    }
 
    /* The hole envelope cannot equal the shell envelope */
    if ( gbox_same(shellbox, testbox) )
    {
      LWDEBUGF(1, "Bbox of shell %d equals that of hole ring",
               _lwt_EdgeRingGetFace(sring));
      continue;
    }
 
    /* Skip if ring box is not in shell box */
    if ( ! gbox_contains_2d(shellbox, testbox) )
    {
      LWDEBUGF(1, "Bbox of shell %d does not contain bbox of ring point",
               _lwt_EdgeRingGetFace(sring));
      continue;
    }
 
    /* Skip test if a containing shell was already found
     * and this shell's bbox is not contained in the other */
    if ( minenv && ! gbox_contains_2d(minenv, shellbox) )
    {
      LWDEBUGF(2, "Bbox of shell %d (face %d) not contained by bbox "
                  "of last shell found to contain the point",
                  i, _lwt_EdgeRingGetFace(sring));
      continue;
    }
 
    contains = _lwt_EdgeRingContainsPoint(sring, &pt);
    if ( contains )
    {
      /* Continue until all shells are tested, as we want to
       * use the one with the smallest bounding box */
      /* IDEA: sort shells by bbox size, stopping on first match */
      LWDEBUGF(1, "Shell %d contains hole of edge %d",
               _lwt_EdgeRingGetFace(sring),
               ring->elems[0]->edge->edge_id);
      minenv = shellbox;
      foundInFace = _lwt_EdgeRingGetFace(sring);
    }
  }
  if ( foundInFace == -1 ) foundInFace = 0;
 
  candidates.size = 0; /* Avoid destroying the actual shell rings */
  LWT_EDGERING_ARRAY_CLEAN(&candidates);
 
  GEOSGeom_destroy(ghole);
 
  return foundInFace;
}

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: