path: root/src/mongo/db/geo/geoquery.cpp

/**
 *    Copyright (C) 2013 MongoDB Inc.
 *
 *    This program is free software: you can redistribute it and/or  modify
 *    it under the terms of the GNU Affero General Public License, version 3,
 *    as published by the Free Software Foundation.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU Affero General Public License for more details.
 *
 *    You should have received a copy of the GNU Affero General Public License
 *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *    As a special exception, the copyright holders give permission to link the
 *    code of portions of this program with the OpenSSL library under certain
 *    conditions as described in each individual source file and distribute
 *    linked combinations including the program with the OpenSSL library. You
 *    must comply with the GNU Affero General Public License in all respects for
 *    all of the code used other than as permitted herein. If you modify file(s)
 *    with this exception, you may extend this exception to your version of the
 *    file(s), but you are not obligated to do so. If you do not wish to do so,
 *    delete this exception statement from your version. If you delete this
 *    exception statement from all source files in the program, then also delete
 *    it in the license file.
 */

#include "mongo/db/geo/geoquery.h"

#include "mongo/db/geo/geoconstants.h"

namespace mongo {

    using mongoutils::str::equals;

    bool NearQuery::parseLegacyQuery(const BSONObj &obj) {
        bool hasGeometry = false;

        // First, try legacy near, e.g.:
        // t.find({ loc : { $nearSphere: [0,0], $minDistance: 1, $maxDistance: 3 }})
        // t.find({ loc : { $nearSphere: [0,0] }})
        // t.find({ loc : { $near: { someGeoJSONPoint}})
        // t.find({ loc : { $geoNear: { someGeoJSONPoint}})
        BSONObjIterator it(obj);
        while (it.more()) {
            BSONElement e = it.next();
            if (equals(e.fieldName(), "$near") || equals(e.fieldName(), "$geoNear")
                                               || equals(e.fieldName(), "$nearSphere")) {
                if (!e.isABSONObj()) { return false; }
                BSONObj embeddedObj = e.embeddedObject();

                if ((GeoParser::isPoint(embeddedObj) && GeoParser::parsePoint(embeddedObj, &centroid))
                    || GeoParser::parsePointWithMaxDistance(embeddedObj, &centroid, &maxDistance)) {
                    hasGeometry = true;
                    isNearSphere = equals(e.fieldName(), "$nearSphere");
                }
            } else if (equals(e.fieldName(), "$minDistance")) {
                uassert(16893, "$minDistance must be a number", e.isNumber());
                minDistance = e.Number();
                uassert(16894, "$minDistance must be non-negative", minDistance >= 0.0);
            } else if (equals(e.fieldName(), "$maxDistance")) {
                uassert(16895, "$maxDistance must be a number", e.isNumber());
                maxDistance = e.Number();
                uassert(16896, "$maxDistance must be non-negative", maxDistance >= 0.0);
            } else if (equals(e.fieldName(), "$uniqueDocs")) {
                warning() << "ignoring deprecated option $uniqueDocs";
            }
        }

        // The user-provided point can be flat.  We need to make sure that it's in bounds.
        if (isNearSphere) {
            uassert(17444,
                    "Legacy point is out of bounds for spherical query",
                    centroid.flatUpgradedToSphere || (SPHERE == centroid.crs));
        }

        return hasGeometry;
    }

    Status NearQuery::parseNewQuery(const BSONObj &obj) {
        bool hasGeometry = false;

        BSONObjIterator objIt(obj);
        if (!objIt.more()) {
            return Status(ErrorCodes::BadValue, "empty geo near query object");
        }
        BSONElement e = objIt.next();
        // Just one arg. to $geoNear.
        if (objIt.more()) {
            return Status(ErrorCodes::BadValue, mongoutils::str::stream() <<
                          "geo near accepts just one argument when querying for a GeoJSON " <<
                          "point. Extra field found: " << objIt.next());
        }

        // Parse "new" near:
        // t.find({"geo" : {"$near" : {"$geometry": pointA, $minDistance: 1, $maxDistance: 3}}})
        // t.find({"geo" : {"$geoNear" : {"$geometry": pointA, $minDistance: 1, $maxDistance: 3}}})
        if (!e.isABSONObj()) {
            return Status(ErrorCodes::BadValue, "geo near query argument is not an object");
        }
        BSONObj::MatchType matchType = static_cast<BSONObj::MatchType>(e.getGtLtOp());
        if (BSONObj::opNEAR != matchType) {
            return Status(ErrorCodes::BadValue, mongoutils::str::stream() <<
                          "invalid geo near query operator: " << e.fieldName());
        }

        // Iterate over the argument.
        BSONObjIterator it(e.embeddedObject());
        while (it.more()) {
            BSONElement e = it.next();
            if (equals(e.fieldName(), "$geometry")) {
                if (e.isABSONObj()) {
                    BSONObj embeddedObj = e.embeddedObject();
                    uassert(16885, "$near requires a point, given " + embeddedObj.toString(),
                            GeoParser::isPoint(embeddedObj));
                    if (!GeoParser::parsePoint(embeddedObj, &centroid)) {
                        return Status(ErrorCodes::BadValue, mongoutils::str::stream() <<
                                      "invalid point in geo near query $geometry argument: " <<
                                      embeddedObj);
                    }
                    uassert(16681, "$near requires geojson point, given " + embeddedObj.toString(),
                            (SPHERE == centroid.crs));
                    hasGeometry = true;
                }
            } else if (equals(e.fieldName(), "$minDistance")) {
                uassert(16897, "$minDistance must be a number", e.isNumber());
                minDistance = e.Number();
                uassert(16898, "$minDistance must be non-negative", minDistance >= 0.0);
            } else if (equals(e.fieldName(), "$maxDistance")) {
                uassert(16899, "$maxDistance must be a number", e.isNumber());
                maxDistance = e.Number();
                uassert(16900, "$maxDistance must be non-negative", maxDistance >= 0.0);
            }
        }

        if (!hasGeometry) {
            return Status(ErrorCodes::BadValue, "$geometry is required for geo near query");
        }

        return Status::OK();
    }


    Status NearQuery::parseFrom(const BSONObj &obj) {
        if (parseLegacyQuery(obj)) {
            return Status::OK();
        }
        // Clear out any half-baked data.
        minDistance = 0;
        isNearSphere = false;
        maxDistance = std::numeric_limits<double>::max();
        centroid = PointWithCRS();
        // And try parsing new format.
        return parseNewQuery(obj);
    }

    bool GeoQuery::parseLegacyQuery(const BSONObj &obj) {
        // The only legacy syntax is {$within: {.....}}
        BSONObjIterator outerIt(obj);
        if (!outerIt.more()) { return false; }
        BSONElement withinElt = outerIt.next();
        if (outerIt.more()) { return false; }
        if (!withinElt.isABSONObj()) { return false; }
        if (!equals(withinElt.fieldName(), "$within") && !equals(withinElt.fieldName(), "$geoWithin")) {
            return false;
        }
        BSONObj withinObj = withinElt.embeddedObject();

        bool hasGeometry = false;

        BSONObjIterator withinIt(withinObj);
        while (withinIt.more()) {
            BSONElement elt = withinIt.next();
            if (equals(elt.fieldName(), "$uniqueDocs")) {
                warning() << "deprecated $uniqueDocs option: " << obj.toString() << endl;
                // return false;
            }
            else if (elt.isABSONObj()) {
                hasGeometry = geoContainer.parseFrom(elt.wrap());
            }
            else {
                warning() << "bad geo query: " << obj.toString() << endl;
                return false;
            }
        }

        predicate = GeoQuery::WITHIN;

        return hasGeometry;
    }

    bool GeoQuery::parseNewQuery(const BSONObj &obj) {
        // pointA = { "type" : "Point", "coordinates": [ 40, 5 ] }
        // t.find({ "geo" : { "$intersect" : { "$geometry" : pointA} } })
        // t.find({ "geo" : { "$within" : { "$geometry" : polygon } } })
        // where field.name is "geo"
        BSONElement e = obj.firstElement();
        if (!e.isABSONObj()) { return false; }

        BSONObj::MatchType matchType = static_cast<BSONObj::MatchType>(e.getGtLtOp());
        if (BSONObj::opGEO_INTERSECTS == matchType) {
            predicate = GeoQuery::INTERSECT;
        } else if (BSONObj::opWITHIN == matchType) {
            predicate = GeoQuery::WITHIN;
        } else {
            return false;
        }

        bool hasGeometry = false;
        BSONObjIterator argIt(e.embeddedObject());
        while (argIt.more()) {
            BSONElement e = argIt.next();
            if (mongoutils::str::equals(e.fieldName(), "$geometry")) {
                if (e.isABSONObj()) {
                    BSONObj embeddedObj = e.embeddedObject();
                     if (geoContainer.parseFrom(embeddedObj)) {
                         hasGeometry = true;
                     }
                }
            }
        }

        // Don't want to give the error below if we could not pull any geometry out.
        if (!hasGeometry) { return false; }

        if (GeoQuery::WITHIN == predicate) {
            // Why do we only deal with $within {polygon}?
            // 1. Finding things within a point is silly and only valid
            // for points and degenerate lines/polys.
            //
            // 2. Finding points within a line is easy but that's called intersect.
            // Finding lines within a line is kind of tricky given what S2 gives us.
            // Doing line-within-line is a valid yet unsupported feature,
            // though I wonder if we want to preserve orientation for lines or
            // allow (a,b),(c,d) to be within (c,d),(a,b).  Anyway, punt on
            // this for now.
            uassert(16672, "$within not supported with provided geometry: " + obj.toString(),
                    geoContainer.supportsContains());
        }

        return hasGeometry;
    }

    bool GeoQuery::parseFrom(const BSONObj &obj) {
        return parseLegacyQuery(obj) || parseNewQuery(obj);
    }

    const S2Region& GeoQuery::getRegion() const {
        return geoContainer.getRegion();
    }

    bool GeoQuery::hasS2Region() const {
        return geoContainer.hasS2Region();
    }

    bool GeometryContainer::isSimpleContainer() const {
        return NULL != _point || NULL != _line || NULL != _polygon;
    }

    bool GeometryContainer::supportsContains() const {
        return NULL != _polygon
               || NULL != _cap
               || NULL != _multiPolygon
               || (NULL != _geometryCollection
                   && (_geometryCollection->polygons.vector().size() > 0
                       || _geometryCollection->multiPolygons.vector().size() > 0));
    }

    bool GeometryContainer::hasS2Region() const {
        return (NULL != _point && (_point->crs == SPHERE || _point->flatUpgradedToSphere))
               || NULL != _line
               || (NULL != _polygon && _polygon->crs == SPHERE)
               || (NULL != _cap && _cap->crs == SPHERE)
               || NULL != _multiPoint
               || NULL != _multiLine
               || NULL != _multiPolygon
               || NULL != _geometryCollection;
    }

    bool GeometryContainer::hasFlatRegion() const {
        return (NULL != _polygon && _polygon->crs == FLAT)
               || (NULL != _cap && _cap->crs == FLAT)
               || NULL != _box;
    }

    bool GeoQuery::satisfiesPredicate(const GeometryContainer &otherContainer) const {
        verify(predicate == WITHIN || predicate == INTERSECT);

        if (WITHIN == predicate) {
            return geoContainer.contains(otherContainer);
        } else {
            return geoContainer.intersects(otherContainer);
        }
    }

    bool GeometryContainer::contains(const GeometryContainer& otherContainer) const {
        // First let's deal with the case where we are FLAT.
        if (NULL != _polygon && (FLAT == _polygon->crs)) {
            if (NULL == otherContainer._point) { return false; }
            return _polygon->oldPolygon.contains(otherContainer._point->oldPoint);
        }

        if (NULL != _box) {
            verify(FLAT == _box->crs);
            if (NULL == otherContainer._point) { return false; }
            return _box->box.inside(otherContainer._point->oldPoint);
        }

        if (NULL != _cap && (FLAT == _cap->crs)) {
            if (NULL == otherContainer._point) { return false; }
            // Let's be as consistent epsilon-wise as we can with the '2d' indextype.
            return distanceWithin(_cap->circle.center, otherContainer._point->oldPoint,
                                  _cap->circle.radius);
        }

        // Now we deal with all the SPHERE stuff.

        // Iterate over the other thing and see if we contain it all.
        if (NULL != otherContainer._point) {
            // The point must be valid lng, lat if it was old-style.
            if (FLAT == otherContainer._point->crs
                && !otherContainer._point->flatUpgradedToSphere) {
                return false;
            }
            return contains(otherContainer._point->cell, otherContainer._point->point);
        }

        if (NULL != otherContainer._line) {
            return contains(otherContainer._line->line);
        }

        if (NULL != otherContainer._polygon) {
            return contains(otherContainer._polygon->polygon);
        }

        if (NULL != otherContainer._multiPoint) {
            for (size_t i = 0; i < otherContainer._multiPoint->points.size(); ++i) {
                if (!contains(otherContainer._multiPoint->cells[i],
                              otherContainer._multiPoint->points[i])) {
                    return false;
                }
            }
            return true;
        }

        if (NULL != otherContainer._multiLine) {
            const vector<S2Polyline*>& lines = otherContainer._multiLine->lines.vector();
            for (size_t i = 0; i < lines.size(); ++i) {
                if (!contains(*lines[i])) { return false; }
            }
            return true;
        }

        if (NULL != otherContainer._multiPolygon) {
            const vector<S2Polygon*>& polys = otherContainer._multiPolygon->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (!contains(*polys[i])) { return false; }
            }
            return true;
        }

        if (NULL != otherContainer._geometryCollection) {
            GeometryCollection& c = *otherContainer._geometryCollection;

            for (size_t i = 0; i < c.points.size(); ++i) {
                if (!contains(c.points[i].cell, c.points[i].point)) {
                    return false;
                }
            }

            const vector<LineWithCRS*>& lines = c.lines.vector();
            for (size_t i = 0; i < lines.size(); ++i) {
                if (!contains(lines[i]->line)) { return false; }
            }

            const vector<PolygonWithCRS*>& polys = c.polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (!contains(polys[i]->polygon)) { return false; }
            }

            const vector<MultiPointWithCRS*>& multipoints = c.multiPoints.vector();
            for (size_t i = 0; i < multipoints.size(); ++i) {
                MultiPointWithCRS* mp = multipoints[i];
                for (size_t j = 0; j < mp->points.size(); ++j) {
                    if (!contains(mp->cells[j], mp->points[j])) { return false; }
                }
            }

            const vector<MultiLineWithCRS*>& multilines = c.multiLines.vector();
            for (size_t i = 0; i < multilines.size(); ++i) {
                const vector<S2Polyline*>& lines = multilines[i]->lines.vector();
                for (size_t j = 0; j < lines.size(); ++j) {
                    if (!contains(*lines[j])) { return false; }
                }
            }

            const vector<MultiPolygonWithCRS*>& multipolys = c.multiPolygons.vector();
            for (size_t i = 0; i < multipolys.size(); ++i) {
                const vector<S2Polygon*>& polys = multipolys[i]->polygons.vector();
                for (size_t j = 0; j < polys.size(); ++j) {
                    if (!contains(*polys[j])) { return false; }
                }
            }

            return true;
        }

        return false;
    }

    bool containsPoint(const S2Polygon& poly, const S2Cell& otherCell, const S2Point& otherPoint) {
        // This is much faster for actual containment checking.
        if (poly.Contains(otherPoint)) { return true; }
        // This is slower but contains edges/vertices.
        return poly.MayIntersect(otherCell);
    }

    bool GeometryContainer::contains(const S2Cell& otherCell, const S2Point& otherPoint) const {
        if (NULL != _polygon && (_polygon->crs == SPHERE)) {
            return containsPoint(_polygon->polygon, otherCell, otherPoint);
        }

        if (NULL != _cap && (_cap->crs == SPHERE)) {
            return _cap->cap.MayIntersect(otherCell);
        }

        if (NULL != _multiPolygon) {
            const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsPoint(*polys[i], otherCell, otherPoint)) { return true; }
            }
        }

        if (NULL != _geometryCollection) {
            const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsPoint(polys[i]->polygon, otherCell, otherPoint)) { return true; }
            }
            
            const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector();
            for (size_t i = 0; i < multipolys.size(); ++i) {
                const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector();
                for (size_t j = 0; j < innerpolys.size(); ++j) {
                    if (containsPoint(*innerpolys[j], otherCell, otherPoint)) { return true; }
                }
            }
        }

        return false;
    }

    bool containsLine(const S2Polygon& poly, const S2Polyline& otherLine) {
        // Kind of a mess.  We get a function for clipping the line to the
        // polygon.  We do this and make sure the line is the same as the
        // line we're clipping against.
        OwnedPointerVector<S2Polyline> clippedOwned;
        vector<S2Polyline*>& clipped = clippedOwned.mutableVector();

        poly.IntersectWithPolyline(&otherLine, &clipped);
        if (1 != clipped.size()) { return false; }

        // If the line is entirely contained within the polygon, we should be
        // getting it back verbatim, so really there should be no error.
        bool ret = clipped[0]->NearlyCoversPolyline(otherLine,
                S1Angle::Degrees(1e-10));

        return ret;
    }

    bool GeometryContainer::contains(const S2Polyline& otherLine) const {
        if (NULL != _polygon && (_polygon->crs == SPHERE)) {
            return containsLine(_polygon->polygon, otherLine);
        }

        if (NULL != _multiPolygon) {
            const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsLine(*polys[i], otherLine)) { return true; }
            }
        }

        if (NULL != _geometryCollection) {
            const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsLine(polys[i]->polygon, otherLine)) { return true; }
            }
            
            const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector();
            for (size_t i = 0; i < multipolys.size(); ++i) {
                const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector();
                for (size_t j = 0; j < innerpolys.size(); ++j) {
                    if (containsLine(*innerpolys[j], otherLine)) { return true; }
                }
            }
        }

        return false;
    }

    bool containsPolygon(const S2Polygon& poly, const S2Polygon& otherPoly) {
        return poly.Contains(&otherPoly);
    }

    bool GeometryContainer::contains(const S2Polygon& otherPolygon) const {
        if (NULL != _polygon && (_polygon->crs == SPHERE)) {
            return containsPolygon(_polygon->polygon, otherPolygon);
        }

        if (NULL != _multiPolygon) {
            const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsPolygon(*polys[i], otherPolygon)) { return true; }
            }
        }

        if (NULL != _geometryCollection) {
            const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (containsPolygon(polys[i]->polygon, otherPolygon)) { return true; }
            }
            
            const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector();
            for (size_t i = 0; i < multipolys.size(); ++i) {
                const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector();
                for (size_t j = 0; j < innerpolys.size(); ++j) {
                    if (containsPolygon(*innerpolys[j], otherPolygon)) { return true; }
                }
            }
        }

        return false;
    }

    bool GeometryContainer::intersects(const GeometryContainer& otherContainer) const {
        if (NULL != otherContainer._point) {
            // The point must be valid lng, lat if it was old-style.
            if (FLAT == otherContainer._point->crs
                && !otherContainer._point->flatUpgradedToSphere) {
                return false;
            }
            return intersects(otherContainer._point->cell);
        } else if (NULL != otherContainer._line) {
            return intersects(otherContainer._line->line);
        } else if (NULL != otherContainer._polygon) {
            if (SPHERE != otherContainer._polygon->crs) { return false; }
            return intersects(otherContainer._polygon->polygon);
        } else if (NULL != otherContainer._multiPoint) {
            return intersects(*otherContainer._multiPoint);
        } else if (NULL != otherContainer._multiLine) {
            return intersects(*otherContainer._multiLine);
        } else if (NULL != otherContainer._multiPolygon) {
            return intersects(*otherContainer._multiPolygon);
        } else if (NULL != otherContainer._geometryCollection) {
            const GeometryCollection& c = *otherContainer._geometryCollection;

            for (size_t i = 0; i < c.points.size(); ++i) {
                if (intersects(c.points[i].cell)) { return true; }
            }

            for (size_t i = 0; i < c.polygons.vector().size(); ++i) {
                if (intersects(c.polygons.vector()[i]->polygon)) { return true; }
            }

            for (size_t i = 0; i < c.lines.vector().size(); ++i) {
                if (intersects(c.lines.vector()[i]->line)) { return true; }
            }

            for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) {
                if (intersects(*c.multiPolygons.vector()[i])) { return true; }
            }

            for (size_t i = 0; i < c.multiLines.vector().size(); ++i) {
                if (intersects(*c.multiLines.vector()[i])) { return true; }
            }

            for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) {
                if (intersects(*c.multiPoints.vector()[i])) { return true; }
            }
        }

        return false;
    }

    bool GeometryContainer::intersects(const MultiPointWithCRS& otherMultiPoint) const {
        for (size_t i = 0; i < otherMultiPoint.cells.size(); ++i) {
            if (intersects(otherMultiPoint.cells[i])) { return true; }
        }
        return false;
    }

    bool GeometryContainer::intersects(const MultiLineWithCRS& otherMultiLine) const {
        for (size_t i = 0; i < otherMultiLine.lines.vector().size(); ++i) {
            if (intersects(*otherMultiLine.lines.vector()[i])) { return true; }
        }
        return false;
    }

    bool GeometryContainer::intersects(const MultiPolygonWithCRS& otherMultiPolygon) const {
        for (size_t i = 0; i < otherMultiPolygon.polygons.vector().size(); ++i) {
            if (intersects(*otherMultiPolygon.polygons.vector()[i])) { return true; }
        }
        return false;
    }

    // Does this (GeometryContainer) intersect the provided data?
    bool GeometryContainer::intersects(const S2Cell &otherPoint) const {
        if (NULL != _point) {
            // The point must be valid lng, lat if it was old-style.
            if (FLAT == _point->crs && !_point->flatUpgradedToSphere) {
                return false;
            }
            return _point->cell.MayIntersect(otherPoint);
        } else if (NULL != _line) {
            return _line->line.MayIntersect(otherPoint);
        } else if (NULL != _polygon) {
            return _polygon->polygon.MayIntersect(otherPoint);
        } else if (NULL != _multiPoint) {
            const vector<S2Cell>& cells = _multiPoint->cells;
            for (size_t i = 0; i < cells.size(); ++i) {
                if (cells[i].MayIntersect(otherPoint)) { return true; }
            }
        } else if (NULL != _multiLine) {
            const vector<S2Polyline*>& lines = _multiLine->lines.vector();
            for (size_t i = 0; i < lines.size(); ++i) {
                if (lines[i]->MayIntersect(otherPoint)) { return true; }
            }
        } else if (NULL != _multiPolygon) {
            const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector();
            for (size_t i = 0; i < polys.size(); ++i) {
                if (polys[i]->MayIntersect(otherPoint)) { return true; }
            }
        } else if (NULL != _geometryCollection) {
            const GeometryCollection& c = *_geometryCollection;

            for (size_t i = 0; i < c.points.size(); ++i) {
                if (c.points[i].cell.MayIntersect(otherPoint)) { return true; }
            }

            for (size_t i = 0; i < c.polygons.vector().size(); ++i) {
                if (c.polygons.vector()[i]->polygon.MayIntersect(otherPoint)) { return true; }
            }

            for (size_t i = 0; i < c.lines.vector().size(); ++i) {
                if (c.lines.vector()[i]->line.MayIntersect(otherPoint)) { return true; }
            }

            for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) {
                const vector<S2Polygon*>& innerPolys =
                    c.multiPolygons.vector()[i]->polygons.vector();
                for (size_t j = 0; j < innerPolys.size(); ++j) {
                    if (innerPolys[j]->MayIntersect(otherPoint)) { return true; }
                }
            }

            for (size_t i = 0; i < c.multiLines.vector().size(); ++i) {
                const vector<S2Polyline*>& innerLines =
                    c.multiLines.vector()[i]->lines.vector();
                for (size_t j = 0; j < innerLines.size(); ++j) {
                    if (innerLines[j]->MayIntersect(otherPoint)) { return true; }
                }
            }

            for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) {
                const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells;
                for (size_t j = 0; j < innerCells.size(); ++j) {
                    if (innerCells[j].MayIntersect(otherPoint)) { return true; }
                }
            }
        }

        return false;
    }

    bool polygonLineIntersection(const S2Polyline& line, const S2Polygon& poly) {
        // TODO(hk): modify s2 library to just let us know if it intersected
        // rather than returning all this.
        vector<S2Polyline*> clipped;
        poly.IntersectWithPolyline(&line, &clipped);
        bool ret = clipped.size() > 0;
        for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i];
        return ret;
    }

    bool GeometryContainer::intersects(const S2Polyline& otherLine) const {
        if (NULL != _point) {
            // The point must be valid lng, lat if it was old-style.
            if (FLAT == _point->crs && !_point->flatUpgradedToSphere) {
                return false;
            }
            return otherLine.MayIntersect(_point->cell);
        } else if (NULL != _line) {
            return otherLine.Intersects(&_line->line);
        } else if (NULL != _polygon && (_polygon->crs == SPHERE)) {
            return polygonLineIntersection(otherLine, _polygon->polygon);
        } else if (NULL != _multiPoint) {
            for (size_t i = 0; i < _multiPoint->cells.size(); ++i) {
                if (otherLine.MayIntersect(_multiPoint->cells[i])) { return true; }
            }
        } else if (NULL != _multiLine) {
            for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) {
                if (otherLine.Intersects(_multiLine->lines.vector()[i])) {
                    return true;
                }
            }
        } else if (NULL != _multiPolygon) {
            for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) {
                if (polygonLineIntersection(otherLine, *_multiPolygon->polygons.vector()[i])) {
                    return true;
                }
            }
        } else if (NULL != _geometryCollection) {
            const GeometryCollection& c = *_geometryCollection;

            for (size_t i = 0; i < c.points.size(); ++i) {
                if (otherLine.MayIntersect(c.points[i].cell)) { return true; }
            }

            for (size_t i = 0; i < c.polygons.vector().size(); ++i) {
                if (polygonLineIntersection(otherLine, c.polygons.vector()[i]->polygon)) {
                    return true;
                }
            }

            for (size_t i = 0; i < c.lines.vector().size(); ++i) {
                if (c.lines.vector()[i]->line.Intersects(&otherLine)) { return true; }
            }

            for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) {
                const vector<S2Polygon*>& innerPolys =
                    c.multiPolygons.vector()[i]->polygons.vector();
                for (size_t j = 0; j < innerPolys.size(); ++j) {
                    if (polygonLineIntersection(otherLine, *innerPolys[j])) {
                        return true;
                    }
                }
            }

            for (size_t i = 0; i < c.multiLines.vector().size(); ++i) {
                const vector<S2Polyline*>& innerLines =
                    c.multiLines.vector()[i]->lines.vector();
                for (size_t j = 0; j < innerLines.size(); ++j) {
                    if (innerLines[j]->Intersects(&otherLine)) { return true; }
                }
            }

            for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) {
                const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells;
                for (size_t j = 0; j < innerCells.size(); ++j) {
                    if (otherLine.MayIntersect(innerCells[j])) { return true; }
                }
            }
        }

        return false;
    }

    // Does 'this' intersect with the provided polygon?
    bool GeometryContainer::intersects(const S2Polygon& otherPolygon) const {
        if (NULL != _point) {
            // The point must be valid lng, lat if it was old-style.
            if (FLAT == _point->crs && !_point->flatUpgradedToSphere) {
                return false;
            }
            return otherPolygon.MayIntersect(_point->cell);
        } else if (NULL != _line) {
            return polygonLineIntersection(_line->line, otherPolygon);
        } else if (NULL != _polygon) {
            return otherPolygon.Intersects(&_polygon->polygon);
        } else if (NULL != _multiPoint) {
            for (size_t i = 0; i < _multiPoint->cells.size(); ++i) {
                if (otherPolygon.MayIntersect(_multiPoint->cells[i])) { return true; }
            }
        } else if (NULL != _multiLine) {
            for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) {
                if (polygonLineIntersection(*_multiLine->lines.vector()[i], otherPolygon)) {
                    return true;
                }
            }
        } else if (NULL != _multiPolygon) {
            for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) {
                if (otherPolygon.Intersects(_multiPolygon->polygons.vector()[i])) {
                    return true;
                }
            }
        } else if (NULL != _geometryCollection) {
            const GeometryCollection& c = *_geometryCollection;

            for (size_t i = 0; i < c.points.size(); ++i) {
                if (otherPolygon.MayIntersect(c.points[i].cell)) { return true; }
            }

            for (size_t i = 0; i < c.polygons.vector().size(); ++i) {
                if (otherPolygon.Intersects(&c.polygons.vector()[i]->polygon)) {
                    return true;
                }
            }

            for (size_t i = 0; i < c.lines.vector().size(); ++i) {
                if (polygonLineIntersection(c.lines.vector()[i]->line, otherPolygon)) {
                    return true;
                }
            }

            for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) {
                const vector<S2Polygon*>& innerPolys =
                    c.multiPolygons.vector()[i]->polygons.vector();
                for (size_t j = 0; j < innerPolys.size(); ++j) {
                    if (otherPolygon.Intersects(innerPolys[j])) {
                        return true;
                    }
                }
            }

            for (size_t i = 0; i < c.multiLines.vector().size(); ++i) {
                const vector<S2Polyline*>& innerLines =
                    c.multiLines.vector()[i]->lines.vector();
                for (size_t j = 0; j < innerLines.size(); ++j) {
                    if (polygonLineIntersection(*innerLines[j], otherPolygon)) {
                        return true;
                    }
                }
            }

            for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) {
                const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells;
                for (size_t j = 0; j < innerCells.size(); ++j) {
                    if (otherPolygon.MayIntersect(innerCells[j])) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    bool GeometryContainer::parseFrom(const BSONObj& obj) {
        *this = GeometryContainer();

        if (GeoParser::isPolygon(obj)) {
            // We can't really pass these things around willy-nilly except by ptr.
            _polygon.reset(new PolygonWithCRS());
            if (!GeoParser::parsePolygon(obj, _polygon.get())) { return false; }
        } else if (GeoParser::isPoint(obj)) {
            _point.reset(new PointWithCRS());
            if (!GeoParser::parsePoint(obj, _point.get())) { return false; }
        } else if (GeoParser::isLine(obj)) {
            _line.reset(new LineWithCRS());
            if (!GeoParser::parseLine(obj, _line.get())) { return false; }
        } else if (GeoParser::isBox(obj)) {
            _box.reset(new BoxWithCRS());
            if (!GeoParser::parseBox(obj, _box.get())) { return false; }
        } else if (GeoParser::isCap(obj)) {
            _cap.reset(new CapWithCRS());
            if (!GeoParser::parseCap(obj, _cap.get())) { return false; }
        } else if (GeoParser::isMultiPoint(obj)) {
            _multiPoint.reset(new MultiPointWithCRS());
            if (!GeoParser::parseMultiPoint(obj, _multiPoint.get())) { return false; }
            _region.reset(new S2RegionUnion());
            for (size_t i = 0; i < _multiPoint->cells.size(); ++i) {
                _region->Add(&_multiPoint->cells[i]);
            }
        } else if (GeoParser::isMultiLine(obj)) {
            _multiLine.reset(new MultiLineWithCRS());
            if (!GeoParser::parseMultiLine(obj, _multiLine.get())) { return false; }
            _region.reset(new S2RegionUnion());
            for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) {
                _region->Add(_multiLine->lines.vector()[i]);
            }
        } else if (GeoParser::isMultiPolygon(obj)) {
            _multiPolygon.reset(new MultiPolygonWithCRS());
            if (!GeoParser::parseMultiPolygon(obj, _multiPolygon.get())) { return false; }
            _region.reset(new S2RegionUnion());
            for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) {
                _region->Add(_multiPolygon->polygons.vector()[i]);
            }
        } else if (GeoParser::isGeometryCollection(obj)) {
            _geometryCollection.reset(new GeometryCollection());
            if (!GeoParser::parseGeometryCollection(obj, _geometryCollection.get())) {
                return false;
            }
            _region.reset(new S2RegionUnion());
            for (size_t i = 0; i < _geometryCollection->points.size(); ++i) {
                _region->Add(&_geometryCollection->points[i].cell);
            }
            for (size_t i = 0; i < _geometryCollection->lines.vector().size(); ++i) {
                _region->Add(&_geometryCollection->lines.vector()[i]->line);
            }
            for (size_t i = 0; i < _geometryCollection->polygons.vector().size(); ++i) {
                _region->Add(&_geometryCollection->polygons.vector()[i]->polygon);
            }
            for (size_t i = 0; i < _geometryCollection->multiPoints.vector().size(); ++i) {
                MultiPointWithCRS* multiPoint = _geometryCollection->multiPoints.vector()[i];
                for (size_t j = 0; j < multiPoint->cells.size(); ++j) {
                    _region->Add(&multiPoint->cells[j]);
                }
            }
            for (size_t i = 0; i < _geometryCollection->multiLines.vector().size(); ++i) {
                const MultiLineWithCRS* multiLine = _geometryCollection->multiLines.vector()[i];
                for (size_t j = 0; j < multiLine->lines.vector().size(); ++j) {
                    _region->Add(multiLine->lines.vector()[j]);
                }
            }
            for (size_t i = 0; i < _geometryCollection->multiPolygons.vector().size(); ++i) {
                const MultiPolygonWithCRS* multiPolygon =
                    _geometryCollection->multiPolygons.vector()[i];
                for (size_t j = 0; j < multiPolygon->polygons.vector().size(); ++j) {
                    _region->Add(multiPolygon->polygons.vector()[j]);
                }
            }
        } else {
            return false;
        }

        return true;
    }

    const S2Region& GeometryContainer::getRegion() const {
        if (NULL != _point) {
            // _point->crs might be FLAT but we "upgrade" it for free if it was in bounds.
            if (FLAT == _point->crs) {
                verify(_point->flatUpgradedToSphere);
            }
            return _point->cell;
        } else if (NULL != _line) {
            return _line->line;
        } else if (NULL != _cap && SPHERE == _cap->crs) {
            return _cap->cap;
        } else if (NULL != _multiPoint) {
            return *_region;
        } else if (NULL != _multiLine) {
            return *_region;
        } else if (NULL != _multiPolygon) {
            return *_region;
        } else if (NULL != _geometryCollection) {
            return *_region;
        } else {
            verify(NULL != _polygon);
            verify(SPHERE == _polygon->crs);
            return _polygon->polygon;
        }
    }
}  // namespace mongo