in h3_polyfill.c [408:590]
void iterStepPolygonCompact(IterCellsPolygonCompact *iter) {
H3Index cell = iter->cell;
// once the cell is H3_NULL, the iterator returns an infinite sequence of
// H3_NULL
if (cell == H3_NULL) return;
// For the first step, we need to evaluate the current cell; after that, we
// should start with the next cell.
if (iter->_started) {
cell = nextCell(cell);
} else {
iter->_started = true;
}
// Short-circuit iteration for 0-vert polygon
if (iter->_polygon->geoloop.numVerts == 0) {
iterDestroyPolygonCompact(iter);
return;
}
ContainmentMode mode = FLAG_GET_CONTAINMENT_MODE(iter->_flags);
while (cell) {
int cellRes = H3_GET_RESOLUTION(cell);
// Target res: Do a fine-grained check
if (cellRes == iter->_res) {
if (mode == CONTAINMENT_CENTER || mode == CONTAINMENT_OVERLAPPING ||
mode == CONTAINMENT_OVERLAPPING_BBOX) {
// Check if the cell center is inside the polygon
LatLng center;
H3Error centerErr = H3_EXPORT(cellToLatLng)(cell, ¢er);
if (centerErr != E_SUCCESS) {
iterErrorPolygonCompact(iter, centerErr);
return;
}
if (pointInsidePolygon(iter->_polygon, iter->_bboxes,
¢er)) {
// Set to next output
iter->cell = cell;
return;
}
}
if (mode == CONTAINMENT_OVERLAPPING ||
mode == CONTAINMENT_OVERLAPPING_BBOX) {
// For overlapping, we need to do a quick check to determine
// whether the polygon is wholly contained by the cell. We
// check the first polygon vertex, which if it is contained
// could also mean we simply intersect.
// Deferencing verts[0] is safe because we check numVerts above
LatLng firstVertex = iter->_polygon->geoloop.verts[0];
// We have to check whether the point is in the expected range
// first, because out-of-bounds values will yield false
// positives with latLngToCell
if (bboxContains(&VALID_RANGE_BBOX, &firstVertex)) {
H3Index polygonCell;
H3Error polygonCellErr = H3_EXPORT(latLngToCell)(
&(iter->_polygon->geoloop.verts[0]), cellRes,
&polygonCell);
if (NEVER(polygonCellErr != E_SUCCESS)) {
// This should be unreachable with the bbox check
iterErrorPolygonCompact(iter, polygonCellErr);
return;
}
if (polygonCell == cell) {
// Set to next output
iter->cell = cell;
return;
}
}
}
if (mode == CONTAINMENT_FULL || mode == CONTAINMENT_OVERLAPPING ||
mode == CONTAINMENT_OVERLAPPING_BBOX) {
CellBoundary boundary;
H3Error boundaryErr =
H3_EXPORT(cellToBoundary)(cell, &boundary);
if (boundaryErr != E_SUCCESS) {
iterErrorPolygonCompact(iter, boundaryErr);
return;
}
BBox bbox;
H3Error bboxErr = cellToBBox(cell, &bbox, false);
if (NEVER(bboxErr != E_SUCCESS)) {
// Should be unreachable - invalid cells would be caught in
// the previous boundaryErr
iterErrorPolygonCompact(iter, bboxErr);
return;
}
// Check if the cell is fully contained by the polygon
if ((mode == CONTAINMENT_FULL ||
mode == CONTAINMENT_OVERLAPPING_BBOX) &&
cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes,
&boundary, &bbox)) {
// Set to next output
iter->cell = cell;
return;
}
// For overlap, we've already checked for center point inclusion
// above; if that failed, we only need to check for line
// intersection
else if ((mode == CONTAINMENT_OVERLAPPING ||
mode == CONTAINMENT_OVERLAPPING_BBOX) &&
cellBoundaryCrossesPolygon(
iter->_polygon, iter->_bboxes, &boundary, &bbox)) {
// Set to next output
iter->cell = cell;
return;
}
}
if (mode == CONTAINMENT_OVERLAPPING_BBOX) {
// Get a bounding box containing all the cell's children, so
// this can work for the max size calculation
BBox bbox;
H3Error bboxErr = cellToBBox(cell, &bbox, true);
if (bboxErr) {
iterErrorPolygonCompact(iter, bboxErr);
return;
}
if (bboxOverlapsBBox(&iter->_bboxes[0], &bbox)) {
CellBoundary bboxBoundary = bboxToCellBoundary(&bbox);
if (
// cell bbox contains the polygon
bboxContainsBBox(&bbox, &iter->_bboxes[0]) ||
// polygon contains cell bbox
pointInsidePolygon(iter->_polygon, iter->_bboxes,
&bboxBoundary.verts[0]) ||
// polygon crosses cell bbox
cellBoundaryCrossesPolygon(iter->_polygon,
iter->_bboxes, &bboxBoundary,
&bbox)) {
iter->cell = cell;
return;
}
}
}
}
// Coarser cell: Check the bounding box
if (cellRes < iter->_res) {
// Get a bounding box for all of the cell's children
BBox bbox;
H3Error bboxErr = cellToBBox(cell, &bbox, true);
if (bboxErr) {
iterErrorPolygonCompact(iter, bboxErr);
return;
}
if (bboxOverlapsBBox(&iter->_bboxes[0], &bbox)) {
// Quick check for possible containment
if (bboxContainsBBox(&iter->_bboxes[0], &bbox)) {
CellBoundary bboxBoundary = bboxToCellBoundary(&bbox);
// Do a fine-grained, more expensive check on the polygon
if (cellBoundaryInsidePolygon(iter->_polygon, iter->_bboxes,
&bboxBoundary, &bbox)) {
// Bounding box is fully contained, so all children are
// included. Set to next output.
iter->cell = cell;
return;
}
}
// Otherwise, the intersecting bbox means we need to test all
// children, starting with the first child
H3Index child;
H3Error childErr =
H3_EXPORT(cellToCenterChild)(cell, cellRes + 1, &child);
if (childErr) {
iterErrorPolygonCompact(iter, childErr);
return;
}
// Restart the loop with the child cell
cell = child;
continue;
}
}
// Find the next cell in the sequence of all cells and continue
cell = nextCell(cell);
}
// If we make it out of the loop, we're done
iterDestroyPolygonCompact(iter);
}