2
* Copyright (C) 2012 10gen Inc.
4
* This program is free software: you can redistribute it and/or modify
5
* it under the terms of the GNU Affero General Public License, version 3,
6
* as published by the Free Software Foundation.
8
* This program is distributed in the hope that it will be useful,
9
* but WITHOUT ANY WARRANTY; without even the implied warranty of
10
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
* GNU Affero General Public License for more details.
13
* You should have received a copy of the GNU Affero General Public License
14
* along with this program. If not, see <http://www.gnu.org/licenses/>.
19
#include "mongo/db/jsobj.h"
20
#include "mongo/db/geo/geoparser.h"
21
#include "mongo/util/mongoutils/str.h"
22
#include "third_party/s2/s2.h"
23
#include "third_party/s2/s2cap.h"
24
#include "third_party/s2/s2cell.h"
25
#include "third_party/s2/s2latlng.h"
26
#include "third_party/s2/s2loop.h"
27
#include "third_party/s2/s2polygon.h"
28
#include "third_party/s2/s2polygonbuilder.h"
29
#include "third_party/s2/s2polyline.h"
32
// This field must be present, and...
33
static const string GEOJSON_TYPE = "type";
34
// Have one of these three values:
35
static const string GEOJSON_TYPE_POINT = "Point";
36
static const string GEOJSON_TYPE_LINESTRING = "LineString";
37
static const string GEOJSON_TYPE_POLYGON = "Polygon";
38
// This field must also be present. The value depends on the type.
39
static const string GEOJSON_COORDINATES = "coordinates";
41
//// Utility functions used by GeoParser functions below.
42
static S2Point coordToPoint(double p0, double p1) {
43
return S2LatLng::FromDegrees(p1, p0).Normalized().ToPoint();
46
static S2Point coordsToPoint(const vector<BSONElement>& coordElt) {
47
return coordToPoint(coordElt[0].Number(), coordElt[1].Number());
50
static void parsePoints(const vector<BSONElement>& coordElt, vector<S2Point>* out) {
51
for (size_t i = 0; i < coordElt.size(); ++i) {
52
const vector<BSONElement>& pointElt = coordElt[i].Array();
53
if (pointElt.empty()) { continue; }
54
out->push_back(coordsToPoint(pointElt));
58
static bool isArrayOfCoordinates(const vector<BSONElement>& coordinateArray) {
59
for (size_t i = 0; i < coordinateArray.size(); ++i) {
60
// Each coordinate should be an array
61
if (Array != coordinateArray[i].type()) { return false; }
63
const vector<BSONElement> &thisCoord = coordinateArray[i].Array();
64
if (2 != thisCoord.size()) { return false; }
66
for (size_t j = 0; j < thisCoord.size(); ++j) {
67
if (!thisCoord[j].isNumber()) { return false; }
69
// ...where the latitude is valid
70
double lat = thisCoord[1].Number();
71
double lng = thisCoord[0].Number();
72
if (lat < -90 || lat > 90) { return false; }
73
if (lng < -180 || lng > 180) { return false; }
78
// Coordinates looks like [[0,0],[5,0],[5,5],[0,5],[0,0]]
79
static bool isLoopClosed(const vector<BSONElement>& coordinates) {
80
double x1, y1, x2, y2;
81
x1 = coordinates[0].Array()[0].Number();
82
y1 = coordinates[0].Array()[1].Number();
83
x2 = coordinates[coordinates.size() - 1].Array()[0].Number();
84
y2 = coordinates[coordinates.size() - 1].Array()[1].Number();
85
return (fabs(x1 - x2) < 1e-6) && fabs(y1 - y2) < 1e-6;
88
//// What we publicly export
89
bool GeoParser::isGeoJSONPoint(const BSONObj& obj) {
90
BSONElement type = obj.getFieldDotted(GEOJSON_TYPE);
91
if (type.eoo() || (String != type.type())) { return false; }
92
if (GEOJSON_TYPE_POINT != type.String()) { return false; }
95
warning() << "Invalid CRS: " << obj.toString() << endl;
99
BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES);
100
if (coordElt.eoo() || (Array != coordElt.type())) { return false; }
102
const vector<BSONElement>& coordinates = coordElt.Array();
103
if (coordinates.size() != 2) { return false; }
104
if (!coordinates[0].isNumber() || !coordinates[1].isNumber()) { return false; }
105
double lat = coordinates[1].Number();
106
double lng = coordinates[0].Number();
107
return lat >= -90 && lat <= 90 && lng >= -180 && lng <= 180;
110
void GeoParser::parseGeoJSONPoint(const BSONObj& obj, S2Cell* out) {
111
S2Point point = coordsToPoint(obj.getFieldDotted(GEOJSON_COORDINATES).Array());
112
*out = S2Cell(point);
115
void GeoParser::parseGeoJSONPoint(const BSONObj& obj, Point* out) {
116
const vector<BSONElement>& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array();
117
out->x = coords[0].Number();
118
out->y = coords[1].Number();
121
void GeoParser::parseGeoJSONPoint(const BSONObj& obj, S2Point* out) {
122
const vector<BSONElement>& coords = obj.getFieldDotted(GEOJSON_COORDINATES).Array();
123
*out = coordsToPoint(coords);
126
bool GeoParser::isGeoJSONLineString(const BSONObj& obj) {
127
BSONElement type = obj.getFieldDotted(GEOJSON_TYPE);
128
if (type.eoo() || (String != type.type())) { return false; }
129
if (GEOJSON_TYPE_LINESTRING != type.String()) { return false; }
132
warning() << "Invalid CRS: " << obj.toString() << endl;
136
BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES);
137
if (coordElt.eoo() || (Array != coordElt.type())) { return false; }
139
const vector<BSONElement>& coordinateArray = coordElt.Array();
140
if (coordinateArray.size() < 2) { return false; }
141
if (!isArrayOfCoordinates(coordinateArray)) { return false; }
142
vector<S2Point> vertices;
143
parsePoints(obj.getFieldDotted(GEOJSON_COORDINATES).Array(), &vertices);
144
return S2Polyline::IsValid(vertices);
147
void GeoParser::parseGeoJSONLineString(const BSONObj& obj, S2Polyline* out) {
148
vector<S2Point> vertices;
149
parsePoints(obj.getFieldDotted(GEOJSON_COORDINATES).Array(), &vertices);
153
bool GeoParser::isGeoJSONPolygon(const BSONObj& obj) {
154
BSONElement type = obj.getFieldDotted(GEOJSON_TYPE);
155
if (type.eoo() || (String != type.type())) { return false; }
156
if (GEOJSON_TYPE_POLYGON != type.String()) { return false; }
159
warning() << "Invalid CRS: " << obj.toString() << endl;
163
BSONElement coordElt = obj.getFieldDotted(GEOJSON_COORDINATES);
164
if (coordElt.eoo() || (Array != coordElt.type())) { return false; }
166
const vector<BSONElement>& coordinates = coordElt.Array();
167
// Must be at least one element, the outer shell
168
if (coordinates.empty()) { return false; }
169
// Verify that the shell is a bunch'a coordinates.
170
for (size_t i = 0; i < coordinates.size(); ++i) {
171
if (Array != coordinates[i].type()) { return false; }
172
const vector<BSONElement>& thisLoop = coordinates[i].Array();
173
// A triangle is the simplest 2d shape, and we repeat a vertex, so, 4.
174
if (thisLoop.size() < 4) { return false; }
175
if (!isArrayOfCoordinates(thisLoop)) { return false; }
176
if (!isLoopClosed(thisLoop)) { return false; }
181
void GeoParser::parseGeoJSONPolygon(const BSONObj& obj, S2Polygon* out) {
182
const vector<BSONElement>& coordinates =
183
obj.getFieldDotted(GEOJSON_COORDINATES).Array();
185
const vector<BSONElement>& exteriorRing = coordinates[0].Array();
186
vector<S2Point> exteriorVertices;
187
parsePoints(exteriorRing, &exteriorVertices);
188
// The last point is duplicated. We drop it, since S2Loop expects no
190
exteriorVertices.resize(exteriorVertices.size() - 1);
192
S2PolygonBuilderOptions polyOptions;
193
polyOptions.set_validate(true);
194
// Don't silently eliminate duplicate edges.
195
polyOptions.set_xor_edges(false);
196
S2PolygonBuilder polyBuilder(polyOptions);
197
S2Loop exteriorLoop(exteriorVertices);
198
exteriorLoop.Normalize();
199
if (exteriorLoop.is_hole()) {
200
exteriorLoop.Invert();
202
uassert(16693, "Exterior shell of polygon is invalid: " + obj.toString(),
203
exteriorLoop.IsValid());
204
polyBuilder.AddLoop(&exteriorLoop);
206
// Subsequent arrays of coordinates are interior rings/holes.
207
for (size_t i = 1; i < coordinates.size(); ++i) {
208
vector<S2Point> holePoints;
209
parsePoints(coordinates[i].Array(), &holePoints);
210
// Drop the duplicated last point.
211
holePoints.resize(holePoints.size() - 1);
212
// Interior rings are clockwise.
213
S2Loop holeLoop(holePoints);
214
holeLoop.Normalize();
215
uassert(16694, "Interior hole of polygon is invalid: " + obj.toString(),
217
if (!holeLoop.is_hole()) {
220
polyBuilder.AddLoop(&holeLoop);
223
uassert(16695, "Couldn't assemble polygon: " + obj.toString(),
224
polyBuilder.AssemblePolygon(out, NULL));
227
bool GeoParser::parsePoint(const BSONObj &obj, Point *out) {
228
if (isGeoJSONPoint(obj)) {
229
parseGeoJSONPoint(obj, out);
231
} else if (isLegacyPoint(obj)) {
232
parseLegacyPoint(obj, out);
238
bool GeoParser::parsePoint(const BSONObj &obj, S2Point *out) {
239
if (isGeoJSONPoint(obj)) {
240
parseGeoJSONPoint(obj, out);
242
} else if (isLegacyPoint(obj)) {
243
BSONObjIterator it(obj);
244
BSONElement x = it.next();
245
BSONElement y = it.next();
246
*out = coordToPoint(x.number(), y.number());
252
bool GeoParser::parsePoint(const BSONObj &obj, S2Cell *out) {
254
if (parsePoint(obj, &point)) {
255
*out = S2Cell(point);
261
bool GeoParser::parseLineString(const BSONObj &obj, S2Polyline *out) {
262
if (!isGeoJSONLineString(obj)) { return false; }
263
parseGeoJSONLineString(obj, out);
267
void GeoParser::parseLegacyPoint(const BSONObj &obj, S2Point *out) {
268
BSONObjIterator it(obj);
269
BSONElement x = it.next();
270
BSONElement y = it.next();
271
*out = coordToPoint(x.number(), y.number());
274
bool GeoParser::parsePolygon(const BSONObj &obj, S2Polygon *out) {
275
if (isGeoJSONPolygon(obj)) {
276
parseGeoJSONPolygon(obj, out);
283
bool GeoParser::isLegacyPoint(const BSONObj &obj) {
284
BSONObjIterator it(obj);
285
if (!it.more()) { return false; }
286
BSONElement x = it.next();
287
if (!x.isNumber()) { return false; }
288
if (!it.more()) { return false; }
289
BSONElement y = it.next();
290
if (!y.isNumber()) { return false; }
291
if (it.more()) { return false; }
295
bool GeoParser::isLegacyPolygon(const BSONObj &obj) {
296
BSONObjIterator typeIt(obj);
297
BSONElement type = typeIt.next();
298
if (!type.isABSONObj()) { return false; }
299
if (!mongoutils::str::equals(type.fieldName(), "$polygon")) { return false; }
300
BSONObjIterator coordIt(type.embeddedObject());
302
while (coordIt.more()) {
303
BSONElement coord = coordIt.next();
304
if (!coord.isABSONObj()) { return false; }
305
if (!isLegacyPoint(coord.Obj())) { return false; }
308
if (vertices < 3) { return false; }
312
bool GeoParser::isPoint(const BSONObj &obj) {
313
return isGeoJSONPoint(obj) || isLegacyPoint(obj);
316
bool GeoParser::isLineString(const BSONObj &obj) {
317
return isGeoJSONLineString(obj);
320
bool GeoParser::isPolygon(const BSONObj &obj) {
321
return isGeoJSONPolygon(obj) || isLegacyPolygon(obj);
324
bool GeoParser::crsIsOK(const BSONObj &obj) {
325
if (!obj.hasField("crs")) { return true; }
327
if (!obj["crs"].isABSONObj()) { return false; }
329
BSONObj crsObj = obj["crs"].embeddedObject();
330
if (!crsObj.hasField("type")) { return false; }
331
if (String != crsObj["type"].type()) { return false; }
332
if ("name" != crsObj["type"].String()) { return false; }
333
if (!crsObj.hasField("properties")) { return false; }
334
if (!crsObj["properties"].isABSONObj()) { return false; }
336
BSONObj propertiesObj = crsObj["properties"].embeddedObject();
337
if (!propertiesObj.hasField("name")) { return false; }
338
if (String != propertiesObj["name"].type()) { return false; }
339
const string& name = propertiesObj["name"].String();
341
// see http://portal.opengeospatial.org/files/?artifact_id=24045
342
// and http://spatialreference.org/ref/epsg/4326/
343
// and http://www.geojson.org/geojson-spec.html#named-crs
344
return ("urn:ogc:def:crs:OGC:1.3:CRS84" == name) || ("EPSG:4326" == name);
347
void GeoParser::parseLegacyPoint(const BSONObj &obj, Point *out) {
348
BSONObjIterator it(obj);
349
BSONElement x = it.next();
350
BSONElement y = it.next();
355
bool GeoParser::isLegacyBox(const BSONObj &obj) {
356
BSONObjIterator typeIt(obj);
357
BSONElement type = typeIt.next();
358
if (!type.isABSONObj()) { return false; }
359
if (!mongoutils::str::equals(type.fieldName(), "$box")) { return false; }
360
BSONObjIterator coordIt(type.embeddedObject());
361
BSONElement minE = coordIt.next();
362
if (!minE.isABSONObj()) { return false; }
363
if (!isLegacyPoint(minE.Obj())) { return false; }
364
if (!coordIt.more()) { return false; }
365
BSONElement maxE = coordIt.next();
366
if (!maxE.isABSONObj()) { return false; }
367
if (!isLegacyPoint(maxE.Obj())) { return false; }
371
void GeoParser::parseLegacyBox(const BSONObj &obj, Box *out) {
372
BSONObjIterator typeIt(obj);
373
BSONElement type = typeIt.next();
374
BSONObjIterator coordIt(type.embeddedObject());
375
BSONElement minE = coordIt.next();
376
BSONElement maxE = coordIt.next();
377
parseLegacyPoint(minE.Obj(), &out->_min);
378
parseLegacyPoint(maxE.Obj(), &out->_max);
381
bool GeoParser::isLegacyCenter(const BSONObj &obj) {
382
BSONObjIterator typeIt(obj);
383
BSONElement type = typeIt.next();
384
if (!type.isABSONObj()) { return false; }
385
bool isCenter = mongoutils::str::equals(type.fieldName(), "$center");
386
if (!isCenter) { return false; }
387
BSONObjIterator objIt(type.embeddedObject());
388
BSONElement center = objIt.next();
389
if (!center.isABSONObj()) { return false; }
390
if (!isLegacyPoint(center.Obj())) { return false; }
391
if (!objIt.more()) { return false; }
392
BSONElement radius = objIt.next();
393
if (!radius.isNumber()) { return false; }
397
void GeoParser::parseLegacyCenter(const BSONObj &obj, Circle *out) {
398
BSONObjIterator typeIt(obj);
399
BSONElement type = typeIt.next();
400
BSONObjIterator objIt(type.embeddedObject());
401
BSONElement center = objIt.next();
402
parseLegacyPoint(center.Obj(), &out->center);
403
BSONElement radius = objIt.next();
404
out->radius = radius.number();
407
bool GeoParser::isLegacyCenterSphere(const BSONObj &obj) {
408
BSONObjIterator typeIt(obj);
409
BSONElement type = typeIt.next();
410
if (!type.isABSONObj()) { return false; }
411
bool isCenterSphere = mongoutils::str::equals(type.fieldName(), "$centerSphere");
412
if (!isCenterSphere) { return false; }
413
BSONObjIterator objIt(type.embeddedObject());
414
BSONElement center = objIt.next();
415
if (!center.isABSONObj()) { return false; }
416
if (!isLegacyPoint(center.Obj())) { return false; }
417
if (!objIt.more()) { return false; }
418
BSONElement radius = objIt.next();
419
if (!radius.isNumber()) { return false; }
423
void GeoParser::parseLegacyCenterSphere(const BSONObj &obj, S2Cap *out) {
424
BSONObjIterator typeIt(obj);
425
BSONElement type = typeIt.next();
426
BSONObjIterator objIt(type.embeddedObject());
427
BSONElement center = objIt.next();
429
parseLegacyPoint(center.Obj(), ¢erPoint);
430
BSONElement radiusElt = objIt.next();
431
double radius = radiusElt.number();
432
*out = S2Cap::FromAxisAngle(centerPoint, S1Angle::Radians(radius));
435
void GeoParser::parseLegacyPolygon(const BSONObj &obj, Polygon *out) {
436
BSONObjIterator typeIt(obj);
437
BSONElement type = typeIt.next();
438
BSONObjIterator coordIt(type.embeddedObject());
439
vector<Point> points;
440
while (coordIt.more()) {
442
parseLegacyPoint(coordIt.next().Obj(), &p);
445
*out = Polygon(points);
448
bool GeoParser::parsePolygon(const BSONObj &obj, Polygon *out) {
449
if (!isLegacyPolygon(obj)) { return false; }
450
parseLegacyPolygon(obj, out);