diff options
author | Hari Khalsa <hkhalsa@10gen.com> | 2013-03-29 15:25:55 -0400 |
---|---|---|
committer | Hari Khalsa <hkhalsa@10gen.com> | 2013-06-25 13:46:36 -0400 |
commit | ba239918c950c254056bf589a943a5e88fd4144c (patch) | |
tree | c65dcc83ab6362e7099caa13093d059cdf2c073e /src | |
parent | b290b65c9e679a42999fe1b0ef7d466b669bd6c9 (diff) | |
download | mongo-ba239918c950c254056bf589a943a5e88fd4144c.tar.gz |
add multipoint/line/poly. SERVER-8907 SERVER-8349
Diffstat (limited to 'src')
-rw-r--r-- | src/mongo/base/owned_pointer_vector.h | 2 | ||||
-rw-r--r-- | src/mongo/db/geo/geonear.cpp | 2 | ||||
-rw-r--r-- | src/mongo/db/geo/geoparser.cpp | 660 | ||||
-rw-r--r-- | src/mongo/db/geo/geoparser.h | 67 | ||||
-rw-r--r-- | src/mongo/db/geo/geoparser_test.cpp | 284 | ||||
-rw-r--r-- | src/mongo/db/geo/geoquery.cpp | 728 | ||||
-rw-r--r-- | src/mongo/db/geo/geoquery.h | 90 | ||||
-rw-r--r-- | src/mongo/db/geo/s2common.cpp | 152 | ||||
-rw-r--r-- | src/mongo/db/geo/s2common.h | 39 | ||||
-rw-r--r-- | src/mongo/db/geo/shapes.cpp | 1 | ||||
-rw-r--r-- | src/mongo/db/geo/shapes.h | 81 | ||||
-rw-r--r-- | src/mongo/db/index/s2_access_method.cpp | 45 | ||||
-rw-r--r-- | src/mongo/db/index/s2_access_method.h | 2 | ||||
-rw-r--r-- | src/mongo/db/index/s2_common.h | 72 | ||||
-rw-r--r-- | src/mongo/db/index/s2_index_cursor.h | 2 | ||||
-rw-r--r-- | src/mongo/db/index/s2_near_cursor.cpp | 36 | ||||
-rw-r--r-- | src/mongo/db/index/s2_near_cursor.h | 2 | ||||
-rw-r--r-- | src/mongo/db/index/s2_simple_cursor.h | 2 | ||||
-rw-r--r-- | src/third_party/s2/s2regionunion.cc | 2 | ||||
-rw-r--r-- | src/third_party/s2/s2regionunion.h | 3 |
20 files changed, 1585 insertions, 687 deletions
diff --git a/src/mongo/base/owned_pointer_vector.h b/src/mongo/base/owned_pointer_vector.h index 4c3f83ae9d5..fffe530bece 100644 --- a/src/mongo/base/owned_pointer_vector.h +++ b/src/mongo/base/owned_pointer_vector.h @@ -35,7 +35,7 @@ namespace mongo { ~OwnedPointerVector(); /** Access the vector. */ - const std::vector<T*>& vector() { return _vector; } + const std::vector<T*>& vector() const { return _vector; } std::vector<T*>& mutableVector() { return _vector; } void clear(); diff --git a/src/mongo/db/geo/geonear.cpp b/src/mongo/db/geo/geonear.cpp index 5f3df84dc39..d9279d62102 100644 --- a/src/mongo/db/geo/geonear.cpp +++ b/src/mongo/db/geo/geonear.cpp @@ -23,12 +23,12 @@ #include "mongo/db/auth/privilege.h" #include "mongo/db/commands.h" #include "mongo/db/curop.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index_names.h" #include "mongo/db/index/2d_index_cursor.h" #include "mongo/db/index/catalog_hack.h" #include "mongo/db/index/index_descriptor.h" #include "mongo/db/index/index_access_method.h" -#include "mongo/db/index/s2_common.h" #include "mongo/db/index/s2_near_cursor.h" #include "mongo/db/jsobj.h" #include "mongo/db/namespace_details.h" diff --git a/src/mongo/db/geo/geoparser.cpp b/src/mongo/db/geo/geoparser.cpp index 3de520be0be..31e1cdee664 100644 --- a/src/mongo/db/geo/geoparser.cpp +++ b/src/mongo/db/geo/geoparser.cpp @@ -16,82 +16,35 @@ #include <string> #include <vector> -#include "mongo/db/jsobj.h" + #include "mongo/db/geo/geoparser.h" +#include "mongo/db/geo/shapes.h" +#include "mongo/db/jsobj.h" #include "mongo/util/mongoutils/str.h" -#include "third_party/s2/s2.h" -#include "third_party/s2/s2cap.h" -#include "third_party/s2/s2cell.h" -#include "third_party/s2/s2latlng.h" -#include "third_party/s2/s2loop.h" -#include "third_party/s2/s2polygon.h" #include "third_party/s2/s2polygonbuilder.h" -#include "third_party/s2/s2polyline.h" namespace mongo { + // This field must be present, and... static const string GEOJSON_TYPE = "type"; - // Have one of these three values: + // Have one of these values: static const string GEOJSON_TYPE_POINT = "Point"; static const string GEOJSON_TYPE_LINESTRING = "LineString"; static const string GEOJSON_TYPE_POLYGON = "Polygon"; + static const string GEOJSON_TYPE_MULTI_POINT = "MultiPoint"; + static const string GEOJSON_TYPE_MULTI_LINESTRING = "MultiLineString"; + static const string GEOJSON_TYPE_MULTI_POLYGON = "MultiPolygon"; + static const string GEOJSON_TYPE_GEOMETRY_COLLECTION = "GeometryCollection"; // This field must also be present. The value depends on the type. static const string GEOJSON_COORDINATES = "coordinates"; + static const string GEOJSON_GEOMETRIES = "geometries"; - //// Utility functions used by GeoParser functions below. - static S2Point coordToPoint(double p0, double p1) { - return S2LatLng::FromDegrees(p1, p0).Normalized().ToPoint(); - } - - static S2Point coordsToPoint(const vector<BSONElement>& coordElt) { - return coordToPoint(coordElt[0].Number(), coordElt[1].Number()); - } - - static void parsePoints(const vector<BSONElement>& coordElt, vector<S2Point>* out) { - for (size_t i = 0; i < coordElt.size(); ++i) { - const vector<BSONElement>& pointElt = coordElt[i].Array(); - if (pointElt.empty()) { continue; } - out->push_back(coordsToPoint(pointElt)); - } - } - - static bool isArrayOfCoordinates(const vector<BSONElement>& coordinateArray) { - for (size_t i = 0; i < coordinateArray.size(); ++i) { - // Each coordinate should be an array - if (Array != coordinateArray[i].type()) { return false; } - // ...of two - const vector<BSONElement> &thisCoord = coordinateArray[i].Array(); - if (2 != thisCoord.size()) { return false; } - // ...numbers. - for (size_t j = 0; j < thisCoord.size(); ++j) { - if (!thisCoord[j].isNumber()) { return false; } - } - // ...where the latitude is valid - double lat = thisCoord[1].Number(); - double lng = thisCoord[0].Number(); - if (lat < -90 || lat > 90) { return false; } - if (lng < -180 || lng > 180) { return false; } - } - return true; - } - - // Coordinates looks like [[0,0],[5,0],[5,5],[0,5],[0,0]] - static bool isLoopClosed(const vector<BSONElement>& coordinates) { - double x1, y1, x2, y2; - x1 = coordinates[0].Array()[0].Number(); - y1 = coordinates[0].Array()[1].Number(); - x2 = coordinates[coordinates.size() - 1].Array()[0].Number(); - y2 = coordinates[coordinates.size() - 1].Array()[1].Number(); - return (fabs(x1 - x2) < 1e-6) && fabs(y1 - y2) < 1e-6; - } - - //// What we publicly export - bool GeoParser::isGeoJSONPoint(const BSONObj& obj) { + static bool isGeoJSONPoint(const BSONObj& obj) { BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); if (type.eoo() || (String != type.type())) { return false; } if (GEOJSON_TYPE_POINT != type.String()) { return false; } - if (!crsIsOK(obj)) { + if (!GeoParser::crsIsOK(obj)) { warning() << "Invalid CRS: " << obj.toString() << endl; return false; } @@ -107,23 +60,24 @@ namespace mongo { return lat >= -90 && lat <= 90 && lng >= -180 && lng <= 180; } - void GeoParser::parseGeoJSONPoint(const BSONObj& obj, S2Cell* out) { - S2Point point = coordsToPoint(obj.getFieldDotted(GEOJSON_COORDINATES).Array()); - *out = S2Cell(point); - } - - void GeoParser::parseGeoJSONPoint(const BSONObj& obj, Point* out) { - const vector<BSONElement>& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); - out->x = coords[0].Number(); - out->y = coords[1].Number(); + static bool isLegacyPoint(const BSONObj &obj) { + BSONObjIterator it(obj); + if (!it.more()) { return false; } + BSONElement x = it.next(); + if (!x.isNumber()) { return false; } + if (!it.more()) { return false; } + BSONElement y = it.next(); + if (!y.isNumber()) { return false; } + if (it.more()) { return false; } + return true; } - void GeoParser::parseGeoJSONPoint(const BSONObj& obj, S2Point* out) { - const vector<BSONElement>& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); - *out = coordsToPoint(coords); + static S2Point coordToPoint(double lng, double lat) { + // Note that it's (lat, lng) for S2 but (lng, lat) for MongoDB. + return S2LatLng::FromDegrees(lat, lng).Normalized().ToPoint(); } - void eraseDuplicatePoints(vector<S2Point>* vertices) { + static void eraseDuplicatePoints(vector<S2Point>* vertices) { for (size_t i = 1; i < vertices->size(); ++i) { if ((*vertices)[i - 1] == (*vertices)[i]) { vertices->erase(vertices->begin() + i); @@ -133,67 +87,45 @@ namespace mongo { } } - bool GeoParser::isGeoJSONLineString(const BSONObj& obj) { - BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); - if (type.eoo() || (String != type.type())) { return false; } - if (GEOJSON_TYPE_LINESTRING != type.String()) { return false; } - - if (!crsIsOK(obj)) { - warning() << "Invalid CRS: " << obj.toString() << endl; - return false; + static bool isArrayOfCoordinates(const vector<BSONElement>& coordinateArray) { + for (size_t i = 0; i < coordinateArray.size(); ++i) { + // Each coordinate should be an array + if (Array != coordinateArray[i].type()) { return false; } + // ...of two + const vector<BSONElement> &thisCoord = coordinateArray[i].Array(); + if (2 != thisCoord.size()) { return false; } + // ...numbers. + for (size_t j = 0; j < thisCoord.size(); ++j) { + if (!thisCoord[j].isNumber()) { return false; } + } + // ...where the latitude is valid + double lat = thisCoord[1].Number(); + double lng = thisCoord[0].Number(); + if (lat < -90 || lat > 90) { return false; } + if (lng < -180 || lng > 180) { return false; } } + return true; + } - BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); - if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + static void parsePoints(const vector<BSONElement>& coordElt, vector<S2Point>* out) { + for (size_t i = 0; i < coordElt.size(); ++i) { + const vector<BSONElement>& pointElt = coordElt[i].Array(); + if (pointElt.empty()) { continue; } + out->push_back(coordToPoint(pointElt[0].Number(), pointElt[1].Number())); + } + } - const vector<BSONElement>& coordinateArray = coordElt.Array(); + static bool isValidLineString(const vector<BSONElement>& coordinateArray) { if (coordinateArray.size() < 2) { return false; } if (!isArrayOfCoordinates(coordinateArray)) { return false; } vector<S2Point> vertices; - parsePoints(obj.getFieldDotted(GEOJSON_COORDINATES).Array(), &vertices); + parsePoints(coordinateArray, &vertices); eraseDuplicatePoints(&vertices); return S2Polyline::IsValid(vertices); } - void GeoParser::parseGeoJSONLineString(const BSONObj& obj, S2Polyline* out) { - vector<S2Point> vertices; - parsePoints(obj.getFieldDotted(GEOJSON_COORDINATES).Array(), &vertices); - eraseDuplicatePoints(&vertices); - out->Init(vertices); - } - - bool GeoParser::isGeoJSONPolygon(const BSONObj& obj) { - BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); - if (type.eoo() || (String != type.type())) { return false; } - if (GEOJSON_TYPE_POLYGON != type.String()) { return false; } - - if (!crsIsOK(obj)) { - warning() << "Invalid CRS: " << obj.toString() << endl; - return false; - } - - BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); - if (coordElt.eoo() || (Array != coordElt.type())) { return false; } - - const vector<BSONElement>& coordinates = coordElt.Array(); - // Must be at least one element, the outer shell - if (coordinates.empty()) { return false; } - // Verify that the shell is a bunch'a coordinates. - for (size_t i = 0; i < coordinates.size(); ++i) { - if (Array != coordinates[i].type()) { return false; } - const vector<BSONElement>& thisLoop = coordinates[i].Array(); - // A triangle is the simplest 2d shape, and we repeat a vertex, so, 4. - if (thisLoop.size() < 4) { return false; } - if (!isArrayOfCoordinates(thisLoop)) { return false; } - if (!isLoopClosed(thisLoop)) { return false; } - } - return true; - } - - void GeoParser::parseGeoJSONPolygon(const BSONObj& obj, S2Polygon* out) { - const vector<BSONElement>& coordinates = - obj.getFieldDotted(GEOJSON_COORDINATES).Array(); - + static void parseGeoJSONPolygonCoordinates(const vector<BSONElement>& coordinates, + const BSONObj &sourceObject, S2Polygon *out) { const vector<BSONElement>& exteriorRing = coordinates[0].Array(); vector<S2Point> exteriorVertices; parsePoints(exteriorRing, &exteriorVertices); @@ -211,7 +143,7 @@ namespace mongo { if (exteriorLoop.is_hole()) { exteriorLoop.Invert(); } - uassert(16693, "Exterior shell of polygon is invalid: " + obj.toString(), + uassert(16693, "Exterior shell of polygon is invalid: " + sourceObject.toString(), exteriorLoop.IsValid()); polyBuilder.AddLoop(&exteriorLoop); @@ -224,7 +156,7 @@ namespace mongo { // Interior rings are clockwise. S2Loop holeLoop(holePoints); holeLoop.Normalize(); - uassert(16694, "Interior hole of polygon is invalid: " + obj.toString(), + uassert(16694, "Interior hole of polygon is invalid: " + sourceObject.toString(), holeLoop.IsValid()); if (!holeLoop.is_hole()) { holeLoop.Invert(); @@ -232,79 +164,60 @@ namespace mongo { polyBuilder.AddLoop(&holeLoop); } - uassert(16695, "Couldn't assemble polygon: " + obj.toString(), + uassert(16695, "Couldn't assemble polygon: " + sourceObject.toString(), polyBuilder.AssemblePolygon(out, NULL)); } - bool GeoParser::parsePoint(const BSONObj &obj, Point *out) { - if (isGeoJSONPoint(obj)) { - parseGeoJSONPoint(obj, out); - return true; - } else if (isLegacyPoint(obj)) { - parseLegacyPoint(obj, out); - return true; - } - return false; + static void parseLegacyPoint(const BSONObj &obj, Point *out) { + BSONObjIterator it(obj); + BSONElement x = it.next(); + BSONElement y = it.next(); + out->x = x.number(); + out->y = y.number(); } - bool GeoParser::parsePoint(const BSONObj &obj, S2Point *out) { - if (isGeoJSONPoint(obj)) { - parseGeoJSONPoint(obj, out); - return true; - } else if (isLegacyPoint(obj)) { - BSONObjIterator it(obj); - BSONElement x = it.next(); - BSONElement y = it.next(); - *out = coordToPoint(x.number(), y.number()); - return true; - } - return false; + // Coordinates looks like [[0,0],[5,0],[5,5],[0,5],[0,0]] + static bool isLoopClosed(const vector<BSONElement>& coordinates) { + double x1, y1, x2, y2; + x1 = coordinates[0].Array()[0].Number(); + y1 = coordinates[0].Array()[1].Number(); + x2 = coordinates[coordinates.size() - 1].Array()[0].Number(); + y2 = coordinates[coordinates.size() - 1].Array()[1].Number(); + return (fabs(x1 - x2) < 1e-6) && fabs(y1 - y2) < 1e-6; } - bool GeoParser::parsePoint(const BSONObj &obj, S2Cell *out) { - S2Point point; - if (parsePoint(obj, &point)) { - *out = S2Cell(point); - return true; + static bool isGeoJSONPolygonCoordinates(const vector<BSONElement>& coordinates) { + // Must be at least one element, the outer shell + if (coordinates.empty()) { return false; } + // Verify that the shell is a bunch'a coordinates. + for (size_t i = 0; i < coordinates.size(); ++i) { + if (Array != coordinates[i].type()) { return false; } + const vector<BSONElement>& thisLoop = coordinates[i].Array(); + // A triangle is the simplest 2d shape, and we repeat a vertex, so, 4. + if (thisLoop.size() < 4) { return false; } + if (!isArrayOfCoordinates(thisLoop)) { return false; } + if (!isLoopClosed(thisLoop)) { return false; } } - return false; - } - - bool GeoParser::parseLineString(const BSONObj &obj, S2Polyline *out) { - if (!isGeoJSONLineString(obj)) { return false; } - parseGeoJSONLineString(obj, out); return true; } - void GeoParser::parseLegacyPoint(const BSONObj &obj, S2Point *out) { - BSONObjIterator it(obj); - BSONElement x = it.next(); - BSONElement y = it.next(); - *out = coordToPoint(x.number(), y.number()); - } + static bool isGeoJSONPolygon(const BSONObj& obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_POLYGON != type.String()) { return false; } - bool GeoParser::parsePolygon(const BSONObj &obj, S2Polygon *out) { - if (isGeoJSONPolygon(obj)) { - parseGeoJSONPolygon(obj, out); - return true; - } else { + if (!GeoParser::crsIsOK(obj)) { + warning() << "Invalid CRS: " << obj.toString() << endl; return false; } - } - bool GeoParser::isLegacyPoint(const BSONObj &obj) { - BSONObjIterator it(obj); - if (!it.more()) { return false; } - BSONElement x = it.next(); - if (!x.isNumber()) { return false; } - if (!it.more()) { return false; } - BSONElement y = it.next(); - if (!y.isNumber()) { return false; } - if (it.more()) { return false; } - return true; + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + + return isGeoJSONPolygonCoordinates(coordElt.Array()); } - bool GeoParser::isLegacyPolygon(const BSONObj &obj) { + static bool isLegacyPolygon(const BSONObj &obj) { BSONObjIterator typeIt(obj); BSONElement type = typeIt.next(); if (!type.isABSONObj()) { return false; } @@ -321,50 +234,89 @@ namespace mongo { return true; } - bool GeoParser::isPoint(const BSONObj &obj) { - return isGeoJSONPoint(obj) || isLegacyPoint(obj); + static bool isLegacyCenter(const BSONObj &obj) { + BSONObjIterator typeIt(obj); + BSONElement type = typeIt.next(); + if (!type.isABSONObj()) { return false; } + bool isCenter = mongoutils::str::equals(type.fieldName(), "$center"); + if (!isCenter) { return false; } + BSONObjIterator objIt(type.embeddedObject()); + BSONElement center = objIt.next(); + if (!center.isABSONObj()) { return false; } + if (!isLegacyPoint(center.Obj())) { return false; } + if (!objIt.more()) { return false; } + BSONElement radius = objIt.next(); + if (!radius.isNumber()) { return false; } + return true; } - bool GeoParser::isLineString(const BSONObj &obj) { - return isGeoJSONLineString(obj); + static bool isLegacyCenterSphere(const BSONObj &obj) { + BSONObjIterator typeIt(obj); + BSONElement type = typeIt.next(); + if (!type.isABSONObj()) { return false; } + bool isCenterSphere = mongoutils::str::equals(type.fieldName(), "$centerSphere"); + if (!isCenterSphere) { return false; } + BSONObjIterator objIt(type.embeddedObject()); + BSONElement center = objIt.next(); + if (!center.isABSONObj()) { return false; } + if (!isLegacyPoint(center.Obj())) { return false; } + if (!objIt.more()) { return false; } + BSONElement radius = objIt.next(); + if (!radius.isNumber()) { return false; } + return true; } - bool GeoParser::isPolygon(const BSONObj &obj) { - return isGeoJSONPolygon(obj) || isLegacyPolygon(obj); + /** exported **/ + + bool GeoParser::isPoint(const BSONObj &obj) { + return isGeoJSONPoint(obj) || isLegacyPoint(obj); } - bool GeoParser::crsIsOK(const BSONObj &obj) { - if (!obj.hasField("crs")) { return true; } + void GeoParser::parsePoint(const BSONObj &obj, PointWithCRS *out) { + if (isGeoJSONPoint(obj)) { + const vector<BSONElement>& 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)) { + BSONObjIterator it(obj); + BSONElement x = it.next(); + BSONElement y = it.next(); + 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; + } + } - if (!obj["crs"].isABSONObj()) { return false; } + bool GeoParser::isLine(const BSONObj& obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_LINESTRING != type.String()) { return false; } - BSONObj crsObj = obj["crs"].embeddedObject(); - if (!crsObj.hasField("type")) { return false; } - if (String != crsObj["type"].type()) { return false; } - if ("name" != crsObj["type"].String()) { return false; } - if (!crsObj.hasField("properties")) { return false; } - if (!crsObj["properties"].isABSONObj()) { return false; } + if (!crsIsOK(obj)) { + warning() << "Invalid CRS: " << obj.toString() << endl; + return false; + } - BSONObj propertiesObj = crsObj["properties"].embeddedObject(); - if (!propertiesObj.hasField("name")) { return false; } - if (String != propertiesObj["name"].type()) { return false; } - const string& name = propertiesObj["name"].String(); + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } - // see http://portal.opengeospatial.org/files/?artifact_id=24045 - // and http://spatialreference.org/ref/epsg/4326/ - // and http://www.geojson.org/geojson-spec.html#named-crs - return ("urn:ogc:def:crs:OGC:1.3:CRS84" == name) || ("EPSG:4326" == name); + return isValidLineString(coordElt.Array()); } - void GeoParser::parseLegacyPoint(const BSONObj &obj, Point *out) { - BSONObjIterator it(obj); - BSONElement x = it.next(); - BSONElement y = it.next(); - out->x = x.number(); - out->y = y.number(); + void GeoParser::parseLine(const BSONObj& obj, LineWithCRS* out) { + vector<S2Point> vertices; + parsePoints(obj.getFieldDotted(GEOJSON_COORDINATES).Array(), &vertices); + eraseDuplicatePoints(&vertices); + out->line.Init(vertices); + out->crs = SPHERE; } - bool GeoParser::isLegacyBox(const BSONObj &obj) { + bool GeoParser::isBox(const BSONObj &obj) { BSONObjIterator typeIt(obj); BSONElement type = typeIt.next(); if (!type.isABSONObj()) { return false; } @@ -380,86 +332,250 @@ namespace mongo { return true; } - void GeoParser::parseLegacyBox(const BSONObj &obj, Box *out) { + void GeoParser::parseBox(const BSONObj &obj, BoxWithCRS *out) { BSONObjIterator typeIt(obj); BSONElement type = typeIt.next(); BSONObjIterator coordIt(type.embeddedObject()); BSONElement minE = coordIt.next(); BSONElement maxE = coordIt.next(); - parseLegacyPoint(minE.Obj(), &out->_min); - parseLegacyPoint(maxE.Obj(), &out->_max); + parseLegacyPoint(minE.Obj(), &out->box._min); + parseLegacyPoint(maxE.Obj(), &out->box._max); + out->crs = FLAT; } - bool GeoParser::isLegacyCenter(const BSONObj &obj) { - BSONObjIterator typeIt(obj); - BSONElement type = typeIt.next(); - if (!type.isABSONObj()) { return false; } - bool isCenter = mongoutils::str::equals(type.fieldName(), "$center"); - if (!isCenter) { return false; } - BSONObjIterator objIt(type.embeddedObject()); - BSONElement center = objIt.next(); - if (!center.isABSONObj()) { return false; } - if (!isLegacyPoint(center.Obj())) { return false; } - if (!objIt.more()) { return false; } - BSONElement radius = objIt.next(); - if (!radius.isNumber()) { return false; } - return true; + void GeoParser::parsePolygon(const BSONObj &obj, PolygonWithCRS *out) { + if (isGeoJSONPolygon(obj)) { + const vector<BSONElement>& coordinates = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); + parseGeoJSONPolygonCoordinates(coordinates, obj, &out->polygon); + out->crs = SPHERE; + } else { + BSONObjIterator typeIt(obj); + BSONElement type = typeIt.next(); + BSONObjIterator coordIt(type.embeddedObject()); + vector<Point> points; + while (coordIt.more()) { + Point p; + parseLegacyPoint(coordIt.next().Obj(), &p); + points.push_back(p); + } + out->oldPolygon = Polygon(points); + out->crs = FLAT; + } } - void GeoParser::parseLegacyCenter(const BSONObj &obj, Circle *out) { - BSONObjIterator typeIt(obj); - BSONElement type = typeIt.next(); - BSONObjIterator objIt(type.embeddedObject()); - BSONElement center = objIt.next(); - parseLegacyPoint(center.Obj(), &out->center); - BSONElement radius = objIt.next(); - out->radius = radius.number(); + bool GeoParser::isMultiPoint(const BSONObj &obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_MULTI_POINT != type.String()) { return false; } + + if (!crsIsOK(obj)) { + warning() << "Invalid CRS: " << obj.toString() << endl; + return false; + } + + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + + const vector<BSONElement>& coordinates = coordElt.Array(); + if (0 == coordinates.size()) { return false; } + return isArrayOfCoordinates(coordinates); } - bool GeoParser::isLegacyCenterSphere(const BSONObj &obj) { - BSONObjIterator typeIt(obj); - BSONElement type = typeIt.next(); - if (!type.isABSONObj()) { return false; } - bool isCenterSphere = mongoutils::str::equals(type.fieldName(), "$centerSphere"); - if (!isCenterSphere) { return false; } - BSONObjIterator objIt(type.embeddedObject()); - BSONElement center = objIt.next(); - if (!center.isABSONObj()) { return false; } - if (!isLegacyPoint(center.Obj())) { return false; } - if (!objIt.more()) { return false; } - BSONElement radius = objIt.next(); - if (!radius.isNumber()) { return false; } + void GeoParser::parseMultiPoint(const BSONObj &obj, MultiPointWithCRS *out) { + out->points.clear(); + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + const vector<BSONElement>& coordinates = coordElt.Array(); + out->points.resize(coordinates.size()); + out->cells.resize(coordinates.size()); + for (size_t i = 0; i < coordinates.size(); ++i) { + const vector<BSONElement>& thisCoord = coordinates[i].Array(); + out->points[i] = coordToPoint(thisCoord[0].Number(), thisCoord[1].Number()); + out->cells[i] = S2Cell(out->points[i]); + } + } + + bool GeoParser::isMultiLine(const BSONObj &obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_MULTI_LINESTRING != type.String()) { return false; } + + if (!crsIsOK(obj)) { + warning() << "Invalid CRS: " << obj.toString() << endl; + return false; + } + + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + + const vector<BSONElement>& coordinates = coordElt.Array(); + if (0 == coordinates.size()) { return false; } + + for (size_t i = 0; i < coordinates.size(); ++i) { + if (coordinates[i].eoo() || (Array != coordinates[i].type())) { return false; } + if (!isValidLineString(coordinates[i].Array())) { return false; } + } + return true; } - void GeoParser::parseLegacyCenterSphere(const BSONObj &obj, S2Cap *out) { - BSONObjIterator typeIt(obj); - BSONElement type = typeIt.next(); - BSONObjIterator objIt(type.embeddedObject()); - BSONElement center = objIt.next(); - S2Point centerPoint; - parseLegacyPoint(center.Obj(), ¢erPoint); - BSONElement radiusElt = objIt.next(); - double radius = radiusElt.number(); - *out = S2Cap::FromAxisAngle(centerPoint, S1Angle::Radians(radius)); + void GeoParser::parseMultiLine(const BSONObj &obj, MultiLineWithCRS *out) { + vector<BSONElement> coordElt = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); + out->lines.mutableVector().clear(); + out->lines.mutableVector().resize(coordElt.size()); + + for (size_t i = 0; i < coordElt.size(); ++i) { + vector<S2Point> vertices; + parsePoints(coordElt[i].Array(), &vertices); + out->lines.mutableVector()[i] = new S2Polyline(); + out->lines.mutableVector()[i]->Init(vertices); + } } - void GeoParser::parseLegacyPolygon(const BSONObj &obj, Polygon *out) { - BSONObjIterator typeIt(obj); - BSONElement type = typeIt.next(); - BSONObjIterator coordIt(type.embeddedObject()); - vector<Point> points; - while (coordIt.more()) { - Point p; - parseLegacyPoint(coordIt.next().Obj(), &p); - points.push_back(p); + bool GeoParser::isMultiPolygon(const BSONObj &obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_MULTI_POLYGON != type.String()) { return false; } + + if (!crsIsOK(obj)) { + warning() << "Invalid CRS: " << obj.toString() << endl; + return false; + } + + BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + + const vector<BSONElement>& coordinates = coordElt.Array(); + if (0 == coordinates.size()) { return false; } + for (size_t i = 0; i < coordinates.size(); ++i) { + if (coordinates[i].eoo() || (Array != coordinates[i].type())) { return false; } + if (!isGeoJSONPolygonCoordinates(coordinates[i].Array())) { return false; } + } + + return true; + } + + void GeoParser::parseMultiPolygon(const BSONObj &obj, MultiPolygonWithCRS *out) { + vector<BSONElement> coordElt = obj.getFieldDotted(GEOJSON_COORDINATES).Array(); + out->polygons.mutableVector().clear(); + out->polygons.mutableVector().resize(coordElt.size()); + + for (size_t i = 0; i < coordElt.size(); ++i) { + out->polygons.mutableVector()[i] = new S2Polygon(); + parseGeoJSONPolygonCoordinates(coordElt[i].Array(), obj, out->polygons.vector()[i]); } - *out = Polygon(points); } - bool GeoParser::parsePolygon(const BSONObj &obj, Polygon *out) { - if (!isLegacyPolygon(obj)) { return false; } - parseLegacyPolygon(obj, out); + bool GeoParser::isGeometryCollection(const BSONObj &obj) { + BSONElement type = obj.getFieldDotted(GEOJSON_TYPE); + if (type.eoo() || (String != type.type())) { return false; } + if (GEOJSON_TYPE_GEOMETRY_COLLECTION != type.String()) { return false; } + + BSONElement coordElt = obj.getFieldDotted(GEOJSON_GEOMETRIES); + if (coordElt.eoo() || (Array != coordElt.type())) { return false; } + + const vector<BSONElement>& coordinates = coordElt.Array(); + if (0 == coordinates.size()) { return false; } + + for (size_t i = 0; i < coordinates.size(); ++i) { + if (coordinates[i].eoo() || (Object != coordinates[i].type())) { return false; } + BSONObj obj = coordinates[i].Obj(); + if (!isGeoJSONPoint(obj) && !isLine(obj) && !isGeoJSONPolygon(obj) + && !isMultiPoint(obj) && !isMultiPolygon(obj) && !isMultiLine(obj)) { + return false; + } + } + return true; } + + bool GeoParser::isPolygon(const BSONObj &obj) { + return isGeoJSONPolygon(obj) || isLegacyPolygon(obj); + } + + bool GeoParser::crsIsOK(const BSONObj &obj) { + if (!obj.hasField("crs")) { return true; } + + if (!obj["crs"].isABSONObj()) { return false; } + + BSONObj crsObj = obj["crs"].embeddedObject(); + if (!crsObj.hasField("type")) { return false; } + if (String != crsObj["type"].type()) { return false; } + if ("name" != crsObj["type"].String()) { return false; } + if (!crsObj.hasField("properties")) { return false; } + if (!crsObj["properties"].isABSONObj()) { return false; } + + BSONObj propertiesObj = crsObj["properties"].embeddedObject(); + if (!propertiesObj.hasField("name")) { return false; } + if (String != propertiesObj["name"].type()) { return false; } + const string& name = propertiesObj["name"].String(); + + // see http://portal.opengeospatial.org/files/?artifact_id=24045 + // and http://spatialreference.org/ref/epsg/4326/ + // and http://www.geojson.org/geojson-spec.html#named-crs + return ("urn:ogc:def:crs:OGC:1.3:CRS84" == name) || ("EPSG:4326" == name); + } + + bool GeoParser::isCap(const BSONObj &obj) { + return isLegacyCenter(obj) || isLegacyCenterSphere(obj); + } + + void GeoParser::parseCap(const BSONObj& obj, CapWithCRS *out) { + if (isLegacyCenter(obj)) { + BSONObjIterator typeIt(obj); + BSONElement type = typeIt.next(); + BSONObjIterator objIt(type.embeddedObject()); + BSONElement center = objIt.next(); + parseLegacyPoint(center.Obj(), &out->circle.center); + BSONElement radius = objIt.next(); + out->circle.radius = radius.number(); + out->crs = FLAT; + } else { + BSONObjIterator typeIt(obj); + BSONElement type = typeIt.next(); + BSONObjIterator objIt(type.embeddedObject()); + BSONObj centerObj = objIt.next().Obj(); + + S2Point centerPoint; + BSONObjIterator it(centerObj); + BSONElement x = it.next(); + BSONElement y = it.next(); + centerPoint = S2LatLng::FromDegrees(y.Number(), x.Number()).Normalized().ToPoint(); + BSONElement radiusElt = objIt.next(); + double radius = radiusElt.number(); + out->cap = S2Cap::FromAxisAngle(centerPoint, S1Angle::Radians(radius)); + out->crs = SPHERE; + } + } + + void GeoParser::parseGeometryCollection(const BSONObj &obj, GeometryCollection *out) { + BSONElement coordElt = obj.getFieldDotted(GEOJSON_GEOMETRIES); + const vector<BSONElement>& geometries = coordElt.Array(); + + for (size_t i = 0; i < geometries.size(); ++i) { + const BSONObj& geoObj = geometries[i].Obj(); + + if (isGeoJSONPoint(geoObj)) { + PointWithCRS point; + parsePoint(geoObj, &point); + out->points.push_back(point); + } else if (isLine(geoObj)) { + out->lines.mutableVector().push_back(new LineWithCRS()); + parseLine(geoObj, out->lines.vector().back()); + } else if (isGeoJSONPolygon(geoObj)) { + out->polygons.mutableVector().push_back(new PolygonWithCRS()); + parsePolygon(geoObj, out->polygons.vector().back()); + } else if (isMultiPoint(geoObj)) { + out->multiPoints.mutableVector().push_back(new MultiPointWithCRS()); + parseMultiPoint(geoObj, out->multiPoints.mutableVector().back()); + } else if (isMultiPolygon(geoObj)) { + out->multiPolygons.mutableVector().push_back(new MultiPolygonWithCRS()); + parseMultiPolygon(geoObj, out->multiPolygons.mutableVector().back()); + } else { + verify(isMultiLine(geoObj)); + out->multiLines.mutableVector().push_back(new MultiLineWithCRS()); + parseMultiLine(geoObj, out->multiLines.mutableVector().back()); + } + } + } + } // namespace mongo diff --git a/src/mongo/db/geo/geoparser.h b/src/mongo/db/geo/geoparser.h index 72d998267ff..6529636a76d 100644 --- a/src/mongo/db/geo/geoparser.h +++ b/src/mongo/db/geo/geoparser.h @@ -1,5 +1,5 @@ /** -* Copyright (C) 2008-2012 10gen Inc. +* 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, @@ -16,69 +16,47 @@ #pragma once -#include "mongo/db/jsobj.h" -#include <vector> -#include "third_party/s2/s2.h" #include "mongo/db/geo/shapes.h" - -class S2Cap; -class S2Cell; -class S2Polyline; -class S2Polygon; +#include "mongo/db/jsobj.h" namespace mongo { + // This class parses geographic data. // It parses a subset of GeoJSON and creates S2 shapes from it. // See http://geojson.org/geojson-spec.html for the spec. // // This class also parses the ad-hoc geo formats that MongoDB introduced. // - // The parseFoo methods that return a bool internally call isFoo and return true - // if the foo is parsed correctly. - // The parseFoo methods that do not return a bool assume isFoo is true. - // // We assume that if you're trying to parse something, you know it's valid. class GeoParser { public: - // Try to parse GeoJSON, then try legacy format, return true if either succeed. - // These call the various isPoint and parsePoint methods below. - // You can just use these bool parsePoint(...) methods. - static bool parsePoint(const BSONObj &obj, S2Point *out); - static bool parsePoint(const BSONObj &obj, S2Cell *out); - static bool parsePoint(const BSONObj &obj, Point *out); - // Check to see if it's GeoJSON or if it's legacy geo. static bool isPoint(const BSONObj &obj); + static void parsePoint(const BSONObj &obj, PointWithCRS *out); - static bool isGeoJSONPoint(const BSONObj &obj); - static void parseGeoJSONPoint(const BSONObj &obj, S2Point *out); - static void parseGeoJSONPoint(const BSONObj &obj, S2Cell *out); - static void parseGeoJSONPoint(const BSONObj &obj, Point *out); + static bool isLine(const BSONObj &obj); + static void parseLine(const BSONObj &obj, LineWithCRS *out); - static bool isLegacyPoint(const BSONObj &obj); - static void parseLegacyPoint(const BSONObj &obj, S2Point *out); - static void parseLegacyPoint(const BSONObj &obj, Point *out); + static bool isBox(const BSONObj &obj); + static void parseBox(const BSONObj &obj, BoxWithCRS *out); - static bool parseLineString(const BSONObj &obj, S2Polyline *out); - static bool isLineString(const BSONObj &obj); - static bool isGeoJSONLineString(const BSONObj &obj); - static void parseGeoJSONLineString(const BSONObj &obj, S2Polyline *out); - - static bool parsePolygon(const BSONObj &obj, S2Polygon *out); - static bool parsePolygon(const BSONObj &obj, Polygon *out); static bool isPolygon(const BSONObj &obj); - static bool isGeoJSONPolygon(const BSONObj &obj); - static bool isLegacyPolygon(const BSONObj &obj); - static void parseGeoJSONPolygon(const BSONObj &obj, S2Polygon *out); - static void parseLegacyPolygon(const BSONObj &obj, Polygon *out); + static void parsePolygon(const BSONObj &obj, PolygonWithCRS *out); + + // AKA $center or $centerSphere + static bool isCap(const BSONObj &obj); + static void parseCap(const BSONObj &obj, CapWithCRS *out); - static bool isLegacyBox(const BSONObj &obj); - static void parseLegacyBox(const BSONObj &obj, Box *out); + static bool isMultiPoint(const BSONObj &obj); + static void parseMultiPoint(const BSONObj &obj, MultiPointWithCRS *out); - static bool isLegacyCenter(const BSONObj &obj); - static void parseLegacyCenter(const BSONObj &obj, Circle *out); + static bool isMultiLine(const BSONObj &obj); + static void parseMultiLine(const BSONObj &obj, MultiLineWithCRS *out); - static bool isLegacyCenterSphere(const BSONObj &obj); - static void parseLegacyCenterSphere(const BSONObj &obj, S2Cap *out); + static bool isMultiPolygon(const BSONObj &obj); + static void parseMultiPolygon(const BSONObj &obj, MultiPolygonWithCRS *out); + + static bool isGeometryCollection(const BSONObj &obj); + static void parseGeometryCollection(const BSONObj &obj, GeometryCollection *out); // Return true if the CRS field is 1. missing, or 2. is well-formed and // has a datum we accept. Otherwise, return false. @@ -87,4 +65,5 @@ namespace mongo { // needed. static bool crsIsOK(const BSONObj& obj); }; + } // namespace mongo diff --git a/src/mongo/db/geo/geoparser_test.cpp b/src/mongo/db/geo/geoparser_test.cpp index cb3af1a119e..bac9bb57cb9 100644 --- a/src/mongo/db/geo/geoparser_test.cpp +++ b/src/mongo/db/geo/geoparser_test.cpp @@ -22,20 +22,13 @@ #include <sstream> #include "mongo/db/geo/geoparser.h" +#include "mongo/db/geo/shapes.h" #include "mongo/db/json.h" #include "mongo/db/jsobj.h" #include "mongo/unittest/unittest.h" #include "mongo/util/assert_util.h" -#include "mongo/db/geo/shapes.h" -#include "third_party/s2/s2.h" -#include "third_party/s2/s2polygon.h" -#include "third_party/s2/s2polyline.h" - -using mongo::BSONObj; -using mongo::fromjson; -using mongo::GeoParser; -using mongo::Polygon; +using namespace mongo; namespace { @@ -63,27 +56,27 @@ namespace { } TEST(GeoParser, isValidLineString) { - ASSERT_TRUE(GeoParser::isLineString( + ASSERT_TRUE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4]]}"))); - ASSERT_TRUE(GeoParser::isLineString( + ASSERT_TRUE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[0,-90], [0,90]]}"))); - ASSERT_TRUE(GeoParser::isLineString( + ASSERT_TRUE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[180,-90], [-180,90]]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[180.1,-90], [-180.1,90]]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[0,-91], [0,90]]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[0,-90], [0,91]]}"))); - ASSERT_TRUE(GeoParser::isLineString( + ASSERT_TRUE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4], [5,6]]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[1,2]]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[['chicken','little']]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[1,2, 3, 4]}"))); - ASSERT_FALSE(GeoParser::isLineString( + ASSERT_FALSE(GeoParser::isLine( fromjson("{'type':'LineString', 'coordinates':[[1,2, 3], [3,4, 5], [5,6]]}"))); } @@ -111,71 +104,69 @@ namespace { } TEST(GeoParser, parsePoint) { - S2Point point; - ASSERT_TRUE(GeoParser::parsePoint(fromjson("{'type':'Point', 'coordinates': [40, 5]}"), - &point)); - ASSERT_TRUE(GeoParser::parsePoint(fromjson("{'type':'Point', 'coordinates': [-4.3, -5.0]}"), - &point)); + PointWithCRS point; + GeoParser::parsePoint(fromjson("{'type':'Point', 'coordinates': [40, 5]}"), &point); + GeoParser::parsePoint(fromjson("{'type':'Point', 'coordinates': [-4.3, -5.0]}"), &point); } - TEST(GeoParser, parseLineString) { - S2Polyline polyline; - GeoParser::parseLineString( + TEST(GeoParser, parseLine) { + LineWithCRS polyline; + GeoParser::parseLine( fromjson("{'type':'LineString', 'coordinates':[[1,2],[3,4]]}"), &polyline); - GeoParser::parseLineString( + GeoParser::parseLine( fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4], [5,6]]}"), &polyline); - GeoParser::parseLineString( + GeoParser::parseLine( fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4], [5,6]]}"), &polyline); } TEST(GeoParser, parsePolygon) { - S2Point point; + PointWithCRS point; GeoParser::parsePoint(fromjson("{'type':'Point', 'coordinates': [2, 2]}"), &point); - S2Polygon polygonA; + PolygonWithCRS polygonA; GeoParser::parsePolygon( fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[5,0],[5,5],[0,5],[0,0]] ]}"), &polygonA); - ASSERT_TRUE(polygonA.Contains(point)); + ASSERT_TRUE(polygonA.polygon.Contains(point.point)); - S2Polygon polygonB; + PolygonWithCRS polygonB; GeoParser::parsePolygon( fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[5,0],[5,5],[0,5],[0,0]]," " [[1,1],[1,4],[4,4],[4,1],[1,1]] ]}"), &polygonB); // We removed this in the hole. - ASSERT_FALSE(polygonB.Contains(point)); + ASSERT_FALSE(polygonB.polygon.Contains(point.point)); // Now we reverse the orientations and verify that the code fixes it up // (outer loop must be CCW, inner CW). - S2Polygon polygonC; + PolygonWithCRS polygonC; GeoParser::parsePolygon( fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[0,5],[5,5],[5,0],[0,0]] ]}"), &polygonC); - ASSERT_TRUE(polygonC.Contains(point)); + ASSERT_TRUE(polygonC.polygon.Contains(point.point)); - S2Polygon polygonD; + PolygonWithCRS polygonD; GeoParser::parsePolygon( fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[0,5],[5,5],[5,0],[0,0]]," " [[1,1],[1,4],[4,4],[4,1],[1,1]] ]}"), &polygonD); // Also removed in the loop. - ASSERT_FALSE(polygonD.Contains(point)); + ASSERT_FALSE(polygonD.polygon.Contains(point.point)); } - TEST(GeoParser, parseLegacyPoint) { - S2Point point; - ASSERT(GeoParser::parsePoint(BSON_ARRAY(0 << 1), &point)); - ASSERT_FALSE(GeoParser::parsePoint(BSON_ARRAY(0), &point)); - ASSERT_FALSE(GeoParser::parsePoint(BSON_ARRAY(0 << 1 << 2), &point)); - ASSERT(GeoParser::parsePoint(fromjson("{x: 50, y:40}"), &point)); - ASSERT_FALSE(GeoParser::parsePoint(fromjson("{x: '50', y:40}"), &point)); - ASSERT_FALSE(GeoParser::parsePoint(fromjson("{x: 5, y:40, z:50}"), &point)); - ASSERT_FALSE(GeoParser::parsePoint(fromjson("{x: 5}"), &point)); + TEST(GeoParser, legacyPoint) { + PointWithCRS point; + ASSERT(GeoParser::isPoint(BSON_ARRAY(0 << 1))); + ASSERT_FALSE(GeoParser::isPoint(BSON_ARRAY(0))); + ASSERT_FALSE(GeoParser::isPoint(BSON_ARRAY(0 << 1 << 2))); + ASSERT(GeoParser::isPoint(fromjson("{x: 50, y:40}"))); + ASSERT_FALSE(GeoParser::isPoint(fromjson("{x: '50', y:40}"))); + ASSERT_FALSE(GeoParser::isPoint(fromjson("{x: 5, y:40, z:50}"))); + ASSERT_FALSE(GeoParser::isPoint(fromjson("{x: 5}"))); } TEST(GeoParser, verifyCRS) { @@ -186,43 +177,204 @@ namespace { BSONObj point1 = fromjson("{'type':'Point', 'coordinates': [40, 5], " + goodCRS1 + "}"); BSONObj point2 = fromjson("{'type':'Point', 'coordinates': [40, 5], " + goodCRS2 + "}"); - ASSERT(GeoParser::isGeoJSONPoint(point1)); + ASSERT(GeoParser::isPoint(point1)); ASSERT(GeoParser::crsIsOK(point1)); - ASSERT(GeoParser::isGeoJSONPoint(point2)); + ASSERT(GeoParser::isPoint(point2)); ASSERT(GeoParser::crsIsOK(point2)); BSONObj point3 = fromjson("{'type':'Point', 'coordinates': [40, 5], " + badCRS1 + "}"); BSONObj point4 = fromjson("{'type':'Point', 'coordinates': [40, 5], " + badCRS2 + "}"); - ASSERT_FALSE(GeoParser::isGeoJSONPoint(point3)); + ASSERT_FALSE(GeoParser::isPoint(point3)); ASSERT_FALSE(GeoParser::crsIsOK(point3)); - ASSERT_FALSE(GeoParser::isGeoJSONPoint(point4)); + ASSERT_FALSE(GeoParser::isPoint(point4)); ASSERT_FALSE(GeoParser::crsIsOK(point4)); BSONObj polygon1 = fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[5,0],[5,5],[0,5],[0,0]]," " [[1,1],[1,4],[4,4],[4,1],[1,1]] ]," + goodCRS1 + "}"); - ASSERT(GeoParser::isGeoJSONPolygon(polygon1)); + ASSERT(GeoParser::isPolygon(polygon1)); ASSERT(GeoParser::crsIsOK(polygon1)); BSONObj polygon2 = fromjson("{'type':'Polygon', 'coordinates':[ [[0,0],[5,0],[5,5],[0,5],[0,0]]," " [[1,1],[1,4],[4,4],[4,1],[1,1]] ]," + badCRS2 + "}"); - ASSERT_FALSE(GeoParser::isGeoJSONPolygon(polygon2)); + ASSERT_FALSE(GeoParser::isPolygon(polygon2)); ASSERT_FALSE(GeoParser::crsIsOK(polygon2)); BSONObj line1 = fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4], [5,6]]," + goodCRS2 + "}"); - ASSERT(GeoParser::isGeoJSONLineString(line1)); + ASSERT(GeoParser::isLine(line1)); ASSERT(GeoParser::crsIsOK(line1)); BSONObj line2 = fromjson("{'type':'LineString', 'coordinates':[[1,2], [3,4], [5,6]]," + badCRS1 + "}"); - ASSERT_FALSE(GeoParser::isGeoJSONLineString(line2)); + ASSERT_FALSE(GeoParser::isLine(line2)); ASSERT_FALSE(GeoParser::crsIsOK(line2)); } - TEST(GeoParser, parseLegacyPolygon) { - mongo::Polygon polygon; - ASSERT(GeoParser::parsePolygon(fromjson("{$polygon: [[10,20],[10,40],[30,40],[30,20]]}"), - &polygon)); - ASSERT(GeoParser::parsePolygon(fromjson("{$polygon: [[10,20], [10,40], [30,40]]}"), &polygon)); - ASSERT_FALSE(GeoParser::parsePolygon(fromjson("{$polygon: [[10,20],[10,40]]}"), &polygon)); - ASSERT_FALSE(GeoParser::parsePolygon(fromjson("{$polygon: [['10', 20],[10,40],[30,40],[30,20]]}"), &polygon)); - ASSERT_FALSE(GeoParser::parsePolygon(fromjson("{$polygon: [[10,20,30],[10,40],[30,40],[30,20]]}"), &polygon)); - ASSERT(GeoParser::parsePolygon( - fromjson("{$polygon: {a:{x:40,y:5},b:{x:40,y:6},c:{x:41,y:6},d:{x:41,y:5}}}"), &polygon)); + TEST(GeoParser, legacyPolygon) { + PolygonWithCRS polygon; + GeoParser::parsePolygon(fromjson("{$polygon: [[10,20],[10,40],[30,40],[30,20]]}"), + &polygon); + ASSERT(polygon.crs == FLAT); + + GeoParser::parsePolygon(fromjson("{$polygon: [[10,20], [10,40], [30,40]]}"), &polygon); + ASSERT(polygon.crs == FLAT); + + ASSERT_FALSE(GeoParser::isPolygon(fromjson("{$polygon: [[10,20],[10,40]]}"))); + ASSERT_FALSE(GeoParser::isPolygon(fromjson("{$polygon: [['10',20],[10,40],[30,40],[30,20]]}"))); + ASSERT_FALSE(GeoParser::isPolygon(fromjson("{$polygon: [[10,20,30],[10,40],[30,40],[30,20]]}"))); + ASSERT(GeoParser::isPolygon(fromjson("{$polygon: {a:{x:40,y:5},b:{x:40,y:6},c:{x:41,y:6},d:{x:41,y:5}}}"))); + } + + TEST(GeoParser, multiPoint) { + ASSERT(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[1,2],[3,4]]}"))); + ASSERT(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[3,4]]}"))); + ASSERT(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[1,2],[3,4],[5,6],[7,8]]}"))); + + ASSERT_FALSE(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[]}"))); + ASSERT_FALSE(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[181,2],[3,4]]}"))); + ASSERT_FALSE(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[1,-91],[3,4]]}"))); + ASSERT_FALSE(GeoParser::isMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[181,2],[3,'chicken']]}"))); + } + + TEST(GeoParser, parseMultiPoint) { + mongo::MultiPointWithCRS mp; + GeoParser::parseMultiPoint(fromjson("{'type':'MultiPoint','coordinates':[[1,2],[3,4]]}"), + &mp); + GeoParser::parseMultiPoint(fromjson("{'type':'MultiPoint','coordinates':[[3,4]]}"), + &mp); + GeoParser::parseMultiPoint( + fromjson("{'type':'MultiPoint','coordinates':[[1,2],[3,4],[5,6],[7,8]]}"), &mp); + } + + TEST(GeoParser, multiLineString) { + ASSERT(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1],[2,2],[3,3]]," + "[[4,5],[6,7]]]}"))); + ASSERT(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1],[2,2]]," + "[[4,5],[6,7]]]}"))); + ASSERT(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1],[2,2]]]}"))); + + ASSERT(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1],[2,2]]," + "[[2,2],[1,1]]]}"))); + ASSERT_FALSE(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1]]]}"))); + ASSERT_FALSE(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[1,1]],[[1,2],[3,4]]]}"))); + ASSERT_FALSE(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[181,1],[2,2]]]}"))); + ASSERT_FALSE(GeoParser::isMultiLine( + fromjson("{'type':'MultiLineString','coordinates':[ [[181,1],[2,-91]]]}"))); + } + + TEST(GeoParser, parseMultiLine) { + mongo::MultiLineWithCRS mls; + + GeoParser::parseMultiLine( + fromjson("{'type':'MultiLine','coordinates':[ [[1,1],[2,2],[3,3]]," + "[[4,5],[6,7]]]}"), + &mls); + + GeoParser::parseMultiLine( + fromjson("{'type':'MultiLine','coordinates':[ [[1,1],[2,2]]," + "[[4,5],[6,7]]]}"), + &mls); + + GeoParser::parseMultiLine( + fromjson("{'type':'MultiLine','coordinates':[ [[1,1],[2,2]]]}"), + &mls); + + GeoParser::parseMultiLine( + fromjson("{'type':'MultiLine','coordinates':[ [[1,1],[2,2]]," + "[[2,2],[1,1]]]}"), + &mls); + } + + TEST(GeoParser, multiPolygon) { + ASSERT(GeoParser::isMultiPolygon( + fromjson("{'type':'MultiPolygon','coordinates':[" + "[[[102.0, 2.0], [103.0, 2.0], [103.0, 3.0], [102.0, 3.0], [102.0, 2.0]]]," + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}"))); + ASSERT(GeoParser::isMultiPolygon( + fromjson("{'type':'MultiPolygon','coordinates':[" + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}"))); + } + + TEST(GeoParser, parseMultiPolygon) { + mongo::MultiPolygonWithCRS mp; + GeoParser::parseMultiPolygon( + fromjson("{'type':'MultiPolygon','coordinates':[" + "[[[102.0, 2.0], [103.0, 2.0], [103.0, 3.0], [102.0, 3.0], [102.0, 2.0]]]," + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}"), &mp); + } + + TEST(GeoParser, parseGeometryCollection) { + { + mongo::GeometryCollection gc; + BSONObj obj = fromjson( + "{ 'type': 'GeometryCollection', 'geometries': [" + "{ 'type': 'Point','coordinates': [100.0,0.0]}," + "{ 'type': 'LineString', 'coordinates': [ [101.0, 0.0], [102.0, 1.0] ]}" + "]}"); + ASSERT(GeoParser::isGeometryCollection(obj)); + GeoParser::parseGeometryCollection(obj, &gc); + ASSERT_FALSE(gc.supportsContains()); + } + + { + BSONObj obj = fromjson( + "{ 'type': 'GeometryCollection', 'geometries': [" + "{'type':'MultiPolygon','coordinates':[" + "[[[102.0, 2.0], [103.0, 2.0], [103.0, 3.0], [102.0, 3.0], [102.0, 2.0]]]," + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}" + "]}"); + + ASSERT(GeoParser::isGeometryCollection(obj)); + mongo::GeometryCollection gc; + GeoParser::parseGeometryCollection(obj, &gc); + ASSERT_TRUE(gc.supportsContains()); + } + { + BSONObj obj = fromjson( + "{ 'type': 'GeometryCollection', 'geometries': [" + "{'type':'Polygon', 'coordinates':[ [[0,0],[0,91],[5,5],[5,0],[0,0]] ]}," + "{'type':'MultiPolygon','coordinates':[" + "[[[102.0, 2.0], [103.0, 2.0], [103.0, 3.0], [102.0, 3.0], [102.0, 2.0]]]," + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}" + "]}"); + + ASSERT_FALSE(GeoParser::isGeometryCollection(obj)); + } + + { + BSONObj obj = fromjson( + "{ 'type': 'GeometryCollection', 'geometries': [" + "{'type':'Polygon', 'coordinates':[ [[0,0],[0,5],[5,5],[5,0],[0,0]] ]}," + "{'type':'MultiPolygon','coordinates':[" + "[[[102.0, 2.0], [103.0, 2.0], [103.0, 3.0], [102.0, 3.0], [102.0, 2.0]]]," + "[[[100.0, 0.0], [101.0, 0.0], [101.0, 1.0], [100.0, 1.0], [100.0, 0.0]]," + "[[100.2, 0.2], [100.8, 0.2], [100.8, 0.8], [100.2, 0.8], [100.2, 0.2]]]" + "]}" + "]}"); + + ASSERT(GeoParser::isGeometryCollection(obj)); + mongo::GeometryCollection gc; + GeoParser::parseGeometryCollection(obj, &gc); + ASSERT_TRUE(gc.supportsContains()); + } } } diff --git a/src/mongo/db/geo/geoquery.cpp b/src/mongo/db/geo/geoquery.cpp index 34bd3e64dbc..46ef5da8642 100644 --- a/src/mongo/db/geo/geoquery.cpp +++ b/src/mongo/db/geo/geoquery.cpp @@ -21,9 +21,12 @@ namespace mongo { bool NearQuery::parseFromGeoNear(const BSONObj &obj, double radius) { if (obj["near"].eoo()) { return false; } BSONObj nearObj = obj["near"].embeddedObject(); + + if (!GeoParser::isPoint(nearObj)) { return false; } + GeoParser::parsePoint(nearObj, ¢roid); + // The CRS for the legacy points dictates that distances are in radians. - fromRadians = GeoParser::isLegacyPoint(nearObj); - if (!GeoParser::parsePoint(nearObj, ¢roid)) { return false; } + fromRadians = (FLAT == centroid.crs); if (!obj["maxDistance"].eoo()) { if (obj["maxDistance"].isNumber()) { @@ -57,12 +60,15 @@ namespace mongo { if (isNearSphere || isNear) { if (!e.isABSONObj()) { return false; } BSONObj embeddedObj = e.embeddedObject(); - if (isNearSphere && GeoParser::isPoint(embeddedObj)) { - fromRadians = GeoParser::isLegacyPoint(embeddedObj); - GeoParser::parsePoint(embeddedObj, ¢roid); + + if (!GeoParser::isPoint(embeddedObj)) { continue; } + GeoParser::parsePoint(embeddedObj, ¢roid); + + if (isNearSphere) { + fromRadians = (centroid.crs == FLAT); hasGeometry = true; - } else if (isNear && GeoParser::isGeoJSONPoint(embeddedObj)) { - GeoParser::parseGeoJSONPoint(embeddedObj, ¢roid); + } else if (isNear && (centroid.crs == SPHERE)) { + // We don't accept $near : [oldstylepoint]. hasGeometry = true; } } else if (isMaxDistance) { @@ -90,9 +96,11 @@ namespace mongo { if (mongoutils::str::equals(e.fieldName(), "$geometry")) { if (e.isABSONObj()) { BSONObj embeddedObj = e.embeddedObject(); + uassert(16885, "$near requires a point, given " + embeddedObj.toString(), + GeoParser::isPoint(embeddedObj)); + GeoParser::parsePoint(embeddedObj, ¢roid); uassert(16681, "$near requires geojson point, given " + embeddedObj.toString(), - GeoParser::isGeoJSONPoint(embeddedObj)); - GeoParser::parseGeoJSONPoint(embeddedObj, ¢roid); + (SPHERE == centroid.crs)); hasGeometry = true; } } else if (mongoutils::str::equals(e.fieldName(), "$maxDistance")) { @@ -188,6 +196,30 @@ namespace mongo { return geoContainer.getRegion(); } + bool GeoQuery::hasS2Region() const { + return geoContainer.hasS2Region(); + } + + 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 + || NULL != _line + || (NULL != _polygon && _polygon->crs == SPHERE) + || (NULL != _cap && _cap->crs == SPHERE) + || NULL != _multiPoint + || NULL != _multiLine + || NULL != _multiPolygon + || NULL != _geometryCollection; + } + bool GeoQuery::satisfiesPredicate(const GeometryContainer &otherContainer) const { verify(predicate == WITHIN || predicate == INTERSECT); @@ -199,160 +231,620 @@ namespace mongo { } bool GeometryContainer::contains(const GeometryContainer& otherContainer) const { - if (NULL != _oldPolygon) { - if (NULL == otherContainer._oldPoint) { return false; } - return _oldPolygon->contains(*otherContainer._oldPoint); - } - if (NULL != _oldBox) { - if (NULL == otherContainer._oldPoint) { return false; } - return _oldBox->inside(*otherContainer._oldPoint); + // 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 != _cap) { - if (NULL == otherContainer._cell) { return false; } - return _cap->MayIntersect(*otherContainer._cell); + + if (NULL != _box) { + verify(FLAT == _box->crs); + if (NULL == otherContainer._point) { return false; } + return _box->box.inside(otherContainer._point->oldPoint); } - if (NULL != _oldCircle) { - if (NULL == otherContainer._oldPoint) { return false; } + + 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(_oldCircle->center, *otherContainer._oldPoint, - _oldCircle->radius); + return distanceWithin(_cap->circle.center, otherContainer._point->oldPoint, + _cap->circle.radius); } - if (NULL != _polygon) { - if (NULL != otherContainer._cell) { - // This is much faster for actual containment checking. - if (_polygon->Contains(*otherContainer._point)) { - return true; + + // 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; } - // This is slower but contains edges/vertices. - return _polygon->MayIntersect(*otherContainer._cell); - } else if (NULL != otherContainer._line) { - // 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. - vector<S2Polyline*> clipped; - _polygon->IntersectWithPolyline(otherContainer._line.get(), &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(*otherContainer._line, - S1Angle::Degrees(1e-10)); - for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i]; - return ret; - } else if (NULL != otherContainer._polygon) { - return _polygon->Contains(otherContainer._polygon.get()); - } else { return false; } - } - // Containment only works for polygons/boxes/circles. + } + return true; + } + + if (NULL != otherContainer._multiLine) { + const vector<S2Polyline*>& lines = otherContainer._multiLine->lines.vector(); + for (size_t i = 0; i < lines.size(); ++i) { + if (!contains(*lines[i])) { return false; } + } + return true; + } + + if (NULL != otherContainer._multiPolygon) { + const vector<S2Polygon*>& polys = otherContainer._multiPolygon->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (!contains(*polys[i])) { return false; } + } + return true; + } + + if (NULL != otherContainer._geometryCollection) { + GeometryCollection& c = *otherContainer._geometryCollection; + + for (size_t i = 0; i < c.points.size(); ++i) { + if (!contains(c.points[i].cell, c.points[i].point)) { + return false; + } + } + + const vector<LineWithCRS*>& lines = c.lines.vector(); + for (size_t i = 0; i < lines.size(); ++i) { + if (!contains(lines[i]->line)) { return false; } + } + + const vector<PolygonWithCRS*>& polys = c.polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (!contains(polys[i]->polygon)) { return false; } + } + + const vector<MultiPointWithCRS*>& multipoints = c.multiPoints.vector(); + for (size_t i = 0; i < multipoints.size(); ++i) { + MultiPointWithCRS* mp = multipoints[i]; + for (size_t j = 0; j < mp->points.size(); ++j) { + if (!contains(mp->cells[j], mp->points[j])) { return false; } + } + } + + const vector<MultiLineWithCRS*>& multilines = c.multiLines.vector(); + for (size_t i = 0; i < multilines.size(); ++i) { + const vector<S2Polyline*>& lines = multilines[i]->lines.vector(); + for (size_t j = 0; j < lines.size(); ++j) { + if (!contains(*lines[j])) { return false; } + } + } + + const vector<MultiPolygonWithCRS*>& multipolys = c.multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector<S2Polygon*>& polys = multipolys[i]->polygons.vector(); + for (size_t j = 0; j < polys.size(); ++j) { + if (!contains(*polys[j])) { return false; } + } + } + + return true; + } + + return false; + } + + bool containsPoint(const S2Polygon& poly, const S2Cell& otherCell, const S2Point& otherPoint) { + // This is much faster for actual containment checking. + if (poly.Contains(otherPoint)) { return true; } + // This is slower but contains edges/vertices. + return poly.MayIntersect(otherCell); + } + + bool GeometryContainer::contains(const S2Cell& otherCell, const S2Point& otherPoint) const { + if (NULL != _polygon && (_polygon->crs == SPHERE)) { + return containsPoint(_polygon->polygon, otherCell, otherPoint); + } + + if (NULL != _cap && (_cap->crs == SPHERE)) { + return _cap->cap.MayIntersect(otherCell); + } + + if (NULL != _multiPolygon) { + const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPoint(*polys[i], otherCell, otherPoint)) { return true; } + } + } + + if (NULL != _geometryCollection) { + const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPoint(polys[i]->polygon, otherCell, otherPoint)) { return true; } + } + + const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector(); + for (size_t j = 0; j < innerpolys.size(); ++j) { + if (containsPoint(*innerpolys[j], otherCell, otherPoint)) { return true; } + } + } + } + + return false; + } + + bool containsLine(const S2Polygon& poly, const S2Polyline& otherLine) { + // Kind of a mess. We get a function for clipping the line to the + // polygon. We do this and make sure the line is the same as the + // line we're clipping against. + vector<S2Polyline*> clipped; + 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)); + for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i]; + return ret; + } + + bool GeometryContainer::contains(const S2Polyline& otherLine) const { + if (NULL != _polygon && (_polygon->crs == SPHERE)) { + return containsLine(_polygon->polygon, otherLine); + } + + if (NULL != _multiPolygon) { + const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsLine(*polys[i], otherLine)) { return true; } + } + } + + if (NULL != _geometryCollection) { + const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsLine(polys[i]->polygon, otherLine)) { return true; } + } + + const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector(); + for (size_t j = 0; j < innerpolys.size(); ++j) { + if (containsLine(*innerpolys[j], otherLine)) { return true; } + } + } + } + + return false; + } + + bool containsPolygon(const S2Polygon& poly, const S2Polygon& otherPoly) { + return poly.Contains(&otherPoly); + } + + bool GeometryContainer::contains(const S2Polygon& otherPolygon) const { + if (NULL != _polygon && (_polygon->crs == SPHERE)) { + return containsPolygon(_polygon->polygon, otherPolygon); + } + + if (NULL != _multiPolygon) { + const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPolygon(*polys[i], otherPolygon)) { return true; } + } + } + + if (NULL != _geometryCollection) { + const vector<PolygonWithCRS*>& polys = _geometryCollection->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (containsPolygon(polys[i]->polygon, otherPolygon)) { return true; } + } + + const vector<MultiPolygonWithCRS*>& multipolys =_geometryCollection->multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector<S2Polygon*>& innerpolys = multipolys[i]->polygons.vector(); + for (size_t j = 0; j < innerpolys.size(); ++j) { + if (containsPolygon(*innerpolys[j], otherPolygon)) { return true; } + } + } + } + return false; } bool GeometryContainer::intersects(const GeometryContainer& otherContainer) const { - if (NULL != otherContainer._cell) { - return intersects(*otherContainer._cell); + if (NULL != otherContainer._point) { + return intersects(otherContainer._point->cell); } else if (NULL != otherContainer._line) { - return intersects(*otherContainer._line); + return intersects(otherContainer._line->line); } else if (NULL != otherContainer._polygon) { - return intersects(*otherContainer._polygon); - } else { - return false; + 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 != _cell) { - return _cell->MayIntersect(otherPoint); + if (NULL != _point) { + return _point->cell.MayIntersect(otherPoint); } else if (NULL != _line) { - return _line->MayIntersect(otherPoint); - } else { - verify(NULL != _polygon); - return _polygon->MayIntersect(otherPoint); + return _line->line.MayIntersect(otherPoint); + } else if (NULL != _polygon) { + return _polygon->polygon.MayIntersect(otherPoint); + } else if (NULL != _multiPoint) { + const vector<S2Cell>& cells = _multiPoint->cells; + for (size_t i = 0; i < cells.size(); ++i) { + if (cells[i].MayIntersect(otherPoint)) { return true; } + } + } else if (NULL != _multiLine) { + const vector<S2Polyline*>& lines = _multiLine->lines.vector(); + for (size_t i = 0; i < lines.size(); ++i) { + if (lines[i]->MayIntersect(otherPoint)) { return true; } + } + } else if (NULL != _multiPolygon) { + const vector<S2Polygon*>& polys = _multiPolygon->polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + if (polys[i]->MayIntersect(otherPoint)) { return true; } + } + } else if (NULL != _geometryCollection) { + const GeometryCollection& c = *_geometryCollection; + + for (size_t i = 0; i < c.points.size(); ++i) { + if (c.points[i].cell.MayIntersect(otherPoint)) { return true; } + } + + for (size_t i = 0; i < c.polygons.vector().size(); ++i) { + if (c.polygons.vector()[i]->polygon.MayIntersect(otherPoint)) { return true; } + } + + for (size_t i = 0; i < c.lines.vector().size(); ++i) { + if (c.lines.vector()[i]->line.MayIntersect(otherPoint)) { return true; } + } + + for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) { + const vector<S2Polygon*>& innerPolys = + c.multiPolygons.vector()[i]->polygons.vector(); + for (size_t j = 0; j < innerPolys.size(); ++j) { + if (innerPolys[j]->MayIntersect(otherPoint)) { return true; } + } + } + + for (size_t i = 0; i < c.multiLines.vector().size(); ++i) { + const vector<S2Polyline*>& innerLines = + c.multiLines.vector()[i]->lines.vector(); + for (size_t j = 0; j < innerLines.size(); ++j) { + if (innerLines[j]->MayIntersect(otherPoint)) { return true; } + } + } + + for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) { + const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells; + for (size_t j = 0; j < innerCells.size(); ++j) { + if (innerCells[j].MayIntersect(otherPoint)) { return true; } + } + } } + + return false; + } + + bool polygonLineIntersection(const S2Polyline& line, const S2Polygon& poly) { + // TODO(hk): modify s2 library to just let us know if it intersected + // rather than returning all this. + vector<S2Polyline*> clipped; + poly.IntersectWithPolyline(&line, &clipped); + bool ret = clipped.size() > 0; + for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i]; + return ret; } bool GeometryContainer::intersects(const S2Polyline& otherLine) const { - if (NULL != _cell) { - return otherLine.MayIntersect(*_cell); + if (NULL != _point) { + return otherLine.MayIntersect(_point->cell); } else if (NULL != _line) { - return otherLine.Intersects(_line.get()); - } else { - verify(NULL != _polygon); - // TODO(hk): modify s2 library to just let us know if it intersected - // rather than returning all this. - vector<S2Polyline*> clipped; - _polygon->IntersectWithPolyline(&otherLine, &clipped); - bool ret = clipped.size() > 0; - for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i]; - return ret; + return otherLine.Intersects(&_line->line); + } else if (NULL != _polygon && (_polygon->crs == SPHERE)) { + return polygonLineIntersection(otherLine, _polygon->polygon); + } else if (NULL != _multiPoint) { + for (size_t i = 0; i < _multiPoint->cells.size(); ++i) { + if (otherLine.MayIntersect(_multiPoint->cells[i])) { return true; } + } + } else if (NULL != _multiLine) { + for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) { + if (otherLine.Intersects(_multiLine->lines.vector()[i])) { + return true; + } + } + } else if (NULL != _multiPolygon) { + for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) { + if (polygonLineIntersection(otherLine, *_multiPolygon->polygons.vector()[i])) { + return true; + } + } + } else if (NULL != _geometryCollection) { + const GeometryCollection& c = *_geometryCollection; + + for (size_t i = 0; i < c.points.size(); ++i) { + if (otherLine.MayIntersect(c.points[i].cell)) { return true; } + } + + for (size_t i = 0; i < c.polygons.vector().size(); ++i) { + if (polygonLineIntersection(otherLine, c.polygons.vector()[i]->polygon)) { + return true; + } + } + + for (size_t i = 0; i < c.lines.vector().size(); ++i) { + if (c.lines.vector()[i]->line.Intersects(&otherLine)) { return true; } + } + + for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) { + const vector<S2Polygon*>& innerPolys = + c.multiPolygons.vector()[i]->polygons.vector(); + for (size_t j = 0; j < innerPolys.size(); ++j) { + if (polygonLineIntersection(otherLine, *innerPolys[j])) { + return true; + } + } + } + + for (size_t i = 0; i < c.multiLines.vector().size(); ++i) { + const vector<S2Polyline*>& innerLines = + c.multiLines.vector()[i]->lines.vector(); + for (size_t j = 0; j < innerLines.size(); ++j) { + if (innerLines[j]->Intersects(&otherLine)) { return true; } + } + } + + for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) { + const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells; + for (size_t j = 0; j < innerCells.size(); ++j) { + if (otherLine.MayIntersect(innerCells[j])) { return true; } + } + } } + + return false; } + // Does 'this' intersect with the provided polygon? bool GeometryContainer::intersects(const S2Polygon& otherPolygon) const { - if (NULL != _cell) { - return otherPolygon.MayIntersect(*_cell); + if (NULL != _point) { + return otherPolygon.MayIntersect(_point->cell); } else if (NULL != _line) { - // TODO(hk): modify s2 library to just let us know if it intersected - // rather than returning all this. - vector<S2Polyline*> clipped; - otherPolygon.IntersectWithPolyline(_line.get(), &clipped); - bool ret = clipped.size() > 0; - for (size_t i = 0; i < clipped.size(); ++i) delete clipped[i]; - return ret; - } else { - verify(NULL != _polygon); - return otherPolygon.Intersects(_polygon.get()); + return polygonLineIntersection(_line->line, otherPolygon); + } else if (NULL != _polygon) { + return otherPolygon.Intersects(&_polygon->polygon); + } else if (NULL != _multiPoint) { + for (size_t i = 0; i < _multiPoint->cells.size(); ++i) { + if (otherPolygon.MayIntersect(_multiPoint->cells[i])) { return true; } + } + } else if (NULL != _multiLine) { + for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) { + if (polygonLineIntersection(*_multiLine->lines.vector()[i], otherPolygon)) { + return true; + } + } + } else if (NULL != _multiPolygon) { + for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) { + if (otherPolygon.Intersects(_multiPolygon->polygons.vector()[i])) { + return true; + } + } + } else if (NULL != _geometryCollection) { + const GeometryCollection& c = *_geometryCollection; + + for (size_t i = 0; i < c.points.size(); ++i) { + if (otherPolygon.MayIntersect(c.points[i].cell)) { return true; } + } + + for (size_t i = 0; i < c.polygons.vector().size(); ++i) { + if (otherPolygon.Intersects(&c.polygons.vector()[i]->polygon)) { + return true; + } + } + + for (size_t i = 0; i < c.lines.vector().size(); ++i) { + if (polygonLineIntersection(c.lines.vector()[i]->line, otherPolygon)) { + return true; + } + } + + for (size_t i = 0; i < c.multiPolygons.vector().size(); ++i) { + const vector<S2Polygon*>& innerPolys = + c.multiPolygons.vector()[i]->polygons.vector(); + for (size_t j = 0; j < innerPolys.size(); ++j) { + if (otherPolygon.Intersects(innerPolys[j])) { + return true; + } + } + } + + for (size_t i = 0; i < c.multiLines.vector().size(); ++i) { + const vector<S2Polyline*>& innerLines = + c.multiLines.vector()[i]->lines.vector(); + for (size_t j = 0; j < innerLines.size(); ++j) { + if (polygonLineIntersection(*innerLines[j], otherPolygon)) { + return true; + } + } + } + + for (size_t i = 0; i < c.multiPoints.vector().size(); ++i) { + const vector<S2Cell>& innerCells = c.multiPoints.vector()[i]->cells; + for (size_t j = 0; j < innerCells.size(); ++j) { + if (otherPolygon.MayIntersect(innerCells[j])) { + return true; + } + } + } } + + return false; } bool GeometryContainer::parseFrom(const BSONObj& obj) { - // Free up any pointers we might have left over from previous parses. *this = GeometryContainer(); - if (GeoParser::isGeoJSONPolygon(obj)) { + + if (GeoParser::isPolygon(obj)) { // We can't really pass these things around willy-nilly except by ptr. - _polygon.reset(new S2Polygon()); - GeoParser::parseGeoJSONPolygon(obj, _polygon.get()); + _polygon.reset(new PolygonWithCRS()); + GeoParser::parsePolygon(obj, _polygon.get()); } else if (GeoParser::isPoint(obj)) { - _cell.reset(new S2Cell()); - GeoParser::parsePoint(obj, _cell.get()); - _oldPoint.reset(new Point()); - GeoParser::parsePoint(obj, _oldPoint.get()); - _point.reset(new S2Point()); + _point.reset(new PointWithCRS()); GeoParser::parsePoint(obj, _point.get()); - } else if (GeoParser::isLineString(obj)) { - _line.reset(new S2Polyline()); - GeoParser::parseLineString(obj, _line.get()); - } else if (GeoParser::isLegacyBox(obj)) { - _oldBox.reset(new Box()); - GeoParser::parseLegacyBox(obj, _oldBox.get()); - } else if (GeoParser::isLegacyPolygon(obj)) { - _oldPolygon.reset(new Polygon()); - GeoParser::parseLegacyPolygon(obj, _oldPolygon.get()); - } else if (GeoParser::isLegacyCenter(obj)) { - _oldCircle.reset(new Circle()); - GeoParser::parseLegacyCenter(obj, _oldCircle.get()); - } else if (GeoParser::isLegacyCenterSphere(obj)) { - _cap.reset(new S2Cap()); - GeoParser::parseLegacyCenterSphere(obj, _cap.get()); + } else if (GeoParser::isLine(obj)) { + _line.reset(new LineWithCRS()); + GeoParser::parseLine(obj, _line.get()); + } else if (GeoParser::isBox(obj)) { + _box.reset(new BoxWithCRS()); + GeoParser::parseBox(obj, _box.get()); + } else if (GeoParser::isCap(obj)) { + _cap.reset(new CapWithCRS()); + GeoParser::parseCap(obj, _cap.get()); + } else if (GeoParser::isMultiPoint(obj)) { + _multiPoint.reset(new MultiPointWithCRS()); + GeoParser::parseMultiPoint(obj, _multiPoint.get()); + _region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiPoint->cells.size(); ++i) { + _region->Add(&_multiPoint->cells[i]); + } + } else if (GeoParser::isMultiLine(obj)) { + _multiLine.reset(new MultiLineWithCRS()); + GeoParser::parseMultiLine(obj, _multiLine.get()); + _region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiLine->lines.vector().size(); ++i) { + _region->Add(_multiLine->lines.vector()[i]); + } + } else if (GeoParser::isMultiPolygon(obj)) { + _multiPolygon.reset(new MultiPolygonWithCRS()); + GeoParser::parseMultiPolygon(obj, _multiPolygon.get()); + _region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _multiPolygon->polygons.vector().size(); ++i) { + _region->Add(_multiPolygon->polygons.vector()[i]); + } + } else if (GeoParser::isGeometryCollection(obj)) { + _geometryCollection.reset(new GeometryCollection()); + GeoParser::parseGeometryCollection(obj, _geometryCollection.get()); + _region.reset(new S2RegionUnion()); + for (size_t i = 0; i < _geometryCollection->points.size(); ++i) { + _region->Add(&_geometryCollection->points[i].cell); + } + for (size_t i = 0; i < _geometryCollection->lines.vector().size(); ++i) { + _region->Add(&_geometryCollection->lines.vector()[i]->line); + } + for (size_t i = 0; i < _geometryCollection->polygons.vector().size(); ++i) { + _region->Add(&_geometryCollection->polygons.vector()[i]->polygon); + } + for (size_t i = 0; i < _geometryCollection->multiPoints.vector().size(); ++i) { + MultiPointWithCRS* multiPoint = _geometryCollection->multiPoints.vector()[i]; + for (size_t j = 0; j < multiPoint->cells.size(); ++j) { + _region->Add(&multiPoint->cells[j]); + } + } + for (size_t i = 0; i < _geometryCollection->multiLines.vector().size(); ++i) { + const MultiLineWithCRS* multiLine = _geometryCollection->multiLines.vector()[i]; + for (size_t j = 0; j < multiLine->lines.vector().size(); ++j) { + _region->Add(multiLine->lines.vector()[j]); + } + } + for (size_t i = 0; i < _geometryCollection->multiPolygons.vector().size(); ++i) { + const MultiPolygonWithCRS* multiPolygon = + _geometryCollection->multiPolygons.vector()[i]; + for (size_t j = 0; j < multiPolygon->polygons.vector().size(); ++j) { + _region->Add(multiPolygon->polygons.vector()[j]); + } + } } else { return false; } - return true; - } - bool GeoQuery::hasS2Region() const { - return geoContainer.hasS2Region(); + return true; } const S2Region& GeometryContainer::getRegion() const { - if (NULL != _cell) { - return *_cell; + if (NULL != _point) { + // _point->crs might be FLAT but we "upgrade" it for free. + return _point->cell; } else if (NULL != _line) { - return *_line; - } else if (NULL != _cap) { - return *_cap; + return _line->line; + } else if (NULL != _cap && SPHERE == _cap->crs) { + return _cap->cap; + } else if (NULL != _multiPoint) { + return *_region; + } else if (NULL != _multiLine) { + return *_region; + } else if (NULL != _multiPolygon) { + return *_region; + } else if (NULL != _geometryCollection) { + return *_region; } else { verify(NULL != _polygon); - return *_polygon; + verify(SPHERE == _polygon->crs); + return _polygon->polygon; } } } // namespace mongo diff --git a/src/mongo/db/geo/geoquery.h b/src/mongo/db/geo/geoquery.h index 0b67eaf41a6..31ecb5df311 100644 --- a/src/mongo/db/geo/geoquery.h +++ b/src/mongo/db/geo/geoquery.h @@ -14,66 +14,74 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#pragma once + #include "mongo/db/geo/geoparser.h" +#include "mongo/db/geo/shapes.h" #include "mongo/util/mongoutils/str.h" -#include "third_party/s2/s2.h" -#include "third_party/s2/s2cap.h" -#include "third_party/s2/s2regioncoverer.h" -#include "third_party/s2/s2cell.h" -#include "third_party/s2/s2polyline.h" -#include "third_party/s2/s2polygon.h" -#include "third_party/s2/s2regioncoverer.h" - -#pragma once +#include "third_party/s2/s2regionunion.h" namespace mongo { + class GeometryContainer { public: bool parseFrom(const BSONObj &obj); - // Does we intersect the provided data? Sadly there is no common good - // way to check this, so we do different things for all pairs of - // geometry_of(query,data). + /** + * 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; - bool intersects(const S2Cell& otherPoint) const; - bool intersects(const S2Polyline& otherLine) const; - bool intersects(const S2Polygon& otherPolygon) const; - // And, within. + + /** + * 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; - bool supportsContains() const { - return NULL != _polygon.get() - || NULL != _cap.get() - || NULL != _oldPolygon.get() - || NULL != _oldCircle.get(); - } + /** + * Only polygons (and aggregate types thereof) support contains. + */ + bool supportsContains() const; - bool hasS2Region() const { - return NULL != _cell - || NULL != _line - || NULL != _polygon - || NULL != _cap; - } + bool hasS2Region() const; // Used by s2cursor only to generate a covering of the query object. // One region is not NULL and this returns it. const S2Region& getRegion() const; private: + // 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. - shared_ptr<S2Cell> _cell; - // If we have _cell we have _point. We need _cell in some cases, _point in others. - shared_ptr<S2Point> _point; - - shared_ptr<S2Polyline> _line; - shared_ptr<S2Polygon> _polygon; - shared_ptr<S2Cap> _cap; - // Legacy shapes. - shared_ptr<Polygon> _oldPolygon; - shared_ptr<Box> _oldBox; - shared_ptr<Circle> _oldCircle; - shared_ptr<Point> _oldPoint; + shared_ptr<PointWithCRS> _point; + shared_ptr<LineWithCRS> _line; + shared_ptr<PolygonWithCRS> _polygon; + shared_ptr<CapWithCRS> _cap; + shared_ptr<MultiPointWithCRS> _multiPoint; + shared_ptr<MultiLineWithCRS> _multiLine; + shared_ptr<MultiPolygonWithCRS> _multiPolygon; + shared_ptr<GeometryCollection> _geometryCollection; + shared_ptr<BoxWithCRS> _box; + + shared_ptr<S2RegionUnion> _region; }; class NearQuery { @@ -84,7 +92,7 @@ namespace mongo { bool parseFrom(const BSONObj &obj, double radius); bool parseFromGeoNear(const BSONObj &obj, double radius); string field; - S2Point centroid; + PointWithCRS centroid; // Distance IN METERS that we're willing to search. double maxDistance; // Did we convert to this distance from radians? (If so, we output distances in radians.) diff --git a/src/mongo/db/geo/s2common.cpp b/src/mongo/db/geo/s2common.cpp index 217c2a60f06..8021767d8e7 100644 --- a/src/mongo/db/geo/s2common.cpp +++ b/src/mongo/db/geo/s2common.cpp @@ -1,4 +1,3 @@ -// XXX THIS FILE IS DEPRECATED. PLEASE DON'T MODIFY. /** * Copyright (C) 2012 10gen Inc. * @@ -17,6 +16,12 @@ #include "mongo/db/geo/s2common.h" +#include "mongo/db/geo/geoparser.h" +#include "mongo/db/geo/geoquery.h" +#include "third_party/s2/s2.h" +#include "third_party/s2/s2cell.h" +#include "third_party/s2/s2regioncoverer.h" + namespace mongo { static string myitoa(int d) { @@ -25,6 +30,151 @@ namespace mongo { return ss.str(); } + static void keysFromRegion(S2RegionCoverer *coverer, const S2Region ®ion, + vector<string> *out) { + vector<S2CellId> covering; + coverer->GetCovering(region, &covering); + for (size_t i = 0; i < covering.size(); ++i) { + out->push_back(covering[i].toString()); + } + } + + bool S2SearchUtil::getKeysForObject(const BSONObj& obj, const S2IndexingParams& params, + vector<string>* out) { + S2RegionCoverer coverer; + params.configureCoverer(&coverer); + + GeometryContainer geoContainer; + if (!geoContainer.parseFrom(obj)) { return false; } + if (!geoContainer.hasS2Region()) { return false; } + + keysFromRegion(&coverer, geoContainer.getRegion(), out); + + return true; + } + + double dist(const S2Point& a, const S2Point& b) { + S1Angle angle(a, b); + return angle.radians(); + } + + double dist(const S2Point& a, const MultiPointWithCRS& b) { + double minDist = numeric_limits<double>::max(); + for (size_t i = 0; i < b.points.size(); ++i) { + minDist = min(minDist, dist(a, b.points[i])); + } + return minDist; + } + + double dist(const S2Point& a, const S2Polyline& b) { + int tmp; + S1Angle angle(a, b.Project(a, &tmp)); + return angle.radians(); + } + + double dist(const S2Point& a, const MultiLineWithCRS& b) { + double minDist = numeric_limits<double>::max(); + for (size_t i = 0; i < b.lines.vector().size(); ++i) { + minDist = min(minDist, dist(a, *b.lines.vector()[i])); + } + return minDist; + } + + double dist(const S2Point& a, const S2Polygon& b) { + S1Angle angle(a, b.Project(a)); + return angle.radians(); + } + + double dist(const S2Point& a, const MultiPolygonWithCRS& b) { + double minDist = numeric_limits<double>::max(); + for (size_t i = 0; i < b.polygons.vector().size(); ++i) { + minDist = min(minDist, dist(a, *b.polygons.vector()[i])); + } + return minDist; + } + + bool S2SearchUtil::distanceBetween(const S2Point& us, const BSONObj& them, + const S2IndexingParams ¶ms, double *out) { + if (GeoParser::isGeometryCollection(them)) { + GeometryCollection c; + GeoParser::parseGeometryCollection(them, &c); + double minDist = numeric_limits<double>::max(); + + for (size_t i = 0; i < c.points.size(); ++i) { + minDist = min(minDist, dist(us, c.points[i].point)); + } + + const vector<LineWithCRS*>& lines = c.lines.vector(); + for (size_t i = 0; i < lines.size(); ++i) { + minDist = min(minDist, dist(us, lines[i]->line)); + } + + const vector<PolygonWithCRS*>& polys = c.polygons.vector(); + for (size_t i = 0; i < polys.size(); ++i) { + minDist = min(minDist, dist(us, polys[i]->polygon)); + } + + const vector<MultiPointWithCRS*>& multipoints = c.multiPoints.vector(); + for (size_t i = 0; i < multipoints.size(); ++i) { + MultiPointWithCRS* mp = multipoints[i]; + for (size_t j = 0; j < mp->points.size(); ++j) { + minDist = min(minDist, dist(us, mp->points[i])); + } + } + + const vector<MultiLineWithCRS*>& multilines = c.multiLines.vector(); + for (size_t i = 0; i < multilines.size(); ++i) { + const vector<S2Polyline*>& lines = multilines[i]->lines.vector(); + for (size_t j = 0; j < lines.size(); ++j) { + minDist = min(minDist, dist(us, *lines[j])); + } + } + + const vector<MultiPolygonWithCRS*>& multipolys = c.multiPolygons.vector(); + for (size_t i = 0; i < multipolys.size(); ++i) { + const vector<S2Polygon*>& polys = multipolys[i]->polygons.vector(); + for (size_t j = 0; j < polys.size(); ++j) { + minDist = min(minDist, dist(us, *polys[j])); + } + } + + *out = params.radius * minDist; + return true; + } if (GeoParser::isMultiPoint(them)) { + MultiPointWithCRS multiPoint; + GeoParser::parseMultiPoint(them, &multiPoint); + *out = dist(us, multiPoint) * params.radius; + return true; + } else if (GeoParser::isMultiLine(them)) { + MultiLineWithCRS multiLine; + GeoParser::parseMultiLine(them, &multiLine); + *out = dist(us, multiLine) * params.radius; + return true; + } else if (GeoParser::isMultiPolygon(them)) { + MultiPolygonWithCRS multiPolygon; + GeoParser::parseMultiPolygon(them, &multiPolygon); + *out = dist(us, multiPolygon) * params.radius; + return true; + } else if (GeoParser::isPolygon(them)) { + PolygonWithCRS poly; + GeoParser::parsePolygon(them, &poly); + *out = dist(us, poly.polygon) * params.radius; + return true; + } else if (GeoParser::isLine(them)) { + LineWithCRS line; + GeoParser::parseLine(them, &line); + *out = dist(us, line.line) * params.radius; + return true; + } else if (GeoParser::isPoint(them)) { + PointWithCRS point; + GeoParser::parsePoint(them, &point); + *out = dist(us, point.point) * params.radius; + return true; + } else { + return false; + } + } + void S2SearchUtil::setCoverLimitsBasedOnArea(double area, S2RegionCoverer *coverer, int coarsestIndexedLevel) { area = sqrt(area); diff --git a/src/mongo/db/geo/s2common.h b/src/mongo/db/geo/s2common.h index b132dfdce02..ea933876156 100644 --- a/src/mongo/db/geo/s2common.h +++ b/src/mongo/db/geo/s2common.h @@ -27,6 +27,41 @@ namespace mongo { + struct S2IndexingParams { + static const double kRadiusOfEarthInMeters; + + // Since we take the cartesian product when we generate keys for an insert, + // we need a cap. + size_t maxKeysPerInsert; + // This is really an advisory parameter that we pass to the cover generator. The + // finest/coarsest index level determine the required # of cells. + int maxCellsInCovering; + // What's the finest grained level that we'll index? When we query for a point + // we start at that -- we index nothing finer than this. + int finestIndexedLevel; + // And, what's the coarsest? When we search in larger coverings we know we + // can stop here -- we index nothing coarser than this. + int coarsestIndexedLevel; + + double radius; + + string toString() const { + stringstream ss; + ss << "maxKeysPerInsert: " << maxKeysPerInsert << endl; + ss << "maxCellsInCovering: " << maxCellsInCovering << endl; + ss << "finestIndexedLevel: " << finestIndexedLevel << endl; + ss << "coarsestIndexedLevel: " << coarsestIndexedLevel << endl; + return ss.str(); + } + + void configureCoverer(S2RegionCoverer *coverer) const { + coverer->set_min_level(coarsestIndexedLevel); + coverer->set_max_level(finestIndexedLevel); + // This is advisory; the two above are strict. + coverer->set_max_cells(maxCellsInCovering); + } + }; + class S2SearchUtil { public: // Given a coverer, region, and field name, generate a BSONObj that we can pass to a @@ -34,6 +69,10 @@ namespace mongo { static BSONObj coverAsBSON(const vector<S2CellId> &cover, const string& field, const int coarsestIndexedLevel); static void setCoverLimitsBasedOnArea(double area, S2RegionCoverer *coverer, int coarsestIndexedLevel); + static bool getKeysForObject(const BSONObj& obj, const S2IndexingParams& params, + vector<string>* out); + static bool distanceBetween(const S2Point& us, const BSONObj& them, + const S2IndexingParams ¶ms, double *out); }; } // namespace mongo diff --git a/src/mongo/db/geo/shapes.cpp b/src/mongo/db/geo/shapes.cpp index 136ab1cf979..425f4b8f91d 100644 --- a/src/mongo/db/geo/shapes.cpp +++ b/src/mongo/db/geo/shapes.cpp @@ -459,4 +459,5 @@ namespace mongo { return sqrt((a * a) + (b * b)); } + } // namespace mongo diff --git a/src/mongo/db/geo/shapes.h b/src/mongo/db/geo/shapes.h index 7ec31bf23da..96f8ec621ae 100644 --- a/src/mongo/db/geo/shapes.h +++ b/src/mongo/db/geo/shapes.h @@ -16,10 +16,20 @@ #pragma once -#include "mongo/pch.h" +#include <string> +#include <vector> + +#include "mongo/base/owned_pointer_vector.h" #include "mongo/db/jsobj.h" +#include "third_party/s2/s2.h" +#include "third_party/s2/s2cap.h" +#include "third_party/s2/s2cell.h" +#include "third_party/s2/s2latlng.h" +#include "third_party/s2/s2polygon.h" +#include "third_party/s2/s2polyline.h" namespace mongo { + struct Point; double distance(const Point& p1, const Point &p2); bool distanceWithin(const Point &p1, const Point &p2, double radius); @@ -103,4 +113,73 @@ namespace mongo { bool _boundsCalculated; vector<Point> _points; }; + + // Clearly this isn't right but currently it's sufficient. + enum CRS { + FLAT, + SPHERE + }; + + struct PointWithCRS { + S2Point point; + S2Cell cell; + Point oldPoint; + CRS crs; + }; + + struct LineWithCRS { + S2Polyline line; + CRS crs; + }; + + struct CapWithCRS { + S2Cap cap; + Circle circle; + CRS crs; + }; + + struct BoxWithCRS { + Box box; + CRS crs; + }; + + struct PolygonWithCRS { + S2Polygon polygon; + Polygon oldPolygon; + CRS crs; + }; + + struct MultiPointWithCRS { + vector<S2Point> points; + vector<S2Cell> cells; + CRS crs; + }; + + struct MultiLineWithCRS { + OwnedPointerVector<S2Polyline> lines; + CRS crs; + }; + + struct MultiPolygonWithCRS { + OwnedPointerVector<S2Polygon> polygons; + CRS crs; + }; + + struct GeometryCollection { + vector<PointWithCRS> points; + + // The amount of indirection here is painful but we can't operator= scoped_ptr or + // OwnedPointerVector. + OwnedPointerVector<LineWithCRS> lines; + OwnedPointerVector<PolygonWithCRS> polygons; + OwnedPointerVector<MultiPointWithCRS> multiPoints; + OwnedPointerVector<MultiLineWithCRS> multiLines; + OwnedPointerVector<MultiPolygonWithCRS> multiPolygons; + + bool supportsContains() { + // Only polygons (and multiPolygons) support containment. + return (polygons.vector().size() > 0 || multiPolygons.vector().size() > 0); + } + }; + } // namespace mongo diff --git a/src/mongo/db/index/s2_access_method.cpp b/src/mongo/db/index/s2_access_method.cpp index c43ecc75964..e6189f03308 100644 --- a/src/mongo/db/index/s2_access_method.cpp +++ b/src/mongo/db/index/s2_access_method.cpp @@ -20,27 +20,10 @@ #include "mongo/base/status.h" #include "mongo/db/geo/geoparser.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index_names.h" #include "mongo/db/index/s2_index_cursor.h" #include "mongo/db/jsobj.h" -#include "third_party/s2/s2.h" -#include "third_party/s2/s2cell.h" -#include "third_party/s2/s2polygon.h" -#include "third_party/s2/s2polyline.h" -#include "third_party/s2/s2regioncoverer.h" - -namespace { - - static void keysFromRegion(S2RegionCoverer *coverer, const S2Region ®ion, - vector<string> *out) { - vector<S2CellId> covering; - coverer->GetCovering(region, &covering); - for (size_t i = 0; i < covering.size(); ++i) { - out->push_back(covering[i].toString()); - } - } - -} // namespace namespace mongo { @@ -154,34 +137,16 @@ namespace mongo { // Get the index keys for elements that are GeoJSON. void S2AccessMethod::getGeoKeys(const BSONElementSet& elements, BSONObjSet* out) const { - S2RegionCoverer coverer; - _params.configureCoverer(&coverer); - - // See here for GeoJSON format: geojson.org/geojson-spec.html for (BSONElementSet::iterator i = elements.begin(); i != elements.end(); ++i) { uassert(16754, "Can't parse geometry from element: " + i->toString(), i->isABSONObj()); const BSONObj &obj = i->Obj(); vector<string> cells; - S2Polyline line; - S2Cell point; - // We only support GeoJSON polygons. Why?: - // 1. we don't automagically do WGS84/flat -> WGS84, and - // 2. the old polygon format must die. - if (GeoParser::isGeoJSONPolygon(obj)) { - S2Polygon polygon; - GeoParser::parseGeoJSONPolygon(obj, &polygon); - keysFromRegion(&coverer, polygon, &cells); - } else if (GeoParser::parseLineString(obj, &line)) { - keysFromRegion(&coverer, line, &cells); - } else if (GeoParser::parsePoint(obj, &point)) { - S2CellId parent(point.id().parent(_params.finestIndexedLevel)); - cells.push_back(parent.toString()); - } else { - uasserted(16755, "Can't extract geo keys from object, malformed geometry?:" - + obj.toString()); - } + bool succeeded = S2SearchUtil::getKeysForObject(obj, _params, &cells); + uassert(16755, "Can't extract geo keys from object, malformed geometry?:" + + obj.toString(), succeeded); + uassert(16756, "Unable to generate keys for (likely malformed) geometry: " + obj.toString(), cells.size() > 0); diff --git a/src/mongo/db/index/s2_access_method.h b/src/mongo/db/index/s2_access_method.h index 7206ec35e2f..73befcdfc76 100644 --- a/src/mongo/db/index/s2_access_method.h +++ b/src/mongo/db/index/s2_access_method.h @@ -17,9 +17,9 @@ #pragma once #include "mongo/base/status.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index/btree_access_method_internal.h" #include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/s2_common.h" #include "mongo/db/jsobj.h" namespace mongo { diff --git a/src/mongo/db/index/s2_common.h b/src/mongo/db/index/s2_common.h deleted file mode 100644 index 6f10f9fd760..00000000000 --- a/src/mongo/db/index/s2_common.h +++ /dev/null @@ -1,72 +0,0 @@ -/** -* Copyright (C) 2012 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 <http://www.gnu.org/licenses/>. -*/ - -#pragma once - -#include <vector> - -#include "third_party/s2/s2.h" -#include "third_party/s2/s2cell.h" -#include "third_party/s2/s2regioncoverer.h" - -namespace mongo { - - // This is used by both s2cursor and s2nearcursor. - class S2SearchUtil { - public: - // Given a coverer, region, and field name, generate a BSONObj that we can pass to a - // FieldRangeSet so that we only examine the keys that the provided region may intersect. - static BSONObj coverAsBSON(const vector<S2CellId> &cover, const string& field, - const int coarsestIndexedLevel); - static void setCoverLimitsBasedOnArea(double area, S2RegionCoverer *coverer, - int coarsestIndexedLevel); - }; - - struct S2IndexingParams { - static const double kRadiusOfEarthInMeters; - - // Since we take the cartesian product when we generate keys for an insert, - // we need a cap. - size_t maxKeysPerInsert; - // This is really an advisory parameter that we pass to the cover generator. The - // finest/coarsest index level determine the required # of cells. - int maxCellsInCovering; - // What's the finest grained level that we'll index? When we query for a point - // we start at that -- we index nothing finer than this. - int finestIndexedLevel; - // And, what's the coarsest? When we search in larger coverings we know we - // can stop here -- we index nothing coarser than this. - int coarsestIndexedLevel; - - double radius; - - string toString() const { - stringstream ss; - ss << "maxKeysPerInsert: " << maxKeysPerInsert << endl; - ss << "maxCellsInCovering: " << maxCellsInCovering << endl; - ss << "finestIndexedLevel: " << finestIndexedLevel << endl; - ss << "coarsestIndexedLevel: " << coarsestIndexedLevel << endl; - return ss.str(); - } - - void configureCoverer(S2RegionCoverer *coverer) const { - coverer->set_min_level(coarsestIndexedLevel); - coverer->set_max_level(finestIndexedLevel); - // This is advisory; the two above are strict. - coverer->set_max_cells(maxCellsInCovering); - } - }; -} // namespace mongo diff --git a/src/mongo/db/index/s2_index_cursor.h b/src/mongo/db/index/s2_index_cursor.h index 5dd72519fb2..9268440ad99 100644 --- a/src/mongo/db/index/s2_index_cursor.h +++ b/src/mongo/db/index/s2_index_cursor.h @@ -20,9 +20,9 @@ #include "mongo/db/btreecursor.h" #include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index/index_cursor.h" #include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/s2_common.h" #include "mongo/db/jsobj.h" #include "mongo/db/pdfile.h" #include "mongo/platform/unordered_set.h" diff --git a/src/mongo/db/index/s2_near_cursor.cpp b/src/mongo/db/index/s2_near_cursor.cpp index 52648d440f4..2a5cd197b16 100644 --- a/src/mongo/db/index/s2_near_cursor.cpp +++ b/src/mongo/db/index/s2_near_cursor.cpp @@ -146,9 +146,9 @@ namespace mongo { // Caps are inclusive and inverting a cap includes the border. This means that our // initial _innerRadius of 0 is OK -- we'll still find a point that is exactly at // the start of our search. - _innerCap = S2Cap::FromAxisAngle(_nearQuery.centroid, + _innerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, S1Angle::Radians(_innerRadius / _params.radius)); - _outerCap = S2Cap::FromAxisAngle(_nearQuery.centroid, + _outerCap = S2Cap::FromAxisAngle(_nearQuery.centroid.point, S1Angle::Radians(_outerRadius / _params.radius)); double area = _outerCap.area() - _innerCap.area(); _innerCap = _innerCap.Complement(); @@ -295,7 +295,15 @@ namespace mongo { for (BSONElementSet::iterator oi = geoFieldElements.begin(); oi != geoFieldElements.end(); ++oi) { if (!oi->isABSONObj()) { continue; } - double dist = distanceTo(oi->Obj()); + BSONObj obj = oi->Obj(); + double dist; + bool ret = S2SearchUtil::distanceBetween(_nearQuery.centroid.point, + obj, _params, &dist); + if (!ret) { + warning() << "unknown geometry: " << obj.toString(); + dist = numeric_limits<double>::max(); + } + minDistance = min(dist, minDistance); } @@ -341,26 +349,4 @@ namespace mongo { ++_stats._numShells; } - double S2NearIndexCursor::distanceTo(const BSONObj& obj) { - const S2Point &us = _nearQuery.centroid; - S2Point them; - - S2Polygon polygon; - S2Polyline line; - S2Cell point; - if (GeoParser::parsePolygon(obj, &polygon)) { - them = polygon.Project(us); - } else if (GeoParser::parseLineString(obj, &line)) { - int tmp; - them = line.Project(us, &tmp); - } else if (GeoParser::parsePoint(obj, &point)) { - them = point.GetCenter(); - } else { - warning() << "unknown geometry: " << obj.toString(); - return numeric_limits<double>::max(); - } - S1Angle angle(us, them); - return angle.radians() * _params.radius; - } - } // namespace mongo diff --git a/src/mongo/db/index/s2_near_cursor.h b/src/mongo/db/index/s2_near_cursor.h index a02bd8727ca..480db1210ac 100644 --- a/src/mongo/db/index/s2_near_cursor.h +++ b/src/mongo/db/index/s2_near_cursor.h @@ -20,9 +20,9 @@ #include "mongo/db/btreecursor.h" #include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index/index_cursor.h" #include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/s2_common.h" #include "mongo/db/jsobj.h" #include "mongo/db/pdfile.h" #include "mongo/platform/unordered_set.h" diff --git a/src/mongo/db/index/s2_simple_cursor.h b/src/mongo/db/index/s2_simple_cursor.h index d8dd60f96ab..fadcf3e24e2 100644 --- a/src/mongo/db/index/s2_simple_cursor.h +++ b/src/mongo/db/index/s2_simple_cursor.h @@ -20,9 +20,9 @@ #include "mongo/db/btreecursor.h" #include "mongo/db/geo/geoquery.h" +#include "mongo/db/geo/s2common.h" #include "mongo/db/index/index_cursor.h" #include "mongo/db/index/index_descriptor.h" -#include "mongo/db/index/s2_common.h" #include "mongo/db/jsobj.h" #include "mongo/db/pdfile.h" #include "mongo/platform/unordered_set.h" diff --git a/src/third_party/s2/s2regionunion.cc b/src/third_party/s2/s2regionunion.cc index fa774de5ac8..a3e2e5b228b 100644 --- a/src/third_party/s2/s2regionunion.cc +++ b/src/third_party/s2/s2regionunion.cc @@ -13,10 +13,12 @@ S2RegionUnion::S2RegionUnion(vector<S2Region*>* regions) { } S2RegionUnion::~S2RegionUnion() { + /* for (size_t i = 0; i < regions_.size(); ++i) { delete regions_[i]; } regions_.clear(); + */ } void S2RegionUnion::Init(vector<S2Region*>* regions) { diff --git a/src/third_party/s2/s2regionunion.h b/src/third_party/s2/s2regionunion.h index 632130b4667..49987a66156 100644 --- a/src/third_party/s2/s2regionunion.h +++ b/src/third_party/s2/s2regionunion.h @@ -23,7 +23,8 @@ class S2RegionUnion : public S2Region { S2RegionUnion(); // Create a region representing the union of the given regions. - // Takes ownership of all regions and clears the given vector. + // DOES NOT take ownership of all regions. + // clears the given vector. S2RegionUnion(vector<S2Region*>* regions); virtual ~S2RegionUnion(); |