From 2cbd9f1d77ce6b25e9957d3121fccb521caf848f Mon Sep 17 00:00:00 2001 From: Greg Studer Date: Fri, 18 Jul 2014 15:28:37 -0400 Subject: SERVER-5800 changes for geo expression index performance, avoid preprojecting - additional covering parameters - only project points when required --- jstests/core/geo_max.js | 2 + src/mongo/SConscript | 31 +- src/mongo/db/commands/geo_near_cmd.cpp | 2 +- src/mongo/db/exec/geo_near.cpp | 66 +- src/mongo/db/exec/geo_near.h | 2 +- src/mongo/db/geo/SConscript | 31 + src/mongo/db/geo/geo_query.cpp | 285 +++++ src/mongo/db/geo/geo_query.h | 118 +++ src/mongo/db/geo/geometry_container.cpp | 1090 +++++++++++++++++++ src/mongo/db/geo/geometry_container.h | 154 +++ src/mongo/db/geo/geoparser.cpp | 39 +- src/mongo/db/geo/geoquery.cpp | 1338 ------------------------ src/mongo/db/geo/geoquery.h | 238 ----- src/mongo/db/geo/r2_region_coverer_test.cpp | 2 +- src/mongo/db/geo/s2common.cpp | 1 - src/mongo/db/geo/shapes.cpp | 47 +- src/mongo/db/geo/shapes.h | 21 +- src/mongo/db/index/SConscript | 5 +- src/mongo/db/index/expression_index.h | 217 ---- src/mongo/db/index/expression_keys_private.cpp | 10 +- src/mongo/db/matcher/expression_geo.cpp | 6 + src/mongo/db/matcher/expression_geo.h | 2 +- src/mongo/db/query/SConscript | 3 + src/mongo/db/query/canonical_query_test.cpp | 2 +- src/mongo/db/query/expression_index.cpp | 209 ++++ src/mongo/db/query/expression_index.h | 60 ++ src/mongo/db/query/expression_index_knobs.cpp | 39 + src/mongo/db/query/expression_index_knobs.h | 47 + src/mongo/db/query/index_bounds_builder.cpp | 11 +- src/mongo/db/query/planner_ixselect.cpp | 7 +- src/mongo/db/query/query_solution.h | 2 +- 31 files changed, 2183 insertions(+), 1904 deletions(-) create mode 100644 src/mongo/db/geo/SConscript create mode 100644 src/mongo/db/geo/geo_query.cpp create mode 100644 src/mongo/db/geo/geo_query.h create mode 100644 src/mongo/db/geo/geometry_container.cpp create mode 100644 src/mongo/db/geo/geometry_container.h delete mode 100644 src/mongo/db/geo/geoquery.cpp delete mode 100644 src/mongo/db/geo/geoquery.h delete mode 100644 src/mongo/db/index/expression_index.h create mode 100644 src/mongo/db/query/expression_index.cpp create mode 100644 src/mongo/db/query/expression_index.h create mode 100644 src/mongo/db/query/expression_index_knobs.cpp create mode 100644 src/mongo/db/query/expression_index_knobs.h diff --git a/jstests/core/geo_max.js b/jstests/core/geo_max.js index 03932004b75..70fde0c35ec 100644 --- a/jstests/core/geo_max.js +++ b/jstests/core/geo_max.js @@ -44,6 +44,8 @@ assert.eq(test.t.find({loc:{$near:[ 180, 0]}}, {_id:0}).limit(2).toArray(), [{lo assert.eq(test.t.find({loc:{$near:[-180, 0]}}, {_id:0}).limit(2).toArray(), [{loc: [-180, 0]}, {loc: [-179.999, 0]}]) // These will need to change when SERVER-1760 is fixed +printjson(test.t.find({loc:{$nearSphere:[ 180, 0]}}, {_id:0}).limit(2).explain()); assert.eq(test.t.find({loc:{$nearSphere:[ 180, 0]}}, {_id:0}).limit(2).toArray(), [{loc: [ 180, 0]}, {loc: [ 179.999, 0]}]) +printjson(test.t.find({loc:{$nearSphere:[-180, 0]}}, {_id:0}).limit(2).explain()); assert.eq(test.t.find({loc:{$nearSphere:[-180, 0]}}, {_id:0}).limit(2).toArray(), [{loc: [-180, 0]}, {loc: [-179.999, 0]}]) diff --git a/src/mongo/SConscript b/src/mongo/SConscript index bdda44ee17c..2c289b82f10 100644 --- a/src/mongo/SConscript +++ b/src/mongo/SConscript @@ -24,6 +24,7 @@ env.SConscript(['base/SConscript', 'db/catalog/SConscript', 'db/commands/SConscript', 'db/concurrency/SConscript', + 'db/geo/SConscript', 'db/exec/SConscript', 'db/fts/SConscript', 'db/index/SConscript', @@ -179,8 +180,9 @@ env.Library('expressions', env.Library('expressions_geo', ['db/matcher/expression_geo.cpp', - 'db/matcher/expression_parser_geo.cpp'], - LIBDEPS=['expressions','geoquery','geoparser'] ) + 'db/matcher/expression_parser_geo.cpp', + 'db/geo/geo_query.cpp'], + LIBDEPS=['expressions','db/geo/geometry','db/geo/geoparser'] ) env.Library('expressions_text', ['db/matcher/expression_text.cpp', @@ -488,8 +490,6 @@ coredbEnv.Library("coredb", [ 'db/commands/server_status_core', 'db/common', 'server_parameters', - 'geoparser', - 'geoquery', 'expressions', 'expressions_geo', 'expressions_text', @@ -835,27 +835,6 @@ if has_option( 'use-cpu-profiler' ): env.Library("defaultversion", "s/default_version.cpp") -# Geo -env.Library("geometry", [ "db/geo/hash.cpp", "db/geo/shapes.cpp", ], - LIBDEPS = [ "bson", - "$BUILD_DIR/third_party/s2/s2" ]) -env.Library("geoparser", [ "db/geo/geoparser.cpp", ], - LIBDEPS = [ "bson", - "geometry", - '$BUILD_DIR/third_party/s2/s2' ]) -env.Library("geoquery", [ "db/geo/geoquery.cpp", "db/geo/r2_region_coverer.cpp", ], - LIBDEPS = [ "bson", - "geometry", - "geoparser", - '$BUILD_DIR/third_party/s2/s2' ]) - -env.CppUnitTest("hash_test", [ "db/geo/hash_test.cpp" ], - LIBDEPS = ["geometry", "db/common" ]) # db/common needed for field parsing -env.CppUnitTest("geoparser_test", [ "db/geo/geoparser_test.cpp" ], - LIBDEPS = ["geoparser", "db/common" ]) # db/common needed for field parsing -env.CppUnitTest("r2_region_coverer_test", [ "db/geo/r2_region_coverer_test.cpp" ], - LIBDEPS = [ "geoquery", "db/common" ]) # db/common needed for field parsing - env.CppUnitTest( target="index_filter_commands_test", source=[ @@ -925,8 +904,6 @@ serveronlyLibdeps = ["coreshard", "db/concurrency/lock_mgr", "db/ops/update_driver", "defaultversion", - "geoparser", - "geoquery", "global_optime", "index_key_validate", "index_set", diff --git a/src/mongo/db/commands/geo_near_cmd.cpp b/src/mongo/db/commands/geo_near_cmd.cpp index 28e9e802e23..7b85946e9cf 100644 --- a/src/mongo/db/commands/geo_near_cmd.cpp +++ b/src/mongo/db/commands/geo_near_cmd.cpp @@ -35,7 +35,7 @@ #include "mongo/db/commands.h" #include "mongo/db/curop.h" #include "mongo/db/geo/geoconstants.h" -#include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/geo_query.h" #include "mongo/db/geo/s2common.h" #include "mongo/db/index_names.h" #include "mongo/db/index/index_descriptor.h" diff --git a/src/mongo/db/exec/geo_near.cpp b/src/mongo/db/exec/geo_near.cpp index ed570ed0e4f..dc62c17236f 100644 --- a/src/mongo/db/exec/geo_near.cpp +++ b/src/mongo/db/exec/geo_near.cpp @@ -36,8 +36,10 @@ #include "mongo/db/exec/fetch.h" #include "mongo/db/exec/working_set_computed_data.h" #include "mongo/db/geo/geoconstants.h" -#include "mongo/db/index/expression_index.h" +#include "mongo/db/geo/geoparser.h" #include "mongo/db/matcher/expression.h" +#include "mongo/db/query/expression_index.h" +#include "mongo/db/query/expression_index_knobs.h" namespace mongo { @@ -134,7 +136,7 @@ namespace mongo { // Must have an object in order to get geometry out of it. invariant(member->hasObj()); - CRS queryCRS = nearParams.nearQuery.getQueryCRS(); + CRS queryCRS = nearParams.nearQuery.centroid.crs; // Extract all the geometries out of this document for the near query OwnedPointerVector geometriesOwned; @@ -171,7 +173,7 @@ namespace mongo { } if (nearParams.addDistMeta) { - if (nearParams.nearQuery.unitsAreRadians()) { + if (nearParams.nearQuery.unitsAreRadians) { // Hack for nearSphere // TODO: Remove nearSphere? invariant(SPHERE == queryCRS); @@ -190,37 +192,34 @@ namespace mongo { return StatusWith(minDistance); } - static Point toPoint(const PointWithCRS& ptCRS) { - if (ptCRS.crs == FLAT) { - return ptCRS.oldPoint; - } - else { - S2LatLng latLng(ptCRS.point); - return Point(latLng.lng().degrees(), latLng.lat().degrees()); - } - } - static R2Annulus geoNearDistanceBounds(const NearQuery& query) { - if (FLAT == query.getQueryCRS()) { - return R2Annulus(toPoint(query.centroid), query.minDistance, query.maxDistance); + const CRS queryCRS = query.centroid.crs; + + if (FLAT == queryCRS) { + return R2Annulus(query.centroid.oldPoint, query.minDistance, query.maxDistance); } - invariant(SPHERE == query.getQueryCRS()); + invariant(SPHERE == queryCRS); // TODO: Tighten this up a bit by making a CRS for "sphere with radians" double minDistance = query.minDistance; double maxDistance = query.maxDistance; - if (query.unitsAreRadians()) { + if (query.unitsAreRadians) { // Our input bounds are in radians, convert to meters since the query CRS is actually // SPHERE. We'll convert back to radians on outputting distances. minDistance *= kRadiusOfEarthInMeters; maxDistance *= kRadiusOfEarthInMeters; } - invariant(SPHERE == query.getQueryCRS()); - return R2Annulus(toPoint(query.centroid), + // GOTCHA: oldPoint is a misnomer - it is the original point data and is in the correct + // CRS. We must not try to derive the original point from the spherical S2Point generated + // as an optimization - the mapping is not 1->1 - [-180, 0] and [180, 0] map to the same + // place. + // TODO: Wrapping behavior should not depend on the index, which would make $near code + // insensitive to which direction we explore the index in. + return R2Annulus(query.centroid.oldPoint, min(minDistance, kMaxEarthDistanceInMeters), min(maxDistance, kMaxEarthDistanceInMeters)); } @@ -233,8 +232,9 @@ namespace mongo { const IndexDescriptor* twoDIndex) { R2Annulus fullBounds = geoNearDistanceBounds(nearParams.nearQuery); + const CRS queryCRS = nearParams.nearQuery.centroid.crs; - if (FLAT == nearParams.nearQuery.getQueryCRS()) { + if (FLAT == queryCRS) { // Reset the full bounds based on our index bounds GeoHashConverter::Parameters hashParams; @@ -253,8 +253,8 @@ namespace mongo { else { // Spherical queries have upper bounds set by the earth - no-op // TODO: Wrapping errors would creep in here if nearSphere wasn't defined to not wrap - invariant(SPHERE == nearParams.nearQuery.getQueryCRS()); - invariant(!nearParams.nearQuery.isWrappingQuery()); + invariant(SPHERE == queryCRS); + invariant(!nearParams.nearQuery.isWrappingQuery); } return fullBounds; @@ -262,7 +262,7 @@ namespace mongo { static double twoDBoundsIncrement(const GeoNearParams& nearParams) { // TODO: Revisit and tune these - if (FLAT == nearParams.nearQuery.getQueryCRS()) { + if (FLAT == nearParams.nearQuery.centroid.crs) { return 10; } else { @@ -460,10 +460,11 @@ namespace mongo { // max radius. This is slightly conservative for now (box diagonal vs circle radius). double minBoundsIncrement = hasher.getError() / 2; - if (FLAT == query.getQueryCRS()) + const CRS queryCRS = query.centroid.crs; + if (FLAT == queryCRS) return minBoundsIncrement; - invariant(SPHERE == query.getQueryCRS()); + invariant(SPHERE == queryCRS); // If this is a spherical query, units are in meters - this is just a heuristic return minBoundsIncrement * kMetersPerDegreeAtEquator; @@ -522,8 +523,11 @@ namespace mongo { // Get a covering region for this interval // + const CRS queryCRS = _nearParams.nearQuery.centroid.crs; + auto_ptr coverRegion; - if (_nearParams.nearQuery.getQueryCRS() == FLAT) { + + if (FLAT == queryCRS) { // NOTE: Due to floating point math issues, FLAT searches of a 2D index need to treat // containment and distance separately. @@ -567,7 +571,7 @@ namespace mongo { nextBounds.getOuter() + epsilon)); } else { - invariant(SPHERE == _nearParams.nearQuery.getQueryCRS()); + invariant(SPHERE == queryCRS); // TODO: As above, make this consistent with $within : $centerSphere // Our intervals aren't in the same CRS as our index, so we need to adjust them @@ -598,7 +602,11 @@ namespace mongo { OrderedIntervalList coveredIntervals; coveredIntervals.name = scanParams.bounds.fields[twoDFieldPosition].name; - ExpressionMapping::cover2d(*coverRegion, _twoDIndex->infoObj(), &coveredIntervals); + + ExpressionMapping::cover2d(*coverRegion, + _twoDIndex->infoObj(), + internalGeoNearQuery2DMaxCoveringCells, + &coveredIntervals); // Intersect the $near bounds we just generated into the bounds we have for anything else // in the scan (i.e. $within) @@ -630,7 +638,7 @@ namespace mongo { _nearParams.fullFilter ? _nearParams.fullFilter->shallowClone() : NULL; // FLAT searches need to add an additional annulus $within matcher, see above - if (FLAT == _nearParams.nearQuery.getQueryCRS()) { + if (FLAT == queryCRS) { MatchExpression* withinMatcher = new TwoDPtInAnnulusExpression(_fullBounds, twoDFieldName); diff --git a/src/mongo/db/exec/geo_near.h b/src/mongo/db/exec/geo_near.h index bc3eccf6f00..8f576bc82ed 100644 --- a/src/mongo/db/exec/geo_near.h +++ b/src/mongo/db/exec/geo_near.h @@ -32,7 +32,7 @@ #include "mongo/db/exec/working_set.h" #include "mongo/db/exec/plan_stats.h" #include "mongo/db/index/index_descriptor.h" -#include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/geo_query.h" #include "mongo/db/matcher/expression.h" #include "mongo/db/query/index_bounds.h" diff --git a/src/mongo/db/geo/SConscript b/src/mongo/db/geo/SConscript new file mode 100644 index 00000000000..888dd3b02f0 --- /dev/null +++ b/src/mongo/db/geo/SConscript @@ -0,0 +1,31 @@ +# -*- mode: python -*- + +Import("env") + +# Core geometry shape libraries +env.Library("geometry", [ "hash.cpp", + "shapes.cpp", + "r2_region_coverer.cpp" ], + LIBDEPS = [ "$BUILD_DIR/mongo/bson", + "$BUILD_DIR/third_party/s2/s2" ]) + +# Geometry / BSON parsing and wrapping +env.Library("geoparser", [ "geoparser.cpp", + "geometry_container.cpp" ], + LIBDEPS = [ "geometry", + "$BUILD_DIR/mongo/bson", + "$BUILD_DIR/third_party/s2/s2" ]) + +env.CppUnitTest("hash_test", [ "hash_test.cpp" ], + LIBDEPS = ["geometry", + "$BUILD_DIR/mongo/db/common" ]) # db/common needed for field parsing + +env.CppUnitTest("geoparser_test", [ "geoparser_test.cpp" ], + LIBDEPS = [ "geoparser", + "$BUILD_DIR/mongo/db/common" ]) # db/common needed for field parsing + +env.CppUnitTest("r2_region_coverer_test", [ "r2_region_coverer_test.cpp" ], + LIBDEPS = [ "geometry", + "geoparser", + "$BUILD_DIR/mongo/db/common" ]) # db/common needed for field parsing + diff --git a/src/mongo/db/geo/geo_query.cpp b/src/mongo/db/geo/geo_query.cpp new file mode 100644 index 00000000000..05ae6fa4757 --- /dev/null +++ b/src/mongo/db/geo/geo_query.cpp @@ -0,0 +1,285 @@ +/** + * 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 . + * + * 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/geo_query.h" + +#include "mongo/db/geo/geoparser.h" +#include "mongo/util/mongoutils/str.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 : [0, 0, 1] } }); + // 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, ¢roid)) + || GeoParser::parsePointWithMaxDistance(embeddedObj, ¢roid, &maxDistance)) { + uassert(18522, "max distance must be non-negative", maxDistance >= 0.0); + 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"; + } + } + + 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(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, ¢roid)) { + 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) { + + Status status = Status::OK(); + + if (!parseLegacyQuery(obj)) { + // Clear out any half-baked data. + minDistance = 0; + isNearSphere = false; + maxDistance = std::numeric_limits::max(); + centroid = PointWithCRS(); + // ...and try parsing new format. + status = parseNewQuery(obj); + } + + if (!status.isOK()) + return status; + + // Fixup the near query for anonoyances caused by $nearSphere + if (isNearSphere) { + + // The user-provided point can be flat for a spherical query - needs to be projectable + uassert(17444, + "Legacy point is out of bounds for spherical query", + ShapeProjection::supportsProject(centroid, SPHERE)); + + unitsAreRadians = SPHERE != centroid.crs; + // GeoJSON points imply wrapping queries + isWrappingQuery = SPHERE == centroid.crs; + + // Project the point to a spherical CRS now that we've got the settings we need + // We need to manually project here since we aren't using GeometryContainer + ShapeProjection::projectInto(¢roid, SPHERE); + } + else { + unitsAreRadians = false; + isWrappingQuery = SPHERE == centroid.crs; + } + + return status; + } + + 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(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) { + if (!(parseLegacyQuery(obj) || parseNewQuery(obj))) + return false; + + // $geoIntersect queries are hardcoded to *always* be in SPHERE CRS + // TODO: This is probably bad semantics, should not do this + if (GeoQuery::INTERSECT == predicate) { + if (!geoContainer.supportsProject(SPHERE)) + return false; + geoContainer.projectInto(SPHERE); + } + + return true; + } + +} // namespace mongo diff --git a/src/mongo/db/geo/geo_query.h b/src/mongo/db/geo/geo_query.h new file mode 100644 index 00000000000..5390d7c5a23 --- /dev/null +++ b/src/mongo/db/geo/geo_query.h @@ -0,0 +1,118 @@ +/** +* Copyright (C) 2013 10gen 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 . +* +* 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. +*/ + +#pragma once + +#include + +#include "mongo/db/geo/shapes.h" +#include "mongo/db/geo/geometry_container.h" + +namespace mongo { + + // TODO: Make a struct, turn parse stuff into something like + // static Status parseNearQuery(const BSONObj& obj, NearQuery** out); + class NearQuery { + public: + NearQuery() + : minDistance(0), + maxDistance(std::numeric_limits::max()), + isNearSphere(false), + unitsAreRadians(false), + isWrappingQuery(false) { } + + NearQuery(const std::string& f) + : field(f), + minDistance(0), + maxDistance(std::numeric_limits::max()), + isNearSphere(false), + unitsAreRadians(false), + isWrappingQuery(false) { } + + Status parseFrom(const BSONObj &obj); + + // The name of the field that contains the geometry. + std::string field; + + // The starting point of the near search. + PointWithCRS centroid; + + // Min and max distance from centroid that we're willing to search. + // Distance is in units of the geometry's CRS, except SPHERE and isNearSphere => radians + double minDistance; + double maxDistance; + + // Is this a $nearSphere query + bool isNearSphere; + // $nearSphere with a legacy point implies units are radians + bool unitsAreRadians; + // $near with a non-legacy point implies a wrapping query, otherwise the query doesn't wrap + bool isWrappingQuery; + + std::string toString() const { + std::stringstream ss; + ss << " field=" << field; + ss << " maxdist=" << maxDistance; + ss << " isNearSphere=" << isNearSphere; + return ss.str(); + } + + private: + bool parseLegacyQuery(const BSONObj &obj); + Status parseNewQuery(const BSONObj &obj); + }; + + // This represents either a $within or a $geoIntersects. + class GeoQuery { + public: + GeoQuery() : field(""), predicate(INVALID) {} + GeoQuery(const std::string& f) : field(f), predicate(INVALID) {} + + enum Predicate { + WITHIN, + INTERSECT, + INVALID + }; + + bool parseFrom(const BSONObj &obj); + + std::string getField() const { return field; } + Predicate getPred() const { return predicate; } + const GeometryContainer& getGeometry() const { return geoContainer; } + + private: + // Try to parse the provided object into the right place. + bool parseLegacyQuery(const BSONObj &obj); + bool parseNewQuery(const BSONObj &obj); + + // Name of the field in the query. + std::string field; + GeometryContainer geoContainer; + Predicate predicate; + }; +} // namespace mongo diff --git a/src/mongo/db/geo/geometry_container.cpp b/src/mongo/db/geo/geometry_container.cpp new file mode 100644 index 00000000000..568351b75d1 --- /dev/null +++ b/src/mongo/db/geo/geometry_container.cpp @@ -0,0 +1,1090 @@ +/** + * 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 . + * + * 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/geometry_container.h" + +#include "mongo/db/geo/geoconstants.h" +#include "mongo/db/geo/s2common.h" +#include "mongo/util/mongoutils/str.h" + +namespace mongo { + + using mongoutils::str::equals; + + GeometryContainer::GeometryContainer() { + } + + 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) + || NULL != _line + || (NULL != _polygon && _polygon->crs == SPHERE) + || (NULL != _cap && _cap->crs == SPHERE) + || NULL != _multiPoint + || NULL != _multiLine + || NULL != _multiPolygon + || NULL != _geometryCollection; + } + + const S2Region& GeometryContainer::getS2Region() const { + if (NULL != _point && SPHERE == _point->crs) { + return _point->cell; + } else if (NULL != _line) { + return _line->line; + } else if (NULL != _polygon && SPHERE == _polygon->crs) { + return _polygon->polygon; + } else if (NULL != _cap && SPHERE == _cap->crs) { + return _cap->cap; + } else if (NULL != _multiPoint) { + return *_s2Region; + } else if (NULL != _multiLine) { + return *_s2Region; + } else if (NULL != _multiPolygon) { + return *_s2Region; + } else { + invariant(NULL != _geometryCollection); + return *_s2Region; + } + } + + bool GeometryContainer::hasR2Region() const { + return _cap || _box || _point || (_polygon && _polygon->crs == FLAT) + || (_multiPoint && FLAT == _multiPoint->crs); + } + + class GeometryContainer::R2BoxRegion : public R2Region { + public: + + R2BoxRegion(const GeometryContainer* geometry); + virtual ~R2BoxRegion(); + + Box getR2Bounds() const; + + bool fastContains(const Box& other) const; + + bool fastDisjoint(const Box& other) const; + + private: + + static Box buildBounds(const GeometryContainer& geometry); + + // Not owned here + const GeometryContainer* _geometry; + + // TODO: For big complex shapes, may be better to use actual shape from above + const Box _bounds; + }; + + GeometryContainer::R2BoxRegion::R2BoxRegion(const GeometryContainer* geometry) : + _geometry(geometry), _bounds(buildBounds(*geometry)) { + } + + GeometryContainer::R2BoxRegion::~R2BoxRegion() { + } + + Box GeometryContainer::R2BoxRegion::getR2Bounds() const { + return _bounds; + } + + bool GeometryContainer::R2BoxRegion::fastContains(const Box& other) const { + + // TODO: Add more cases here to make coverings better + if (_geometry->_box && FLAT == _geometry->_box->crs) { + const Box& box = _geometry->_box->box; + if (box.contains(other)) + return true; + } else if (_geometry->_cap && FLAT == _geometry->_cap->crs) { + const Circle& circle = _geometry->_cap->circle; + // Exact test + return circleContainsBox(circle, other); + } + + if (_geometry->_polygon && FLAT == _geometry->_polygon->crs) { + const Polygon& polygon = _geometry->_polygon->oldPolygon; + // Exact test + return polygonContainsBox(polygon, other); + } + + // Not sure + return false; + } + + bool GeometryContainer::R2BoxRegion::fastDisjoint(const Box& other) const { + + if (!_bounds.intersects(other)) + return true; + + // Not sure + return false; + } + + static Point toLngLatPoint(const S2Point& s2Point) { + Point point; + S2LatLng latLng(s2Point); + point.x = latLng.lng().degrees(); + point.y = latLng.lat().degrees(); + return point; + } + + static void lineR2Bounds(const S2Polyline& flatLine, Box* flatBounds) { + + int numVertices = flatLine.num_vertices(); + verify(flatLine.num_vertices() > 0); + + flatBounds->init(toLngLatPoint(flatLine.vertex(0)), toLngLatPoint(flatLine.vertex(0))); + + for (int i = 1; i < numVertices; ++i) { + flatBounds->expandToInclude(toLngLatPoint(flatLine.vertex(i))); + } + } + + static void circleR2Bounds(const Circle& circle, Box* flatBounds) { + flatBounds->init(Point(circle.center.x - circle.radius, circle.center.y - circle.radius), + Point(circle.center.x + circle.radius, circle.center.y + circle.radius)); + } + + static void multiPointR2Bounds(const vector& points, Box* flatBounds) { + + verify(!points.empty()); + + flatBounds->init(toLngLatPoint(points.front()), toLngLatPoint(points.front())); + + vector::const_iterator it = points.begin(); + for (++it; it != points.end(); ++it) { + const S2Point& s2Point = *it; + flatBounds->expandToInclude(toLngLatPoint(s2Point)); + } + } + + static void polygonR2Bounds(const Polygon& polygon, Box* flatBounds) { + *flatBounds = polygon.bounds(); + } + + static void s2RegionR2Bounds(const S2Region& region, Box* flatBounds) { + S2LatLngRect s2Bounds = region.GetRectBound(); + flatBounds->init(Point(s2Bounds.lng_lo().degrees(), s2Bounds.lat_lo().degrees()), + Point(s2Bounds.lng_hi().degrees(), s2Bounds.lat_hi().degrees())); + } + + Box GeometryContainer::R2BoxRegion::buildBounds(const GeometryContainer& geometry) { + + Box bounds; + + if (geometry._point && FLAT == geometry._point->crs) { + bounds.init(geometry._point->oldPoint, geometry._point->oldPoint); + } + else if (geometry._line && FLAT == geometry._line->crs) { + lineR2Bounds(geometry._line->line, &bounds); + } + else if (geometry._cap && FLAT == geometry._cap->crs) { + circleR2Bounds(geometry._cap->circle, &bounds); + } + else if (geometry._box && FLAT == geometry._box->crs) { + bounds = geometry._box->box; + } + else if (geometry._polygon && FLAT == geometry._polygon->crs) { + polygonR2Bounds(geometry._polygon->oldPolygon, &bounds); + } + else if (geometry._multiPoint && FLAT == geometry._multiPoint->crs) { + multiPointR2Bounds(geometry._multiPoint->points, &bounds); + } + else if (geometry._multiLine && FLAT == geometry._multiLine->crs) { + verify(false); + } + else if (geometry._multiPolygon && FLAT == geometry._multiPolygon->crs) { + verify(false); + } + else if (geometry._geometryCollection) { + verify(false); + } + else if (geometry.hasS2Region()) { + // For now, just support spherical cap for $centerSphere and GeoJSON points + verify((geometry._cap && FLAT != geometry._cap->crs) || + (geometry._point && FLAT != geometry._point->crs)); + s2RegionR2Bounds(geometry.getS2Region(), &bounds); + } + + return bounds; + } + + const R2Region& GeometryContainer::getR2Region() const { + return *_r2Region; + } + + bool GeometryContainer::contains(const GeometryContainer& otherContainer) const { + + // First let's deal with the FLAT cases + + if (_point && FLAT == _point->crs) { + return false; + } + + 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) { + 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& 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& 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& lines = c.lines.vector(); + for (size_t i = 0; i < lines.size(); ++i) { + if (!contains(lines[i]->line)) { return false; } + } + + const vector& polys = c.polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (!contains(polys[i]->polygon)) { return false; } + } + + const vector& 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& multilines = c.multiLines.vector(); + for (size_t i = 0; i < multilines.size(); ++i) { + const vector& lines = multilines[i]->lines.vector(); + for (size_t j = 0; j < lines.size(); ++j) { + if (!contains(*lines[j])) { return false; } + } + } + + const vector& multipolys = c.multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector& 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& 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& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPoint(polys[i]->polygon, otherCell, otherPoint)) { return true; } + } + + const vector& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector& 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 clippedOwned; + vector& 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& 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& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsLine(polys[i]->polygon, otherLine)) { return true; } + } + + const vector& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector& 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& 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& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPolygon(polys[i]->polygon, otherPolygon)) { return true; } + } + + const vector& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector& 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) { + 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) { + 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& 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& 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& 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& 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& 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& 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 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) { + 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& 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& 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& 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) { + 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& 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& 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& 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) { + + 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::isIndexablePoint(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; } + _s2Region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiPoint->cells.size(); ++i) { + _s2Region->Add(&_multiPoint->cells[i]); + } + } else if (GeoParser::isMultiLine(obj)) { + _multiLine.reset(new MultiLineWithCRS()); + if (!GeoParser::parseMultiLine(obj, _multiLine.get())) { return false; } + _s2Region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) { + _s2Region->Add(_multiLine->lines.vector()[i]); + } + } else if (GeoParser::isMultiPolygon(obj)) { + _multiPolygon.reset(new MultiPolygonWithCRS()); + if (!GeoParser::parseMultiPolygon(obj, _multiPolygon.get())) { return false; } + _s2Region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) { + _s2Region->Add(_multiPolygon->polygons.vector()[i]); + } + } else if (GeoParser::isGeometryCollection(obj)) { + _geometryCollection.reset(new GeometryCollection()); + if (!GeoParser::parseGeometryCollection(obj, _geometryCollection.get())) { + return false; + } + _s2Region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _geometryCollection->points.size(); ++i) { + _s2Region->Add(&_geometryCollection->points[i].cell); + } + for (size_t i = 0; i < _geometryCollection->lines.vector().size(); ++i) { + _s2Region->Add(&_geometryCollection->lines.vector()[i]->line); + } + for (size_t i = 0; i < _geometryCollection->polygons.vector().size(); ++i) { + _s2Region->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) { + _s2Region->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) { + _s2Region->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) { + _s2Region->Add(multiPolygon->polygons.vector()[j]); + } + } + } else { + return false; + } + + // If we support R2 regions, build the region immediately + if (hasR2Region()) + _r2Region.reset(new R2BoxRegion(this)); + + return true; + } + + string GeometryContainer::getDebugType() const { + if (NULL != _point) { return "pt"; } + else if (NULL != _line) { return "ln"; } + else if (NULL != _box) { return "bx"; } + else if (NULL != _polygon) { return "pl"; } + else if (NULL != _cap ) { return "cc"; } + else if (NULL != _multiPoint) { return "mp"; } + else if (NULL != _multiLine) { return "ml"; } + else if (NULL != _multiPolygon) { return "my"; } + else if (NULL != _geometryCollection) { return "gc"; } + else { + invariant(false); + return ""; + } + } + + CRS GeometryContainer::getNativeCRS() const { + + // TODO: Fix geometry collection reporting when/if we support multiple CRSes + + if (NULL != _point) { return _point->crs; } + else if (NULL != _line) { return _line->crs; } + else if (NULL != _box) { return _box->crs; } + else if (NULL != _polygon) { return _polygon->crs; } + else if (NULL != _cap ) { return _cap->crs; } + else if (NULL != _multiPoint) { return _multiPoint->crs; } + else if (NULL != _multiLine) { return _multiLine->crs; } + else if (NULL != _multiPolygon) { return _multiPolygon->crs; } + else if (NULL != _geometryCollection) { return SPHERE; } + else { + invariant(false); + return FLAT; + } + } + + bool GeometryContainer::supportsProject(CRS otherCRS) const { + + // TODO: Fix geometry collection reporting when/if we support more CRSes + + if (NULL != _point) { + return ShapeProjection::supportsProject(*_point, otherCRS); + } + else if (NULL != _line) { return _line->crs == otherCRS; } + else if (NULL != _box) { return _box->crs == otherCRS; } + else if (NULL != _polygon) { return _polygon->crs == otherCRS; } + else if (NULL != _cap ) { return _cap->crs == otherCRS; } + else if (NULL != _multiPoint) { return _multiPoint->crs == otherCRS; } + else if (NULL != _multiLine) { return _multiLine->crs == otherCRS; } + else if (NULL != _multiPolygon) { return _multiPolygon->crs == otherCRS; } + else { + invariant(NULL != _geometryCollection); + return SPHERE == otherCRS; + } + } + + void GeometryContainer::projectInto(CRS otherCRS) { + + if (otherCRS == getNativeCRS()) + return; + + invariant(NULL != _point); + + ShapeProjection::projectInto(_point.get(), otherCRS); + } + + static double s2MinDistanceRad(const S2Point& s2Point, const MultiPointWithCRS& s2MultiPoint) { + + double minDistance = -1; + for (vector::const_iterator it = s2MultiPoint.points.begin(); + it != s2MultiPoint.points.end(); ++it) { + + double nextDistance = S2Distance::distanceRad(s2Point, *it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + return minDistance; + } + + static double s2MinDistanceRad(const S2Point& s2Point, const MultiLineWithCRS& s2MultiLine) { + + double minDistance = -1; + for (vector::const_iterator it = s2MultiLine.lines.vector().begin(); + it != s2MultiLine.lines.vector().end(); ++it) { + + double nextDistance = S2Distance::minDistanceRad(s2Point, **it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + return minDistance; + } + + static double s2MinDistanceRad(const S2Point& s2Point, const MultiPolygonWithCRS& s2MultiPolygon) { + + double minDistance = -1; + for (vector::const_iterator it = s2MultiPolygon.polygons.vector().begin(); + it != s2MultiPolygon.polygons.vector().end(); ++it) { + + double nextDistance = S2Distance::minDistanceRad(s2Point, **it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + return minDistance; + } + + static double s2MinDistanceRad(const S2Point& s2Point, + const GeometryCollection& geometryCollection) { + + double minDistance = -1; + for (vector::const_iterator it = geometryCollection.points.begin(); + it != geometryCollection.points.end(); ++it) { + + invariant(SPHERE == it->crs); + double nextDistance = S2Distance::distanceRad(s2Point, it->point); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + for (vector::const_iterator it = geometryCollection.lines.vector().begin(); + it != geometryCollection.lines.vector().end(); ++it) { + + invariant(SPHERE == (*it)->crs); + double nextDistance = S2Distance::minDistanceRad(s2Point, (*it)->line); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + for (vector::const_iterator it = geometryCollection.polygons.vector().begin(); + it != geometryCollection.polygons.vector().end(); ++it) { + + invariant(SPHERE == (*it)->crs); + double nextDistance = S2Distance::minDistanceRad(s2Point, (*it)->polygon); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + for (vector::const_iterator it = geometryCollection.multiPoints.vector() + .begin(); it != geometryCollection.multiPoints.vector().end(); ++it) { + + double nextDistance = s2MinDistanceRad(s2Point, **it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + for (vector::const_iterator it = geometryCollection.multiLines.vector() + .begin(); it != geometryCollection.multiLines.vector().end(); ++it) { + + double nextDistance = s2MinDistanceRad(s2Point, **it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + for (vector::const_iterator it = geometryCollection.multiPolygons + .vector().begin(); it != geometryCollection.multiPolygons.vector().end(); ++it) { + + double nextDistance = s2MinDistanceRad(s2Point, **it); + if (minDistance < 0 || nextDistance < minDistance) { + minDistance = nextDistance; + } + } + + return minDistance; + } + + double GeometryContainer::minDistance(const PointWithCRS& otherPoint) const { + + const CRS crs = getNativeCRS(); + + if (FLAT == crs) { + + invariant(NULL != _point); + + if (FLAT == otherPoint.crs) { + return distance(_point->oldPoint, otherPoint.oldPoint); + } + else { + S2LatLng latLng(otherPoint.point); + return distance(_point->oldPoint, + Point(latLng.lng().degrees(), latLng.lat().degrees())); + } + } + else { + invariant(SPHERE == crs); + + double minDistance = -1; + + if (NULL != _point) { + minDistance = S2Distance::distanceRad(otherPoint.point, _point->point); + } + else if (NULL != _line) { + minDistance = S2Distance::minDistanceRad(otherPoint.point, _line->line); + } + else if (NULL != _polygon) { + minDistance = S2Distance::minDistanceRad(otherPoint.point, _polygon->polygon); + } + else if (NULL != _cap) { + minDistance = S2Distance::minDistanceRad(otherPoint.point, _cap->cap); + } + else if (NULL != _multiPoint) { + minDistance = s2MinDistanceRad(otherPoint.point, *_multiPoint); + } + else if (NULL != _multiLine) { + minDistance = s2MinDistanceRad(otherPoint.point, *_multiLine); + } + else if (NULL != _multiPolygon) { + minDistance = s2MinDistanceRad(otherPoint.point, *_multiPolygon); + } + else if (NULL != _geometryCollection) { + minDistance = s2MinDistanceRad(otherPoint.point, *_geometryCollection); + } + + invariant(minDistance != -1); + return minDistance * kRadiusOfEarthInMeters; + } + } + + const CapWithCRS* GeometryContainer::getCapGeometryHack() const { + return _cap.get(); + } + +} // namespace mongo diff --git a/src/mongo/db/geo/geometry_container.h b/src/mongo/db/geo/geometry_container.h new file mode 100644 index 00000000000..7bd054778ff --- /dev/null +++ b/src/mongo/db/geo/geometry_container.h @@ -0,0 +1,154 @@ +/** + * Copyright (C) 2013 10gen 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 . + * + * 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. + */ + +#pragma once + +#include + +#include "mongo/base/disallow_copying.h" +#include "mongo/db/geo/shapes.h" +#include "third_party/s2/s2regionunion.h" + +namespace mongo { + + class GeometryContainer { + MONGO_DISALLOW_COPYING(GeometryContainer); + public: + + /** + * Creates an empty geometry container which may then be loaded from BSON or directly. + */ + GeometryContainer(); + + /** + * Loads an empty GeometryContainer from BSON + */ + bool parseFrom(const BSONObj &obj); + + /** + * Is the geometry any of {Point, Line, Polygon}? + */ + bool isSimpleContainer() const; + + /** + * Reports the CRS of the contained geometry. + * TODO: Rework once we have collections of multiple CRSes + */ + CRS getNativeCRS() const; + + /** + * Whether or not this geometry can be projected into a particular CRS + */ + bool supportsProject(CRS crs) const; + + /** + * Projects the current geometry into the supplied crs. + * It is an error to call this function if canProjectInto(crs) is false. + */ + void projectInto(CRS crs); + + /** + * Minimum distance between this geometry and the supplied point. + * TODO: Rework and generalize to full GeometryContainer distance + */ + double minDistance(const PointWithCRS& point) const; + + /** + * Only polygons (and aggregate types thereof) support contains. + */ + bool supportsContains() const; + + /** + * To check containment, we iterate over the otherContainer's geometries. If we don't + * contain any sub-geometry of the otherContainer, the otherContainer is not contained + * within us. If each sub-geometry of the otherContainer is contained within us, we contain + * the entire otherContainer. + */ + bool contains(const GeometryContainer& otherContainer) const; + + /** + * To check intersection, we iterate over the otherContainer's geometries, checking each + * geometry to see if we intersect it. If we intersect one geometry, we intersect the + * entire other container. + */ + bool intersects(const GeometryContainer& otherContainer) const; + + // Region which can be used to generate a covering of the query object in the S2 space. + bool hasS2Region() const; + const S2Region& getS2Region() const; + + // Region which can be used to generate a covering of the query object in euclidean space. + bool hasR2Region() const; + const R2Region& getR2Region() const; + + // Returns a string related to the type of the geometry (for debugging queries) + std::string getDebugType() const; + + // Needed for 2D wrapping check (for now) + // TODO: Remove these hacks + const CapWithCRS* getCapGeometryHack() const; + + private: + + class R2BoxRegion; + + // Does 'this' intersect with the provided type? + bool intersects(const S2Cell& otherPoint) const; + bool intersects(const S2Polyline& otherLine) const; + bool intersects(const S2Polygon& otherPolygon) const; + // These three just iterate over the geometries and call the 3 methods above. + bool intersects(const MultiPointWithCRS& otherMultiPoint) const; + bool intersects(const MultiLineWithCRS& otherMultiLine) const; + bool intersects(const MultiPolygonWithCRS& otherMultiPolygon) const; + + // Used when 'this' has a polygon somewhere, either in _polygon or _multiPolygon or + // _geometryCollection. + bool contains(const S2Cell& otherCell, const S2Point& otherPoint) const; + bool contains(const S2Polyline& otherLine) const; + bool contains(const S2Polygon& otherPolygon) const; + + // Only one of these shared_ptrs should be non-NULL. S2Region is a + // superclass but it only supports testing against S2Cells. We need + // the most specific class we can get. + scoped_ptr _point; + scoped_ptr _line; + scoped_ptr _box; + scoped_ptr _polygon; + scoped_ptr _cap; + scoped_ptr _multiPoint; + scoped_ptr _multiLine; + scoped_ptr _multiPolygon; + scoped_ptr _geometryCollection; + + // Cached for use during covering calculations + // TODO: _s2Region is currently generated immediately - don't necessarily need to do this + scoped_ptr _s2Region; + scoped_ptr _r2Region; + }; + +} // namespace mongo diff --git a/src/mongo/db/geo/geoparser.cpp b/src/mongo/db/geo/geoparser.cpp index a0e956d5315..6efecc3ec58 100644 --- a/src/mongo/db/geo/geoparser.cpp +++ b/src/mongo/db/geo/geoparser.cpp @@ -52,10 +52,6 @@ namespace mongo { static const string GEOJSON_COORDINATES = "coordinates"; static const string GEOJSON_GEOMETRIES = "geometries"; - bool isValidLngLat(double lng, double lat) { - return lat >= -90 && lat <= 90 && lng >= -180 && lng <= 180; - } - static bool isGeoJSONPoint(const BSONObj& obj) { BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); if (type.eoo() || (String != type.type())) { return false; } @@ -72,6 +68,7 @@ namespace mongo { const vector& coordinates = coordElt.Array(); if (coordinates.size() != 2) { return false; } if (!coordinates[0].isNumber() || !coordinates[1].isNumber()) { return false; } + // For now, we assume all GeoJSON must be within WGS84 - this may change double lat = coordinates[1].Number(); double lng = coordinates[0].Number(); return isValidLngLat(lng, lat); @@ -316,35 +313,30 @@ namespace mongo { /** exported **/ bool GeoParser::isPoint(const BSONObj &obj) { - return isGeoJSONPoint(obj) || isLegacyPoint(obj, false); + return isLegacyPoint(obj, false) || isGeoJSONPoint(obj); } bool GeoParser::isIndexablePoint(const BSONObj &obj) { - return isGeoJSONPoint(obj) || isLegacyPoint(obj, true); + return isLegacyPoint(obj, true) || isGeoJSONPoint(obj); } bool GeoParser::parsePoint(const BSONObj &obj, PointWithCRS *out) { - if (isGeoJSONPoint(obj)) { - const vector& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); - out->point = coordToPoint(coords[0].Number(), coords[1].Number()); - out->cell = S2Cell(out->point); - out->oldPoint.x = coords[0].Number(); - out->oldPoint.y = coords[1].Number(); - out->crs = SPHERE; - } else if (isLegacyPoint(obj, true)) { + if (isLegacyPoint(obj, true)) { BSONObjIterator it(obj); BSONElement x = it.next(); BSONElement y = it.next(); - if (isValidLngLat(x.Number(), y.Number())) { - out->flatUpgradedToSphere = true; - out->point = coordToPoint(x.Number(), y.Number()); - out->cell = S2Cell(out->point); - } out->oldPoint.x = x.Number(); out->oldPoint.y = y.Number(); out->crs = FLAT; + } else if (isGeoJSONPoint(obj)) { + const vector& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); + out->oldPoint.x = coords[0].Number(); + out->oldPoint.y = coords[1].Number(); + out->crs = FLAT; + if (!ShapeProjection::supportsProject(*out, SPHERE)) + return false; + ShapeProjection::projectInto(out, SPHERE); } - return true; } @@ -686,15 +678,10 @@ namespace mongo { if (!dist.isNumber()) { return false; } if (it.more()) { return false; } - out->crs = FLAT; out->oldPoint.x = lng.number(); out->oldPoint.y = lat.number(); + out->crs = FLAT; *maxOut = dist.number(); - if (isValidLngLat(lng.Number(), lat.Number())) { - out->flatUpgradedToSphere = true; - out->point = coordToPoint(lng.Number(), lat.Number()); - out->cell = S2Cell(out->point); - } return true; } diff --git a/src/mongo/db/geo/geoquery.cpp b/src/mongo/db/geo/geoquery.cpp deleted file mode 100644 index c393951964b..00000000000 --- a/src/mongo/db/geo/geoquery.cpp +++ /dev/null @@ -1,1338 +0,0 @@ -/** - * 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 . - * - * 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" -#include "mongo/db/geo/s2common.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 : [0, 0, 1] } }); - // 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, ¢roid)) - || GeoParser::parsePointWithMaxDistance(embeddedObj, ¢roid, &maxDistance)) { - uassert(18522, "max distance must be non-negative", maxDistance >= 0.0); - 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(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, ¢roid)) { - 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::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(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); - } - - GeometryContainer::GeometryContainer() { - } - - 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; - } - - const S2Region& GeometryContainer::getS2Region() 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 *_s2Region; - } else if (NULL != _multiLine) { - return *_s2Region; - } else if (NULL != _multiPolygon) { - return *_s2Region; - } else if (NULL != _geometryCollection) { - return *_s2Region; - } else { - verify(NULL != _polygon); - verify(SPHERE == _polygon->crs); - return _polygon->polygon; - } - } - - bool GeometryContainer::hasR2Region() const { - return _cap || _box || _point || (_polygon && _polygon->crs == FLAT) - || (_multiPoint && FLAT == _multiPoint->crs); - } - - class GeometryContainer::R2BoxRegion : public R2Region { - public: - - R2BoxRegion(const GeometryContainer* geometry); - virtual ~R2BoxRegion(); - - Box getR2Bounds() const; - - bool fastContains(const Box& other) const; - - bool fastDisjoint(const Box& other) const; - - private: - - static Box buildBounds(const GeometryContainer& geometry); - - // Not owned here - const GeometryContainer* _geometry; - - // TODO: For big complex shapes, may be better to use actual shape from above - const Box _bounds; - }; - - GeometryContainer::R2BoxRegion::R2BoxRegion(const GeometryContainer* geometry) : - _geometry(geometry), _bounds(buildBounds(*geometry)) { - } - - GeometryContainer::R2BoxRegion::~R2BoxRegion() { - } - - Box GeometryContainer::R2BoxRegion::getR2Bounds() const { - return _bounds; - } - - bool GeometryContainer::R2BoxRegion::fastContains(const Box& other) const { - - // TODO: Add more cases here to make coverings better - if (_geometry->_box && FLAT == _geometry->_box->crs) { - const Box& box = _geometry->_box->box; - if (box.contains(other)) - return true; - } else if (_geometry->_cap && FLAT == _geometry->_cap->crs) { - const Circle& circle = _geometry->_cap->circle; - // Exact test - return circleContainsBox(circle, other); - } - - if (_geometry->_polygon && FLAT == _geometry->_polygon->crs) { - const Polygon& polygon = _geometry->_polygon->oldPolygon; - // Exact test - return polygonContainsBox(polygon, other); - } - - // Not sure - return false; - } - - bool GeometryContainer::R2BoxRegion::fastDisjoint(const Box& other) const { - - if (!_bounds.intersects(other)) - return true; - - // Not sure - return false; - } - - static Point toLngLatPoint(const S2Point& s2Point) { - Point point; - S2LatLng latLng(s2Point); - point.x = latLng.lng().degrees(); - point.y = latLng.lat().degrees(); - return point; - } - - static void lineR2Bounds(const S2Polyline& flatLine, Box* flatBounds) { - - int numVertices = flatLine.num_vertices(); - verify(flatLine.num_vertices() > 0); - - flatBounds->init(toLngLatPoint(flatLine.vertex(0)), toLngLatPoint(flatLine.vertex(0))); - - for (int i = 1; i < numVertices; ++i) { - flatBounds->expandToInclude(toLngLatPoint(flatLine.vertex(i))); - } - } - - static void circleR2Bounds(const Circle& circle, Box* flatBounds) { - flatBounds->init(Point(circle.center.x - circle.radius, circle.center.y - circle.radius), - Point(circle.center.x + circle.radius, circle.center.y + circle.radius)); - } - - static void multiPointR2Bounds(const vector& points, Box* flatBounds) { - - verify(!points.empty()); - - flatBounds->init(toLngLatPoint(points.front()), toLngLatPoint(points.front())); - - vector::const_iterator it = points.begin(); - for (++it; it != points.end(); ++it) { - const S2Point& s2Point = *it; - flatBounds->expandToInclude(toLngLatPoint(s2Point)); - } - } - - static void polygonR2Bounds(const Polygon& polygon, Box* flatBounds) { - *flatBounds = polygon.bounds(); - } - - static void s2RegionR2Bounds(const S2Region& region, Box* flatBounds) { - S2LatLngRect s2Bounds = region.GetRectBound(); - flatBounds->init(Point(s2Bounds.lng_lo().degrees(), s2Bounds.lat_lo().degrees()), - Point(s2Bounds.lng_hi().degrees(), s2Bounds.lat_hi().degrees())); - } - - Box GeometryContainer::R2BoxRegion::buildBounds(const GeometryContainer& geometry) { - - Box bounds; - - if (geometry._point && FLAT == geometry._point->crs) { - bounds.init(geometry._point->oldPoint, geometry._point->oldPoint); - } - else if (geometry._line && FLAT == geometry._line->crs) { - lineR2Bounds(geometry._line->line, &bounds); - } - else if (geometry._cap && FLAT == geometry._cap->crs) { - circleR2Bounds(geometry._cap->circle, &bounds); - } - else if (geometry._box && FLAT == geometry._box->crs) { - bounds = geometry._box->box; - } - else if (geometry._polygon && FLAT == geometry._polygon->crs) { - polygonR2Bounds(geometry._polygon->oldPolygon, &bounds); - } - else if (geometry._multiPoint && FLAT == geometry._multiPoint->crs) { - multiPointR2Bounds(geometry._multiPoint->points, &bounds); - } - else if (geometry._multiLine && FLAT == geometry._multiLine->crs) { - verify(false); - } - else if (geometry._multiPolygon && FLAT == geometry._multiPolygon->crs) { - verify(false); - } - else if (geometry._geometryCollection) { - verify(false); - } - else if (geometry.hasS2Region()) { - // For now, just support spherical cap for $centerSphere and GeoJSON points - verify((geometry._cap && FLAT != geometry._cap->crs) || - (geometry._point && FLAT != geometry._point->crs)); - s2RegionR2Bounds(geometry.getS2Region(), &bounds); - } - - return bounds; - } - - const R2Region& GeometryContainer::getR2Region() const { - return *_r2Region; - } - - 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& 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& 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& lines = c.lines.vector(); - for (size_t i = 0; i < lines.size(); ++i) { - if (!contains(lines[i]->line)) { return false; } - } - - const vector& polys = c.polygons.vector(); - for (size_t i = 0; i < polys.size(); ++i) { - if (!contains(polys[i]->polygon)) { return false; } - } - - const vector& 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& multilines = c.multiLines.vector(); - for (size_t i = 0; i < multilines.size(); ++i) { - const vector& lines = multilines[i]->lines.vector(); - for (size_t j = 0; j < lines.size(); ++j) { - if (!contains(*lines[j])) { return false; } - } - } - - const vector& multipolys = c.multiPolygons.vector(); - for (size_t i = 0; i < multipolys.size(); ++i) { - const vector& 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& 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& polys = _geometryCollection->polygons.vector(); - for (size_t i = 0; i < polys.size(); ++i) { - if (containsPoint(polys[i]->polygon, otherCell, otherPoint)) { return true; } - } - - const vector& multipolys =_geometryCollection->multiPolygons.vector(); - for (size_t i = 0; i < multipolys.size(); ++i) { - const vector& 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 clippedOwned; - vector& 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& 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& polys = _geometryCollection->polygons.vector(); - for (size_t i = 0; i < polys.size(); ++i) { - if (containsLine(polys[i]->polygon, otherLine)) { return true; } - } - - const vector& multipolys =_geometryCollection->multiPolygons.vector(); - for (size_t i = 0; i < multipolys.size(); ++i) { - const vector& 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& 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& polys = _geometryCollection->polygons.vector(); - for (size_t i = 0; i < polys.size(); ++i) { - if (containsPolygon(polys[i]->polygon, otherPolygon)) { return true; } - } - - const vector& multipolys =_geometryCollection->multiPolygons.vector(); - for (size_t i = 0; i < multipolys.size(); ++i) { - const vector& 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& 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& 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& 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& 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& 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& 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 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& 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& 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& 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& 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& 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& 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) { - - 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::isIndexablePoint(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; } - _s2Region.reset(new S2RegionUnion()); - for (size_t i = 0; i < _multiPoint->cells.size(); ++i) { - _s2Region->Add(&_multiPoint->cells[i]); - } - } else if (GeoParser::isMultiLine(obj)) { - _multiLine.reset(new MultiLineWithCRS()); - if (!GeoParser::parseMultiLine(obj, _multiLine.get())) { return false; } - _s2Region.reset(new S2RegionUnion()); - for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) { - _s2Region->Add(_multiLine->lines.vector()[i]); - } - } else if (GeoParser::isMultiPolygon(obj)) { - _multiPolygon.reset(new MultiPolygonWithCRS()); - if (!GeoParser::parseMultiPolygon(obj, _multiPolygon.get())) { return false; } - _s2Region.reset(new S2RegionUnion()); - for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) { - _s2Region->Add(_multiPolygon->polygons.vector()[i]); - } - } else if (GeoParser::isGeometryCollection(obj)) { - _geometryCollection.reset(new GeometryCollection()); - if (!GeoParser::parseGeometryCollection(obj, _geometryCollection.get())) { - return false; - } - _s2Region.reset(new S2RegionUnion()); - for (size_t i = 0; i < _geometryCollection->points.size(); ++i) { - _s2Region->Add(&_geometryCollection->points[i].cell); - } - for (size_t i = 0; i < _geometryCollection->lines.vector().size(); ++i) { - _s2Region->Add(&_geometryCollection->lines.vector()[i]->line); - } - for (size_t i = 0; i < _geometryCollection->polygons.vector().size(); ++i) { - _s2Region->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) { - _s2Region->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) { - _s2Region->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) { - _s2Region->Add(multiPolygon->polygons.vector()[j]); - } - } - } else { - return false; - } - - // If we support R2 regions, build the region immediately - if (hasR2Region()) - _r2Region.reset(new R2BoxRegion(this)); - - return true; - } - - string GeometryContainer::getDebugType() const { - if (NULL != _point) { return "pt"; } - else if (NULL != _line) { return "ln"; } - else if (NULL != _box) { return "bx"; } - else if (NULL != _polygon) { return "pl"; } - else if (NULL != _cap ) { return "cc"; } - else if (NULL != _multiPoint) { return "mp"; } - else if (NULL != _multiLine) { return "ml"; } - else if (NULL != _multiPolygon) { return "my"; } - else if (NULL != _geometryCollection) { return "gc"; } - else { - invariant(false); - return ""; - } - } - - CRS GeometryContainer::getNativeCRS() const { - - // TODO: Fix geometry collection reporting when/if we support multiple CRSes - - if (NULL != _point) { return _point->crs; } - else if (NULL != _line) { return _line->crs; } - else if (NULL != _box) { return _box->crs; } - else if (NULL != _polygon) { return _polygon->crs; } - else if (NULL != _cap ) { return _cap->crs; } - else if (NULL != _multiPoint) { return _multiPoint->crs; } - else if (NULL != _multiLine) { return _multiLine->crs; } - else if (NULL != _multiPolygon) { return _multiPolygon->crs; } - else if (NULL != _geometryCollection) { return SPHERE; } - else { - invariant(false); - return FLAT; - } - } - - bool GeometryContainer::supportsProject(CRS otherCRS) const { - - // TODO: Fix geometry collection reporting when/if we support more CRSes - - if (NULL != _point) { - if (_point->crs == otherCRS) return true; - // SPHERE can always go FLAT, but FLAT may not always go back to SPHERE - return _point->crs == SPHERE || _point->flatUpgradedToSphere; - } - else if (NULL != _line) { return _line->crs == otherCRS; } - else if (NULL != _box) { return _box->crs == otherCRS; } - else if (NULL != _polygon) { return _polygon->crs == otherCRS; } - else if (NULL != _cap ) { return _cap->crs == otherCRS; } - else if (NULL != _multiPoint) { return _multiPoint->crs == otherCRS; } - else if (NULL != _multiLine) { return _multiLine->crs == otherCRS; } - else if (NULL != _multiPolygon) { return _multiPolygon->crs == otherCRS; } - else if (NULL != _geometryCollection) { return SPHERE == otherCRS; } - else { - invariant(false); - return false; - } - } - - void GeometryContainer::projectInto(CRS otherCRS) { - - if (otherCRS == getNativeCRS()) - return; - - invariant(NULL != _point); - - if (FLAT == _point->crs) { - invariant(_point->flatUpgradedToSphere); - _point->crs = SPHERE; - } - else { - invariant(FLAT == otherCRS); - S2LatLng latLng(_point->point); - _point->oldPoint = Point(latLng.lng().degrees(), latLng.lat().degrees()); - _point->flatUpgradedToSphere = true; - _point->crs = FLAT; - } - } - - static double s2MinDistanceRad(const S2Point& s2Point, const MultiPointWithCRS& s2MultiPoint) { - - double minDistance = -1; - for (vector::const_iterator it = s2MultiPoint.points.begin(); - it != s2MultiPoint.points.end(); ++it) { - - double nextDistance = S2Distance::distanceRad(s2Point, *it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - return minDistance; - } - - static double s2MinDistanceRad(const S2Point& s2Point, const MultiLineWithCRS& s2MultiLine) { - - double minDistance = -1; - for (vector::const_iterator it = s2MultiLine.lines.vector().begin(); - it != s2MultiLine.lines.vector().end(); ++it) { - - double nextDistance = S2Distance::minDistanceRad(s2Point, **it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - return minDistance; - } - - static double s2MinDistanceRad(const S2Point& s2Point, const MultiPolygonWithCRS& s2MultiPolygon) { - - double minDistance = -1; - for (vector::const_iterator it = s2MultiPolygon.polygons.vector().begin(); - it != s2MultiPolygon.polygons.vector().end(); ++it) { - - double nextDistance = S2Distance::minDistanceRad(s2Point, **it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - return minDistance; - } - - static double s2MinDistanceRad(const S2Point& s2Point, - const GeometryCollection& geometryCollection) { - - double minDistance = -1; - for (vector::const_iterator it = geometryCollection.points.begin(); - it != geometryCollection.points.end(); ++it) { - - invariant(SPHERE == it->crs); - double nextDistance = S2Distance::distanceRad(s2Point, it->point); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - for (vector::const_iterator it = geometryCollection.lines.vector().begin(); - it != geometryCollection.lines.vector().end(); ++it) { - - invariant(SPHERE == (*it)->crs); - double nextDistance = S2Distance::minDistanceRad(s2Point, (*it)->line); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - for (vector::const_iterator it = geometryCollection.polygons.vector().begin(); - it != geometryCollection.polygons.vector().end(); ++it) { - - invariant(SPHERE == (*it)->crs); - double nextDistance = S2Distance::minDistanceRad(s2Point, (*it)->polygon); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - for (vector::const_iterator it = geometryCollection.multiPoints.vector() - .begin(); it != geometryCollection.multiPoints.vector().end(); ++it) { - - double nextDistance = s2MinDistanceRad(s2Point, **it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - for (vector::const_iterator it = geometryCollection.multiLines.vector() - .begin(); it != geometryCollection.multiLines.vector().end(); ++it) { - - double nextDistance = s2MinDistanceRad(s2Point, **it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - for (vector::const_iterator it = geometryCollection.multiPolygons - .vector().begin(); it != geometryCollection.multiPolygons.vector().end(); ++it) { - - double nextDistance = s2MinDistanceRad(s2Point, **it); - if (minDistance < 0 || nextDistance < minDistance) { - minDistance = nextDistance; - } - } - - return minDistance; - } - - double GeometryContainer::minDistance(const PointWithCRS& otherPoint) const { - - const CRS crs = getNativeCRS(); - - if (FLAT == crs) { - - invariant(NULL != _point); - - if (FLAT == otherPoint.crs) { - return distance(_point->oldPoint, otherPoint.oldPoint); - } - else { - S2LatLng latLng(otherPoint.point); - return distance(_point->oldPoint, - Point(latLng.lng().degrees(), latLng.lat().degrees())); - } - } - else { - invariant(SPHERE == crs); - invariant(FLAT != otherPoint.crs || otherPoint.flatUpgradedToSphere); - - double minDistance = -1; - - if (NULL != _point) { - minDistance = S2Distance::distanceRad(otherPoint.point, _point->point); - } - else if (NULL != _line) { - minDistance = S2Distance::minDistanceRad(otherPoint.point, _line->line); - } - else if (NULL != _polygon) { - minDistance = S2Distance::minDistanceRad(otherPoint.point, _polygon->polygon); - } - else if (NULL != _cap) { - minDistance = S2Distance::minDistanceRad(otherPoint.point, _cap->cap); - } - else if (NULL != _multiPoint) { - minDistance = s2MinDistanceRad(otherPoint.point, *_multiPoint); - } - else if (NULL != _multiLine) { - minDistance = s2MinDistanceRad(otherPoint.point, *_multiLine); - } - else if (NULL != _multiPolygon) { - minDistance = s2MinDistanceRad(otherPoint.point, *_multiPolygon); - } - else if (NULL != _geometryCollection) { - minDistance = s2MinDistanceRad(otherPoint.point, *_geometryCollection); - } - - invariant(minDistance != -1); - return minDistance * kRadiusOfEarthInMeters; - } - } - - const CapWithCRS* GeometryContainer::getCapGeometryHack() const { - return _cap.get(); - } - -} // namespace mongo diff --git a/src/mongo/db/geo/geoquery.h b/src/mongo/db/geo/geoquery.h deleted file mode 100644 index f8085b2db52..00000000000 --- a/src/mongo/db/geo/geoquery.h +++ /dev/null @@ -1,238 +0,0 @@ -/** -* Copyright (C) 2013 10gen 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 . -* -* 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. -*/ - -#pragma once - -#include "mongo/base/disallow_copying.h" -#include "mongo/db/geo/geoparser.h" -#include "mongo/db/geo/shapes.h" -#include "mongo/util/mongoutils/str.h" -#include "third_party/s2/s2regionunion.h" - -namespace mongo { - - class GeometryContainer { - MONGO_DISALLOW_COPYING(GeometryContainer); - public: - - /** - * Creates an empty geometry container which may then be loaded from BSON or directly. - */ - GeometryContainer(); - - /** - * Loads an empty GeometryContainer from BSON - */ - bool parseFrom(const BSONObj &obj); - - /** - * Is the geometry any of {Point, Line, Polygon}? - */ - bool isSimpleContainer() const; - - /** - * Reports the CRS of the contained geometry. - * TODO: Rework once we have collections of multiple CRSes - */ - CRS getNativeCRS() const; - - /** - * Whether or not this geometry can be projected into a particular CRS - */ - bool supportsProject(CRS crs) const; - - /** - * Projects the current geometry into the supplied crs. - * It is an error to call this function if canProjectInto(crs) is false. - */ - void projectInto(CRS crs); - - /** - * Minimum distance between this geometry and the supplied point. - * TODO: Rework and generalize to full GeometryContainer distance - */ - double minDistance(const PointWithCRS& point) const; - - /** - * Only polygons (and aggregate types thereof) support contains. - */ - bool supportsContains() const; - - /** - * To check containment, we iterate over the otherContainer's geometries. If we don't - * contain any sub-geometry of the otherContainer, the otherContainer is not contained - * within us. If each sub-geometry of the otherContainer is contained within us, we contain - * the entire otherContainer. - */ - bool contains(const GeometryContainer& otherContainer) const; - - /** - * To check intersection, we iterate over the otherContainer's geometries, checking each - * geometry to see if we intersect it. If we intersect one geometry, we intersect the - * entire other container. - */ - bool intersects(const GeometryContainer& otherContainer) const; - - // Region which can be used to generate a covering of the query object in the S2 space. - bool hasS2Region() const; - const S2Region& getS2Region() const; - - // Region which can be used to generate a covering of the query object in euclidean space. - bool hasR2Region() const; - const R2Region& getR2Region() const; - - // Returns a string related to the type of the geometry (for debugging queries) - std::string getDebugType() const; - - // Needed for 2D wrapping check (for now) - // TODO: Remove these hacks - const CapWithCRS* getCapGeometryHack() const; - - private: - - class R2BoxRegion; - - // Does 'this' intersect with the provided type? - bool intersects(const S2Cell& otherPoint) const; - bool intersects(const S2Polyline& otherLine) const; - bool intersects(const S2Polygon& otherPolygon) const; - // These three just iterate over the geometries and call the 3 methods above. - bool intersects(const MultiPointWithCRS& otherMultiPoint) const; - bool intersects(const MultiLineWithCRS& otherMultiLine) const; - bool intersects(const MultiPolygonWithCRS& otherMultiPolygon) const; - - // Used when 'this' has a polygon somewhere, either in _polygon or _multiPolygon or - // _geometryCollection. - bool contains(const S2Cell& otherCell, const S2Point& otherPoint) const; - bool contains(const S2Polyline& otherLine) const; - bool contains(const S2Polygon& otherPolygon) const; - - // Only one of these shared_ptrs should be non-NULL. S2Region is a - // superclass but it only supports testing against S2Cells. We need - // the most specific class we can get. - scoped_ptr _point; - scoped_ptr _line; - scoped_ptr _box; - scoped_ptr _polygon; - scoped_ptr _cap; - scoped_ptr _multiPoint; - scoped_ptr _multiLine; - scoped_ptr _multiPolygon; - scoped_ptr _geometryCollection; - - // Cached for use during covering calculations - // TODO: _s2Region is currently generated immediately - don't necessarily need to do this - scoped_ptr _s2Region; - scoped_ptr _r2Region; - }; - - // TODO: Make a struct, turn parse stuff into something like - // static Status parseNearQuery(const BSONObj& obj, NearQuery** out); - class NearQuery { - public: - NearQuery() - : minDistance(0), - maxDistance(std::numeric_limits::max()), - isNearSphere(false) { } - - NearQuery(const std::string& f) - : field(f), - minDistance(0), - maxDistance(std::numeric_limits::max()), - isNearSphere(false) { } - - Status parseFrom(const BSONObj &obj); - - CRS getQueryCRS() const { - return isNearSphere ? SPHERE : centroid.crs; - } - - bool unitsAreRadians() const { - return isNearSphere && FLAT == centroid.crs; - } - - bool isWrappingQuery() const { - return SPHERE == centroid.crs && !isNearSphere; - } - - // The name of the field that contains the geometry. - std::string field; - - // The starting point of the near search. - PointWithCRS centroid; - - // Min and max distance from centroid that we're willing to search. - // Distance is in units of the geometry's CRS, except SPHERE and isNearSphere => radians - double minDistance; - double maxDistance; - - // It's either $near or $nearSphere. - bool isNearSphere; - - std::string toString() const { - std::stringstream ss; - ss << " field=" << field; - ss << " maxdist=" << maxDistance; - ss << " isNearSphere=" << isNearSphere; - return ss.str(); - } - - private: - bool parseLegacyQuery(const BSONObj &obj); - Status parseNewQuery(const BSONObj &obj); - }; - - // This represents either a $within or a $geoIntersects. - class GeoQuery { - public: - GeoQuery() : field(""), predicate(INVALID) {} - GeoQuery(const std::string& f) : field(f), predicate(INVALID) {} - - enum Predicate { - WITHIN, - INTERSECT, - INVALID - }; - - bool parseFrom(const BSONObj &obj); - - std::string getField() const { return field; } - Predicate getPred() const { return predicate; } - const GeometryContainer& getGeometry() const { return geoContainer; } - - private: - // Try to parse the provided object into the right place. - bool parseLegacyQuery(const BSONObj &obj); - bool parseNewQuery(const BSONObj &obj); - - // Name of the field in the query. - std::string field; - GeometryContainer geoContainer; - Predicate predicate; - }; -} // namespace mongo diff --git a/src/mongo/db/geo/r2_region_coverer_test.cpp b/src/mongo/db/geo/r2_region_coverer_test.cpp index b58b7246df6..e3d1c980c71 100644 --- a/src/mongo/db/geo/r2_region_coverer_test.cpp +++ b/src/mongo/db/geo/r2_region_coverer_test.cpp @@ -31,7 +31,7 @@ #include "mongo/unittest/unittest.h" #include "mongo/platform/random.h" #include "mongo/bson/bsonmisc.h" -#include "mongo/db/geo/geoquery.h" // TODO: Move GeometryContainer out of geoquery.h +#include "mongo/db/geo/geometry_container.h" namespace { diff --git a/src/mongo/db/geo/s2common.cpp b/src/mongo/db/geo/s2common.cpp index 2dd2082c96a..9be2465640a 100644 --- a/src/mongo/db/geo/s2common.cpp +++ b/src/mongo/db/geo/s2common.cpp @@ -30,7 +30,6 @@ #include "mongo/db/geo/geoconstants.h" #include "mongo/db/geo/geoparser.h" -#include "mongo/db/geo/geoquery.h" #include "mongo/db/geo/s2.h" #include "third_party/s2/s2cell.h" #include "third_party/s2/s2regioncoverer.h" diff --git a/src/mongo/db/geo/shapes.cpp b/src/mongo/db/geo/shapes.cpp index 9c1e5b80745..14a4fa3de04 100644 --- a/src/mongo/db/geo/shapes.cpp +++ b/src/mongo/db/geo/shapes.cpp @@ -563,11 +563,8 @@ namespace mongo { } // Technically lat/long bounds, not really tied to earth radius. - void checkEarthBounds(const Point &p) { - uassert(14808, str::stream() << "point " << p.toString() - << " must be in earth-like bounds of long " - << ": [-180, 180], lat : [-90, 90] ", - p.x >= -180 && p.x <= 180 && p.y >= -90 && p.y <= 90); + bool isValidLngLat(double lng, double lat) { + return abs(lng) <= 180 && abs(lat) <= 90; } double distance(const Point& p1, const Point &p2) { @@ -750,4 +747,44 @@ namespace mongo { return edgesIntersectsWithBox(polygon.points(), box); } + bool ShapeProjection::supportsProject(const PointWithCRS& point, const CRS crs) { + + // Can always trivially project or project from SPHERE->FLAT + if (point.crs == crs || point.crs == SPHERE) + return true; + + invariant(point.crs == FLAT); + // If crs is FLAT, we might be able to upgrade the point to SPHERE if it's a valid SPHERE + // point (lng/lat in bounds). In this case, we can use FLAT data with SPHERE predicates. + return isValidLngLat(point.oldPoint.x, point.oldPoint.y); + } + + void ShapeProjection::projectInto(PointWithCRS* point, CRS crs) { + dassert(supportsProject(*point, crs)); + + if (point->crs == crs) + return; + + if (FLAT == point->crs) { + invariant(SPHERE == crs); + + // Note that it's (lat, lng) for S2 but (lng, lat) for MongoDB. + S2LatLng latLng = + S2LatLng::FromDegrees(point->oldPoint.y, point->oldPoint.x).Normalized(); + dassert(latLng.is_valid()); + point->point = latLng.ToPoint(); + point->cell = S2Cell(point->point); + point->crs = SPHERE; + } + else { + invariant(SPHERE == point->crs); + invariant(FLAT == crs); + + // Just remove the additional spherical information + point->point = S2Point(); + point->cell = S2Cell(); + point->crs = FLAT; + } + } + } // namespace mongo diff --git a/src/mongo/db/geo/shapes.h b/src/mongo/db/geo/shapes.h index fd79c3680e4..4091ce9357c 100644 --- a/src/mongo/db/geo/shapes.h +++ b/src/mongo/db/geo/shapes.h @@ -62,7 +62,7 @@ namespace mongo { cos(deg2rad(std::max(-89.0, y - maxDistDegrees)))); } - void checkEarthBounds(const Point &p); + bool isValidLngLat(double lng, double lat); bool linesIntersect(const Point& pA, const Point& pB, const Point& pC, const Point& pD); bool circleContainsBox(const Circle& circle, const Box& box); bool circleInteriorContainsBox(const Circle& circle, const Box& box); @@ -254,17 +254,19 @@ namespace mongo { SPHERE }; + // TODO: Make S2 less integral to these types - additional S2 shapes should be an optimization + // when our CRS is not projected, i.e. SPHERE for now. + // Generic shapes (Point, Line, Polygon) should hold the raw coordinate data - right now oldXXX + // is a misnomer - this is the *original* data and the S2 transformation just an optimization. + struct PointWithCRS { - PointWithCRS() : crs(UNSET), flatUpgradedToSphere(false) {} + PointWithCRS() : crs(UNSET) {} S2Point point; S2Cell cell; Point oldPoint; CRS crs; - // If crs is FLAT, we might be able to upgrade the point to SPHERE if it's a valid SPHERE - // point (lng/lat in bounds). In this case, we can use FLAT data with SPHERE predicates. - bool flatUpgradedToSphere; }; struct LineWithCRS { @@ -344,4 +346,13 @@ namespace mongo { } }; + // + // Projection functions - we don't project types other than points for now + // + + struct ShapeProjection { + static bool supportsProject(const PointWithCRS& point, const CRS crs); + static void projectInto(PointWithCRS* point, CRS crs); + }; + } // namespace mongo diff --git a/src/mongo/db/index/SConscript b/src/mongo/db/index/SConscript index 6cf5084abb2..8d062d13878 100644 --- a/src/mongo/db/index/SConscript +++ b/src/mongo/db/index/SConscript @@ -11,9 +11,8 @@ env.Library( LIBDEPS=[ '$BUILD_DIR/mongo/bson', '$BUILD_DIR/mongo/db/fts/base', - '$BUILD_DIR/mongo/geometry', - '$BUILD_DIR/mongo/geoparser', - '$BUILD_DIR/mongo/geoquery', + '$BUILD_DIR/mongo/db/geo/geometry', + '$BUILD_DIR/mongo/db/geo/geoparser', '$BUILD_DIR/mongo/index_names', '$BUILD_DIR/third_party/s2/s2', ], diff --git a/src/mongo/db/index/expression_index.h b/src/mongo/db/index/expression_index.h deleted file mode 100644 index f3877cb8d0e..00000000000 --- a/src/mongo/db/index/expression_index.h +++ /dev/null @@ -1,217 +0,0 @@ -/** - * Copyright (C) 2013 10gen 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 . - * - * 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. - */ - -#pragma once - -#include "third_party/s2/s2regioncoverer.h" - -#include "mongo/db/jsobj.h" -#include "mongo/db/geo/hash.h" -#include "mongo/db/geo/geoquery.h" -#include "mongo/db/geo/r2_region_coverer.h" -#include "mongo/db/hasher.h" -#include "mongo/db/query/index_bounds_builder.h" - -namespace mongo { - - /** - * Functions that compute expression index mappings. - * - * TODO: I think we could structure this more generally with respect to planning. - */ - class ExpressionMapping { - public: - static BSONObj hash(const BSONElement& value) { - BSONObjBuilder bob; - bob.append("", BSONElementHasher::hash64(value, BSONElementHasher::DEFAULT_HASH_SEED)); - return bob.obj(); - } - - // For debugging only - static std::string toCoveringString(const GeoHashConverter& hashConverter, - const set& covering) { - string result = "["; - for (set::const_iterator it = covering.begin(); it != covering.end(); - ++it) { - - if (it != covering.begin()) result += ", "; - - const GeoHash& geoHash = *it; - - result += hashConverter.unhashToBox(geoHash).toString(); - result += " (" + geoHash.toStringHex1() + ")"; - } - - return result + "]"; - } - - static void cover2d(const R2Region& region, - const BSONObj& indexInfoObj, - OrderedIntervalList* oil) { - - GeoHashConverter::Parameters hashParams; - Status paramStatus = GeoHashConverter::parseParameters(indexInfoObj, &hashParams); - verify(paramStatus.isOK()); // We validated the parameters when creating the index - - GeoHashConverter hashConverter(hashParams); - R2RegionCoverer coverer(&hashConverter); - coverer.setMaxLevel(hashConverter.getBits()); - - // TODO: Maybe slightly optimize by returning results in order - vector unorderedCovering; - coverer.getCovering(region, &unorderedCovering); - set covering(unorderedCovering.begin(), unorderedCovering.end()); - - for (set::const_iterator it = covering.begin(); it != covering.end(); - ++it) { - - const GeoHash& geoHash = *it; - BSONObjBuilder builder; - geoHash.appendHashMin(&builder, ""); - geoHash.appendHashMax(&builder, ""); - - oil->intervals.push_back(IndexBoundsBuilder::makeRangeInterval(builder.obj(), - true, - true)); - } - } - - // TODO: what should we really pass in for indexInfoObj? - static void cover2dsphere(const S2Region& region, - const BSONObj& indexInfoObj, - OrderedIntervalList* oilOut) { - - int coarsestIndexedLevel; - BSONElement ce = indexInfoObj["coarsestIndexedLevel"]; - if (ce.isNumber()) { - coarsestIndexedLevel = ce.numberInt(); - } - else { - coarsestIndexedLevel = - S2::kAvgEdge.GetClosestLevel(100 * 1000.0 / kRadiusOfEarthInMeters); - } - - // The min level of our covering is the level whose cells are the closest match to the - // *area* of the region (or the max indexed level, whichever is smaller) The max level - // is 4 sizes larger. - double edgeLen = sqrt(region.GetRectBound().Area()); - S2RegionCoverer coverer; - coverer.set_min_level(min(coarsestIndexedLevel, - 2 + S2::kAvgEdge.GetClosestLevel(edgeLen))); - coverer.set_max_level(4 + coverer.min_level()); - - std::vector cover; - coverer.GetCovering(region, &cover); - - // Look at the cells we cover and all cells that are within our covering and finer. - // Anything with our cover as a strict prefix is contained within the cover and should - // be intersection tested. - bool considerCoarser = false; - std::set intervalSet; - for (size_t i = 0; i < cover.size(); ++i) { - intervalSet.insert(cover[i].toString()); - // If any of our covers could be covered by something in the index, we have - // to look at things coarser. - if (cover[i].level() > coarsestIndexedLevel) { - considerCoarser = true; - } - } - - std::set exactSet; - if (considerCoarser) { - // Look at the cells that cover us. We want to look at every cell that contains the - // covering we would index on if we were to insert the query geometry. We generate - // the would-index-with-this-covering and find all the cells strictly containing the - // cells in that set, until we hit the coarsest indexed cell. We use equality, not - // a prefix match. Why not prefix? Because we've already looked at everything - // finer or as fine as our initial covering. - // - // Say we have a fine point with cell id 212121, we go up one, get 21212, we don't - // want to look at cells 21212[not-1] because we know they're not going to intersect - // with 212121, but entries inserted with cell value 21212 (no trailing digits) may. - // And we've already looked at points with the cell id 211111 from the regex search - // created above, so we only want things where the value of the last digit is not - // stored (and therefore could be 1). - for (size_t i = 0; i < cover.size(); ++i) { - for (S2CellId id = cover[i].parent(); id.level() >= coarsestIndexedLevel; - id = id.parent()) { - exactSet.insert(id.toString()); - } - } - } - - // We turned the cell IDs into strings which define point intervals or prefixes of - // strings we want to look for. - std::set::iterator exactIt = exactSet.begin(); - std::set::iterator intervalIt = intervalSet.begin(); - while (exactSet.end() != exactIt && intervalSet.end() != intervalIt) { - const std::string& exact = *exactIt; - const std::string& ival = *intervalIt; - if (exact < ival) { - // add exact - oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(exact)); - exactIt++; - } - else { - std::string end = ival; - end[end.size() - 1]++; - oilOut->intervals.push_back( - IndexBoundsBuilder::makeRangeInterval(ival, end, true, false)); - intervalIt++; - } - } - - if (exactSet.end() != exactIt) { - verify(intervalSet.end() == intervalIt); - do { - oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(*exactIt)); - exactIt++; - } while (exactSet.end() != exactIt); - } - else if (intervalSet.end() != intervalIt) { - verify(exactSet.end() == exactIt); - do { - const std::string& ival = *intervalIt; - std::string end = ival; - end[end.size() - 1]++; - oilOut->intervals.push_back( - IndexBoundsBuilder::makeRangeInterval(ival, end, true, false)); - intervalIt++; - } while (intervalSet.end() != intervalIt); - } - - // Make sure that our intervals don't overlap each other and are ordered correctly. - // This perhaps should only be done in debug mode. - if (!oilOut->isValidFor(1)) { - cout << "check your assumptions! OIL = " << oilOut->toString() << std::endl; - verify(0); - } - } - }; - -} // namespace mongo diff --git a/src/mongo/db/index/expression_keys_private.cpp b/src/mongo/db/index/expression_keys_private.cpp index b42d3949a34..9ca7eade530 100644 --- a/src/mongo/db/index/expression_keys_private.cpp +++ b/src/mongo/db/index/expression_keys_private.cpp @@ -32,8 +32,8 @@ #include "mongo/db/fts/fts_index_format.h" #include "mongo/db/geo/geoconstants.h" +#include "mongo/db/geo/geometry_container.h" #include "mongo/db/geo/geoparser.h" -#include "mongo/db/geo/geoquery.h" #include "mongo/db/geo/s2common.h" #include "mongo/db/geo/s2.h" #include "mongo/db/index_names.h" @@ -97,10 +97,14 @@ namespace { return false; } - if (!geoContainer.hasS2Region()) { return false; } + // Project the geometry into spherical space + if (!geoContainer.supportsProject(SPHERE)) + return false; + geoContainer.projectInto(SPHERE); - S2KeysFromRegion(&coverer, geoContainer.getS2Region(), out); + invariant(geoContainer.hasS2Region()); + S2KeysFromRegion(&coverer, geoContainer.getS2Region(), out); return true; } diff --git a/src/mongo/db/matcher/expression_geo.cpp b/src/mongo/db/matcher/expression_geo.cpp index 23d28940d01..3c55f8a9133 100644 --- a/src/mongo/db/matcher/expression_geo.cpp +++ b/src/mongo/db/matcher/expression_geo.cpp @@ -52,6 +52,12 @@ namespace mongo { if ( !geometry.parseFrom( e.Obj() ) ) return false; + // Project this geometry into the CRS of the query + if (!geometry.supportsProject(_query->getGeometry().getNativeCRS())) + return false; + + geometry.projectInto(_query->getGeometry().getNativeCRS()); + if (GeoQuery::WITHIN == _query->getPred()) { return _query->getGeometry().contains(geometry); } diff --git a/src/mongo/db/matcher/expression_geo.h b/src/mongo/db/matcher/expression_geo.h index a784dbdabda..0be28de408d 100644 --- a/src/mongo/db/matcher/expression_geo.h +++ b/src/mongo/db/matcher/expression_geo.h @@ -31,7 +31,7 @@ #pragma once -#include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/geo_query.h" #include "mongo/db/matcher/expression.h" #include "mongo/db/matcher/expression_leaf.h" diff --git a/src/mongo/db/query/SConscript b/src/mongo/db/query/SConscript index ca294bc4584..769d6f59aa1 100644 --- a/src/mongo/db/query/SConscript +++ b/src/mongo/db/query/SConscript @@ -65,6 +65,8 @@ env.CppUnitTest( env.Library( target="index_bounds", source=[ + "expression_index.cpp", + "expression_index_knobs.cpp", "index_bounds.cpp", "index_bounds_builder.cpp", "interval.cpp", @@ -75,6 +77,7 @@ env.Library( "$BUILD_DIR/mongo/expressions_geo", "$BUILD_DIR/mongo/index_names", "$BUILD_DIR/mongo/mongohasher", + "$BUILD_DIR/mongo/server_parameters", ], ) diff --git a/src/mongo/db/query/canonical_query_test.cpp b/src/mongo/db/query/canonical_query_test.cpp index 22fb62b3258..73127fbd34f 100644 --- a/src/mongo/db/query/canonical_query_test.cpp +++ b/src/mongo/db/query/canonical_query_test.cpp @@ -625,7 +625,7 @@ namespace { testGetPlanCacheKey("{a: {$near: [0,0], $maxDistance:0.3 }}", "{}", "{}", "gnanrfl"); testGetPlanCacheKey("{a: {$nearSphere: [0,0], $maxDistance: 0.31 }}", "{}", "{}", - "gnansfl"); + "gnanssp"); testGetPlanCacheKey("{a: {$geoNear: {$geometry: {type: 'Point', coordinates: [0,0]}," "$maxDistance:100}}}", "{}", "{}", "gnanrsp"); diff --git a/src/mongo/db/query/expression_index.cpp b/src/mongo/db/query/expression_index.cpp new file mode 100644 index 00000000000..ee49ee574b0 --- /dev/null +++ b/src/mongo/db/query/expression_index.cpp @@ -0,0 +1,209 @@ +/** + * Copyright (C) 2013 10gen 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 . + * + * 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/query/expression_index.h" + +#include "third_party/s2/s2regioncoverer.h" + +#include "mongo/db/geo/geoconstants.h" +#include "mongo/db/geo/hash.h" +#include "mongo/db/geo/r2_region_coverer.h" +#include "mongo/db/hasher.h" + +namespace mongo { + + BSONObj ExpressionMapping::hash(const BSONElement& value) { + BSONObjBuilder bob; + bob.append("", BSONElementHasher::hash64(value, BSONElementHasher::DEFAULT_HASH_SEED)); + return bob.obj(); + } + + // For debugging only + static std::string toCoveringString(const GeoHashConverter& hashConverter, + const set& covering) { + string result = "["; + for (set::const_iterator it = covering.begin(); it != covering.end(); + ++it) { + + if (it != covering.begin()) result += ", "; + + const GeoHash& geoHash = *it; + + result += hashConverter.unhashToBox(geoHash).toString(); + result += " (" + geoHash.toStringHex1() + ")"; + } + + return result + "]"; + } + + void ExpressionMapping::cover2d(const R2Region& region, + const BSONObj& indexInfoObj, + int maxCoveringCells, + OrderedIntervalList* oil) { + + GeoHashConverter::Parameters hashParams; + Status paramStatus = GeoHashConverter::parseParameters(indexInfoObj, &hashParams); + verify(paramStatus.isOK()); // We validated the parameters when creating the index + + GeoHashConverter hashConverter(hashParams); + R2RegionCoverer coverer(&hashConverter); + coverer.setMaxLevel(hashConverter.getBits()); + coverer.setMaxCells(maxCoveringCells); + + // TODO: Maybe slightly optimize by returning results in order + vector unorderedCovering; + coverer.getCovering(region, &unorderedCovering); + set covering(unorderedCovering.begin(), unorderedCovering.end()); + + for (set::const_iterator it = covering.begin(); it != covering.end(); + ++it) { + + const GeoHash& geoHash = *it; + BSONObjBuilder builder; + geoHash.appendHashMin(&builder, ""); + geoHash.appendHashMax(&builder, ""); + + oil->intervals.push_back(IndexBoundsBuilder::makeRangeInterval(builder.obj(), + true, + true)); + } + } + + // TODO: what should we really pass in for indexInfoObj? + void ExpressionMapping::cover2dsphere(const S2Region& region, + const BSONObj& indexInfoObj, + OrderedIntervalList* oilOut) { + + int coarsestIndexedLevel; + BSONElement ce = indexInfoObj["coarsestIndexedLevel"]; + if (ce.isNumber()) { + coarsestIndexedLevel = ce.numberInt(); + } + else { + coarsestIndexedLevel = + S2::kAvgEdge.GetClosestLevel(100 * 1000.0 / kRadiusOfEarthInMeters); + } + + // The min level of our covering is the level whose cells are the closest match to the + // *area* of the region (or the max indexed level, whichever is smaller) The max level + // is 4 sizes larger. + double edgeLen = sqrt(region.GetRectBound().Area()); + S2RegionCoverer coverer; + coverer.set_min_level(min(coarsestIndexedLevel, + 2 + S2::kAvgEdge.GetClosestLevel(edgeLen))); + coverer.set_max_level(4 + coverer.min_level()); + + std::vector cover; + coverer.GetCovering(region, &cover); + + // Look at the cells we cover and all cells that are within our covering and finer. + // Anything with our cover as a strict prefix is contained within the cover and should + // be intersection tested. + bool considerCoarser = false; + std::set intervalSet; + for (size_t i = 0; i < cover.size(); ++i) { + intervalSet.insert(cover[i].toString()); + // If any of our covers could be covered by something in the index, we have + // to look at things coarser. + if (cover[i].level() > coarsestIndexedLevel) { + considerCoarser = true; + } + } + + std::set exactSet; + if (considerCoarser) { + // Look at the cells that cover us. We want to look at every cell that contains the + // covering we would index on if we were to insert the query geometry. We generate + // the would-index-with-this-covering and find all the cells strictly containing the + // cells in that set, until we hit the coarsest indexed cell. We use equality, not + // a prefix match. Why not prefix? Because we've already looked at everything + // finer or as fine as our initial covering. + // + // Say we have a fine point with cell id 212121, we go up one, get 21212, we don't + // want to look at cells 21212[not-1] because we know they're not going to intersect + // with 212121, but entries inserted with cell value 21212 (no trailing digits) may. + // And we've already looked at points with the cell id 211111 from the regex search + // created above, so we only want things where the value of the last digit is not + // stored (and therefore could be 1). + for (size_t i = 0; i < cover.size(); ++i) { + for (S2CellId id = cover[i].parent(); id.level() >= coarsestIndexedLevel; + id = id.parent()) { + exactSet.insert(id.toString()); + } + } + } + + // We turned the cell IDs into strings which define point intervals or prefixes of + // strings we want to look for. + std::set::iterator exactIt = exactSet.begin(); + std::set::iterator intervalIt = intervalSet.begin(); + while (exactSet.end() != exactIt && intervalSet.end() != intervalIt) { + const std::string& exact = *exactIt; + const std::string& ival = *intervalIt; + if (exact < ival) { + // add exact + oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(exact)); + exactIt++; + } + else { + std::string end = ival; + end[end.size() - 1]++; + oilOut->intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(ival, end, true, false)); + intervalIt++; + } + } + + if (exactSet.end() != exactIt) { + verify(intervalSet.end() == intervalIt); + do { + oilOut->intervals.push_back(IndexBoundsBuilder::makePointInterval(*exactIt)); + exactIt++; + } while (exactSet.end() != exactIt); + } + else if (intervalSet.end() != intervalIt) { + verify(exactSet.end() == exactIt); + do { + const std::string& ival = *intervalIt; + std::string end = ival; + end[end.size() - 1]++; + oilOut->intervals.push_back( + IndexBoundsBuilder::makeRangeInterval(ival, end, true, false)); + intervalIt++; + } while (intervalSet.end() != intervalIt); + } + + // Make sure that our intervals don't overlap each other and are ordered correctly. + // This perhaps should only be done in debug mode. + if (!oilOut->isValidFor(1)) { + cout << "check your assumptions! OIL = " << oilOut->toString() << std::endl; + verify(0); + } + } + +} // namespace mongo diff --git a/src/mongo/db/query/expression_index.h b/src/mongo/db/query/expression_index.h new file mode 100644 index 00000000000..b50c2037e21 --- /dev/null +++ b/src/mongo/db/query/expression_index.h @@ -0,0 +1,60 @@ +/** + * Copyright (C) 2013 10gen 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 . + * + * 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. + */ + +#pragma once + +#include "third_party/s2/s2region.h" + +#include "mongo/db/jsobj.h" +#include "mongo/db/geo/shapes.h" +#include "mongo/db/query/index_bounds_builder.h" // For OrderedIntervalList + +namespace mongo { + + /** + * Functions that compute expression index mappings. + * + * TODO: I think we could structure this more generally with respect to planning. + */ + class ExpressionMapping { + public: + + static BSONObj hash(const BSONElement& value); + + static void cover2d(const R2Region& region, + const BSONObj& indexInfoObj, + int maxCoveringCells, + OrderedIntervalList* oil); + + // TODO: what should we really pass in for indexInfoObj? + static void cover2dsphere(const S2Region& region, + const BSONObj& indexInfoObj, + OrderedIntervalList* oilOut); + }; + +} // namespace mongo diff --git a/src/mongo/db/query/expression_index_knobs.cpp b/src/mongo/db/query/expression_index_knobs.cpp new file mode 100644 index 00000000000..4dd8dfe69c1 --- /dev/null +++ b/src/mongo/db/query/expression_index_knobs.cpp @@ -0,0 +1,39 @@ +/** + * Copyright (C) 2014 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 . + * + * 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/query/expression_index_knobs.h" +#include "mongo/db/server_options.h" +#include "mongo/db/server_parameters.h" + +namespace mongo { + + MONGO_EXPORT_SERVER_PARAMETER(internalGeoPredicateQuery2DMaxCoveringCells, int, 16); + + MONGO_EXPORT_SERVER_PARAMETER(internalGeoNearQuery2DMaxCoveringCells, int, 16); + +} // namespace mongo diff --git a/src/mongo/db/query/expression_index_knobs.h b/src/mongo/db/query/expression_index_knobs.h new file mode 100644 index 00000000000..6dcfbaf2592 --- /dev/null +++ b/src/mongo/db/query/expression_index_knobs.h @@ -0,0 +1,47 @@ +/** + * Copyright (C) 2014 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 . + * + * 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. + */ + +#pragma once + +namespace mongo { + + // + // Geo Query knobs + // + + /** + * The maximum number of cells to use for 2D geo query covering for predicate queries + */ + extern int internalGeoPredicateQuery2DMaxCoveringCells; + + /** + * The maximum number of cells to use for 2D geo query covering for predicate queries + */ + extern int internalGeoNearQuery2DMaxCoveringCells; + +} // namespace mongo diff --git a/src/mongo/db/query/index_bounds_builder.cpp b/src/mongo/db/query/index_bounds_builder.cpp index 63e1f7571a5..d9e423f9e07 100644 --- a/src/mongo/db/query/index_bounds_builder.cpp +++ b/src/mongo/db/query/index_bounds_builder.cpp @@ -31,10 +31,12 @@ #include #include "mongo/db/geo/geoconstants.h" #include "mongo/db/geo/s2common.h" -#include "mongo/db/index/expression_index.h" #include "mongo/db/matcher/expression_geo.h" +#include "mongo/db/query/expression_index.h" +#include "mongo/db/query/expression_index_knobs.h" #include "mongo/db/query/indexability.h" #include "mongo/db/query/qlog.h" +#include "mongo/db/query/query_knobs.h" #include "mongo/util/mongoutils/str.h" #include "mongo/db/geo/s2.h" #include "third_party/s2/s2cell.h" @@ -584,7 +586,12 @@ namespace mongo { else if (mongoutils::str::equals("2d", elt.valuestrsafe())) { verify(gme->getGeoQuery().getGeometry().hasR2Region()); const R2Region& region = gme->getGeoQuery().getGeometry().getR2Region(); - ExpressionMapping::cover2d(region, index.infoObj, oilOut); + + ExpressionMapping::cover2d(region, + index.infoObj, + internalGeoPredicateQuery2DMaxCoveringCells, + oilOut); + *tightnessOut = IndexBoundsBuilder::INEXACT_FETCH; } else { diff --git a/src/mongo/db/query/planner_ixselect.cpp b/src/mongo/db/query/planner_ixselect.cpp index 8d4252edc6a..61cda0d0eea 100644 --- a/src/mongo/db/query/planner_ixselect.cpp +++ b/src/mongo/db/query/planner_ixselect.cpp @@ -244,16 +244,15 @@ namespace mongo { else if (exprtype == MatchExpression::GEO_NEAR) { GeoNearMatchExpression* gnme = static_cast(node); // Make sure the near query is compatible with 2dsphere. - if (gnme->getData().centroid.crs == SPHERE || gnme->getData().isNearSphere) { - return true; - } + return gnme->getData().centroid.crs == SPHERE; } return false; } else if (IndexNames::GEO_2D == indexedFieldType) { if (exprtype == MatchExpression::GEO_NEAR) { GeoNearMatchExpression* gnme = static_cast(node); - return gnme->getData().centroid.crs == FLAT; + // Make sure the near query is compatible with 2d index + return gnme->getData().centroid.crs == FLAT || !gnme->getData().isWrappingQuery; } else if (exprtype == MatchExpression::GEO) { // 2d only supports within. diff --git a/src/mongo/db/query/query_solution.h b/src/mongo/db/query/query_solution.h index 20c0c265245..0bbea738939 100644 --- a/src/mongo/db/query/query_solution.h +++ b/src/mongo/db/query/query_solution.h @@ -30,7 +30,7 @@ #include "mongo/db/jsobj.h" #include "mongo/db/matcher/expression.h" -#include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/geo_query.h" #include "mongo/db/fts/fts_query.h" #include "mongo/db/query/index_bounds.h" #include "mongo/db/query/plan_cache.h" -- cgit v1.2.1