bool GENERIC_LOOP_ALGO()

in src/h3lib/include/polygonAlgos.h [67:140]

• 39 lines of code
• 10 McCabe index (conditional complexity)

bool GENERIC_LOOP_ALGO(pointInside)(const TYPE *loop, const BBox *bbox,
                                    const LatLng *coord) {
    // fail fast if we're outside the bounding box
    if (!bboxContains(bbox, coord)) {
        return false;
    }
    bool isTransmeridian = bboxIsTransmeridian(bbox);
    bool contains = false;

    double lat = coord->lat;
    double lng = NORMALIZE_LNG(coord->lng, isTransmeridian);

    LatLng a;
    LatLng b;

    INIT_ITERATION;

    while (true) {
        ITERATE(loop, a, b);

        // Ray casting algo requires the second point to always be higher
        // than the first, so swap if needed
        if (a.lat > b.lat) {
            LatLng tmp = a;
            a = b;
            b = tmp;
        }

        // If the latitude matches exactly, we'll hit an edge case where
        // the ray passes through the vertex twice on successive segment
        // checks. To avoid this, adjust the latiude northward if needed.
        //
        // NOTE: This currently means that a point at the north pole cannot
        // be contained in any polygon. This is acceptable in current usage,
        // because the point we test in this function at present is always
        // a cell center or vertex, and no cell has a center or vertex on the
        // north pole. If we need to expand this algo to more generic uses we
        // might need to handle this edge case.
        if (lat == a.lat || lat == b.lat) {
            lat += DBL_EPSILON;
        }

        // If we're totally above or below the latitude ranges, the test
        // ray cannot intersect the line segment, so let's move on
        if (lat < a.lat || lat > b.lat) {
            continue;
        }

        double aLng = NORMALIZE_LNG(a.lng, isTransmeridian);
        double bLng = NORMALIZE_LNG(b.lng, isTransmeridian);

        // Rays are cast in the longitudinal direction, in case a point
        // exactly matches, to decide tiebreakers, bias westerly
        if (aLng == lng || bLng == lng) {
            lng -= DBL_EPSILON;
        }

        // For the latitude of the point, compute the longitude of the
        // point that lies on the line segment defined by a and b
        // This is done by computing the percent above a the lat is,
        // and traversing the same percent in the longitudinal direction
        // of a to b
        double ratio = (lat - a.lat) / (b.lat - a.lat);
        double testLng =
            NORMALIZE_LNG(aLng + (bLng - aLng) * ratio, isTransmeridian);

        // Intersection of the ray
        if (testLng > lng) {
            contains = !contains;
        }
    }

    return contains;
}