diff options
author | Siyuan Zhou <siyuan.zhou@mongodb.com> | 2014-07-17 14:04:17 -0400 |
---|---|---|
committer | Siyuan Zhou <siyuan.zhou@mongodb.com> | 2014-08-12 17:04:08 -0400 |
commit | 712768556e72d1756995c6a7b020b875fb9d6ea9 (patch) | |
tree | f236788b8109d6becd20fdbac593e8dec18f66e2 | |
parent | 8fab360707f1a88efd821a7b7981ca972a9cad35 (diff) | |
download | mongo-712768556e72d1756995c6a7b020b875fb9d6ea9.tar.gz |
SERVER-14510 Custom CRS for strict winding order enforcement
Add BigSimplePolygon implementation and unit tests.
-rw-r--r-- | src/mongo/db/geo/SConscript | 5 | ||||
-rw-r--r-- | src/mongo/db/geo/big_polygon.cpp | 232 | ||||
-rw-r--r-- | src/mongo/db/geo/big_polygon.h | 122 | ||||
-rw-r--r-- | src/mongo/db/geo/big_polygon_test.cpp | 595 |
4 files changed, 954 insertions, 0 deletions
diff --git a/src/mongo/db/geo/SConscript b/src/mongo/db/geo/SConscript index 888dd3b02f0..4f08472e979 100644 --- a/src/mongo/db/geo/SConscript +++ b/src/mongo/db/geo/SConscript @@ -5,6 +5,7 @@ Import("env") # Core geometry shape libraries env.Library("geometry", [ "hash.cpp", "shapes.cpp", + "big_polygon.cpp", "r2_region_coverer.cpp" ], LIBDEPS = [ "$BUILD_DIR/mongo/bson", "$BUILD_DIR/third_party/s2/s2" ]) @@ -29,3 +30,7 @@ env.CppUnitTest("r2_region_coverer_test", [ "r2_region_coverer_test.cpp" ], "geoparser", "$BUILD_DIR/mongo/db/common" ]) # db/common needed for field parsing +env.CppUnitTest("big_polygon_test", [ "big_polygon_test.cpp" ], + LIBDEPS = [ "geometry", + "$BUILD_DIR/mongo/db/common" ]) # db/common needed for field parsing + diff --git a/src/mongo/db/geo/big_polygon.cpp b/src/mongo/db/geo/big_polygon.cpp new file mode 100644 index 00000000000..2f7c20871c6 --- /dev/null +++ b/src/mongo/db/geo/big_polygon.cpp @@ -0,0 +1,232 @@ +/** + * Copyright (C) 2014 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/>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the GNU Affero General Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/db/geo/big_polygon.h" + +#include <map> + +#include "mongo/base/owned_pointer_vector.h" +#include "mongo/util/assert_util.h" + +namespace mongo { + + using boost::scoped_ptr; + using std::auto_ptr; + using std::vector; + + + BigSimplePolygon::BigSimplePolygon() { + } + + // Caller should ensure loop is valid. + BigSimplePolygon::BigSimplePolygon(S2Loop* loop) : + _loop(loop), _isNormalized(loop->IsNormalized()) { + } + + BigSimplePolygon::~BigSimplePolygon() { + } + + void BigSimplePolygon::Init(S2Loop* loop) { + _loop.reset(loop); + _isNormalized = loop->IsNormalized(); + _borderLine.reset(); + _borderPoly.reset(); + } + + double BigSimplePolygon::GetArea() const { + return _loop->GetArea(); + } + + bool BigSimplePolygon::Contains(const S2Polygon& polygon) const { + const S2Polygon& polyBorder = GetPolygonBorder(); + + if (_isNormalized) { + // Polygon border is the same as the loop + return polyBorder.Contains(&polygon); + } + + // Polygon border is the complement of the loop + // + // Return true iff big polygon's complement (polyBorder) doesn't intersect with polygon. + // We don't guarantee whether the points on border are contained or not. + return !polyBorder.Intersects(&polygon); + } + + bool BigSimplePolygon::Contains(const S2Polyline& line) const { + // + // A line is contained within a loop if the result of subtracting the loop from the line is + // nothing. + // + // Also, a line is contained within a loop if the result of clipping the line to the + // complement of the loop is nothing. + // + // If we can't subtract the loop itself using S2, we clip (intersect) to the inverse. Every + // point in S2 is contained in exactly one of these loops. + // + // TODO: Polygon borders are actually kind of weird, and this is somewhat inconsistent with + // Intersects(). A point might Intersect() a boundary exactly, but not be Contain()ed + // within the Polygon. Think the right thing to do here is custom intersection functions. + // + const S2Polygon& polyBorder = GetPolygonBorder(); + + OwnedPointerVector<S2Polyline> clippedOwned; + vector<S2Polyline*>& clipped = clippedOwned.mutableVector(); + + if (_isNormalized) { + // Polygon border is the same as the loop + polyBorder.SubtractFromPolyline(&line, &clipped); + return clipped.size() == 0; + } + else { + // Polygon border is the complement of the loop + polyBorder.IntersectWithPolyline(&line, &clipped); + return clipped.size() == 0; + } + } + + bool BigSimplePolygon::Contains(S2Point const& point) const { + return _loop->Contains(point); + } + + bool BigSimplePolygon::Intersects(const S2Polygon& polygon) const { + // If the loop area is at most 2*Pi, treat it as a simple Polygon. + if (_isNormalized) { + const S2Polygon& polyBorder = GetPolygonBorder(); + return polyBorder.Intersects(&polygon); + } + + // The loop area is greater than 2*Pi, so it intersects a polygon (even with holes) if it + // intersects any of the top-level polygon loops, since any valid polygon is less than + // a hemisphere. + // + // Intersecting a polygon hole requires that the loop must have intersected the containing + // loop - topology ftw. + // + // Another approach is to check polyBorder doesn't contain polygon, but the following + // approach is cheaper. + + // Iterate over all the top-level polygon loops + for (int i = 0; i < polygon.num_loops(); i = polygon.GetLastDescendant(i) + 1) { + const S2Loop* polyLoop = polygon.loop(i); + if (_loop->Intersects(polyLoop)) + return true; + } + + return false; + } + + bool BigSimplePolygon::Intersects(const S2Polyline& line) const { + // + // A loop intersects a line if line intersects the loop border or, if it doesn't, either + // line is contained in the loop, or line is disjoint with the loop. So checking any + // vertex of the line is sufficient. + // + // TODO: Make a general Polygon/Line relation tester which uses S2 primitives + // + return GetLineBorder().Intersects(&line) || _loop->Contains(line.vertex(0)); + } + + bool BigSimplePolygon::Intersects(S2Point const& point) const { + return Contains(point); + } + + void BigSimplePolygon::Invert() { + _loop->Invert(); + _isNormalized = _loop->IsNormalized(); + } + + const S2Polygon& BigSimplePolygon::GetPolygonBorder() const { + if (_borderPoly) + return *_borderPoly; + + auto_ptr<S2Loop> cloned(_loop->Clone()); + + // Any loop in polygon should be than a hemisphere (2*Pi). + cloned->Normalize(); + + OwnedPointerVector<S2Loop> loops; + loops.mutableVector().push_back(cloned.release()); + _borderPoly.reset(new S2Polygon(&loops.mutableVector())); + return *_borderPoly; + } + + const S2Polyline& BigSimplePolygon::GetLineBorder() const { + if (_borderLine) + return *_borderLine; + + vector<S2Point> points; + int numVertices = _loop->num_vertices(); + for (int i = 0; i <= numVertices; ++i) { + // vertex() maps "numVertices" to 0 internally, so we don't have to deal with + // the index out of range. + points.push_back(_loop->vertex(i)); + } + + _borderLine.reset(new S2Polyline(points)); + + return *_borderLine; + } + + BigSimplePolygon* BigSimplePolygon::Clone() const { + return new BigSimplePolygon(_loop->Clone()); + } + + S2Cap BigSimplePolygon::GetCapBound() const { + return _loop->GetCapBound(); + } + + S2LatLngRect BigSimplePolygon::GetRectBound() const { + return _loop->GetRectBound(); + } + + bool BigSimplePolygon::Contains(const S2Cell& cell) const { + return _loop->Contains(cell); + } + + bool BigSimplePolygon::MayIntersect(const S2Cell& cell) const { + return _loop->MayIntersect(cell); + } + + bool BigSimplePolygon::VirtualContainsPoint(const S2Point& p) const { + return _loop->VirtualContainsPoint(p); + } + + void BigSimplePolygon::Encode(Encoder* const encoder) const { + invariant(false); + } + + bool BigSimplePolygon::Decode(Decoder* const decoder) { + invariant(false); + } + + bool BigSimplePolygon::DecodeWithinScope(Decoder* const decoder) { + invariant(false); + } + +} + diff --git a/src/mongo/db/geo/big_polygon.h b/src/mongo/db/geo/big_polygon.h new file mode 100644 index 00000000000..7125da35f35 --- /dev/null +++ b/src/mongo/db/geo/big_polygon.h @@ -0,0 +1,122 @@ +/** + * Copyright (C) 2014 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/>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the GNU Affero General Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#pragma once + +#include <boost/scoped_ptr.hpp> +#include <vector> + +#include "mongo/db/geo/s2.h" +#include "third_party/s2/s2cap.h" +#include "third_party/s2/s2cell.h" +#include "third_party/s2/s2loop.h" +#include "third_party/s2/s2polygon.h" +#include "third_party/s2/s2polyline.h" +#include "third_party/s2/s2region.h" + +namespace mongo { + + // Simple GeoJSON polygon with a custom CRS identifier as having a strict winding order. + // The winding order will determine unambiguously the inside/outside of the polygon even + // if larger than one hemisphere. + // + // BigSimplePolygon uses S2Loop internally, which follows a left-foot rule (inside to the + // left when walking the edge of the polygon, counter-clockwise) + class BigSimplePolygon : public S2Region { + public: + + BigSimplePolygon(); + + BigSimplePolygon(S2Loop* loop); + + virtual ~BigSimplePolygon(); + + void Init(S2Loop* loop); + + double GetArea() const; + + bool Contains(const S2Polygon& polygon) const; + + bool Contains(const S2Polyline& line) const; + + // Needs to be this way for S2 compatibility + bool Contains(S2Point const& point) const; + + bool Intersects(const S2Polygon& polygon) const; + + bool Intersects(const S2Polyline& line) const; + + bool Intersects(S2Point const& point) const; + + // Only used in tests + void Invert(); + + const S2Polygon& GetPolygonBorder() const; + + const S2Polyline& GetLineBorder() const; + + // + // S2Region interface + // + + BigSimplePolygon* Clone() const; + + S2Cap GetCapBound() const; + + S2LatLngRect GetRectBound() const; + + bool Contains(S2Cell const& cell) const; + + bool MayIntersect(S2Cell const& cell) const; + + bool VirtualContainsPoint(S2Point const& p) const; + + void Encode(Encoder* const encoder) const; + + bool Decode(Decoder* const decoder); + + bool DecodeWithinScope(Decoder* const decoder); + + private: + + boost::scoped_ptr<S2Loop> _loop; + + // Cache whether the loop area is at most 2*Pi (the area of hemisphere). + // + // S2 guarantees that any loop in a valid (normalized) polygon, no matter a hole + // or a shell, has to be less than 2*Pi. So if the loop is normalized, it's the same + // with the border polygon, otherwise, the border polygon is its complement. + bool _isNormalized; + + // Cached to do Intersects() and Contains() with S2Polylines. + mutable boost::scoped_ptr<S2Polyline> _borderLine; + mutable boost::scoped_ptr<S2Polygon> _borderPoly; + }; + +} + diff --git a/src/mongo/db/geo/big_polygon_test.cpp b/src/mongo/db/geo/big_polygon_test.cpp new file mode 100644 index 00000000000..a8cde9bc909 --- /dev/null +++ b/src/mongo/db/geo/big_polygon_test.cpp @@ -0,0 +1,595 @@ +/** + * Copyright (C) 2014 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/>. + * + * As a special exception, the copyright holders give permission to link the + * code of portions of this program with the OpenSSL library under certain + * conditions as described in each individual source file and distribute + * linked combinations including the program with the OpenSSL library. You + * must comply with the GNU Affero General Public License in all respects for + * all of the code used other than as permitted herein. If you modify file(s) + * with this exception, you may extend this exception to your version of the + * file(s), but you are not obligated to do so. If you do not wish to do so, + * delete this exception statement from your version. If you delete this + * exception statement from all source files in the program, then also delete + * it in the license file. + */ + +#include "mongo/db/geo/big_polygon.h" + +#include "mongo/bson/util/builder.h" +#include "mongo/bson/bsonobjbuilder.h" +#include "mongo/unittest/unittest.h" + +namespace { + + using namespace mongo; + using std::auto_ptr; + using std::string; + using std::vector; + + // Helper to build a vector of S2Point + struct PointBuilder { + + vector<S2Point> points; + + PointBuilder& operator<<(const S2LatLng& LatLng) { + points.push_back(LatLng.ToPoint()); + return *this; + } + }; + + vector<S2Point> pointVec(const PointBuilder& builder) { + vector<S2Point> points(builder.points.begin(), builder.points.end()); + return points; + } + + S2Loop* loop(const PointBuilder& builder) { + return new S2Loop(builder.points); + } + + vector<S2Loop*>* loopVec(const PointBuilder& builder) { + static vector<S2Loop*> loops; + loops.clear(); + loops.push_back(loop(builder)); + return &loops; + } + + S2LatLng LatLng(double lat, double lng) { + return S2LatLng::FromDegrees(lat, lng); + } + + // Syntax sugar for PointBuilder, which can be used to construct + // - vector<S2Point> pointVec() + // - S2Loop* loop() + // - vector<S2Loop*>* loopVec() + // + // e.g. points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) << LatLng(0.0, 0.0)) + typedef PointBuilder points; + + TEST(BigSimplePolygon, Basic) { + + // A 20x20 square centered at [0,0] + BigSimplePolygon bigPoly20(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + + // A 10x10 square centered at [0,0] + S2Polygon poly10(loopVec(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + + ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI); + ASSERT_LESS_THAN(poly10.GetArea(), bigPoly20.GetArea()); + ASSERT(bigPoly20.Contains(poly10)); + ASSERT(bigPoly20.Intersects(poly10)); + + // A 20x20 square centered at [0,20] + BigSimplePolygon bigPoly20Offset(loop(points() << LatLng(10.0, 30.0) << LatLng(10.0, 10.0) + << LatLng(-10.0, 10.0) << LatLng(-10.0, 30.0))); + + ASSERT_LESS_THAN(bigPoly20Offset.GetArea(), 2 * M_PI); + ASSERT_LESS_THAN(poly10.GetArea(), bigPoly20Offset.GetArea()); + ASSERT_FALSE(bigPoly20Offset.Contains(poly10)); + ASSERT_FALSE(bigPoly20Offset.Intersects(poly10)); + } + + TEST(BigSimplePolygon, BasicWithHole) { + // A 30x30 square centered at [0,0] with a 20X20 hole + vector<S2Loop*> loops; + loops.push_back(loop(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + loops.push_back(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + + S2Polygon holePoly(&loops); + + // A 16X16 square centered at [0,0] + BigSimplePolygon bigPoly16(loop(points() << LatLng(8.0, 8.0) << LatLng(8.0, -8.0) + << LatLng(-8.0, -8.0) << LatLng(-8.0, 8.0))); + + ASSERT_LESS_THAN(bigPoly16.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly16.Contains(holePoly)); + ASSERT_FALSE(bigPoly16.Intersects(holePoly)); + + // A big polygon bigger than the hole. + BigSimplePolygon bigPoly24(loop(points() << LatLng(12.0, 12.0) << LatLng(12.0, -12.0) + << LatLng(-12.0, -12.0) << LatLng(-12.0, 12.0))); + ASSERT_LESS_THAN(bigPoly24.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly24.Contains(holePoly)); + ASSERT_TRUE(bigPoly24.Intersects(holePoly)); + } + + TEST(BigSimplePolygon, BasicWithHoleAndShell) { + // A 30x30 square centered at [0,0] with a 20X20 hole and 10X10 shell + vector<S2Loop*> loops; + // Border + loops.push_back(loop(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + // Hole + loops.push_back(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + // Shell + loops.push_back(loop(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + S2Polygon shellPoly(&loops); + + // A 16X16 square centered at [0,0] containing the shell + BigSimplePolygon bigPoly16(loop(points() << LatLng(8.0, 8.0) << LatLng(8.0, -8.0) + << LatLng(-8.0, -8.0) << LatLng(-8.0, 8.0))); + ASSERT_LESS_THAN(bigPoly16.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly16.Contains(shellPoly)); + ASSERT_TRUE(bigPoly16.Intersects(shellPoly)); + + // Try a big polygon bigger than the hole. + BigSimplePolygon bigPoly24(loop(points() << LatLng(12.0, 12.0) << LatLng(12.0, -12.0) + << LatLng(-12.0, -12.0) << LatLng(-12.0, 12.0))); + ASSERT_LESS_THAN(bigPoly24.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly24.Contains(shellPoly)); + ASSERT_TRUE(bigPoly24.Intersects(shellPoly)); + + // Try a big polygon smaller than the shell. + BigSimplePolygon bigPoly8(loop(points() << LatLng(4.0, 4.0) << LatLng(4.0, -4.0) + << LatLng(-4.0, -4.0) << LatLng(-4.0, 4.0))); + ASSERT_LESS_THAN(bigPoly8.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly8.Contains(shellPoly)); + ASSERT_TRUE(bigPoly8.Intersects(shellPoly)); + } + + TEST(BigSimplePolygon, BasicComplement) { + + // Everything *not* in a 20x20 square centered at [0,0] + BigSimplePolygon bigPoly20Comp(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) + << LatLng(-10.0, 10.0))); + bigPoly20Comp.Invert(); + + // A 10x10 square centered at [0,0] + S2Polygon poly10(loopVec(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + + ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly20Comp.Contains(poly10)); + ASSERT_FALSE(bigPoly20Comp.Intersects(poly10)); + + // A 10x10 square centered at [0,20], contained by bigPoly20Comp + S2Polygon poly10Contained(loopVec(points() << LatLng(25.0, 25.0) << LatLng(25.0, 15.0) + << LatLng(15.0, 15.0) << LatLng(15.0, 25.0))); + + ASSERT_LESS_THAN(poly10Contained.GetArea(), bigPoly20Comp.GetArea()); + ASSERT(bigPoly20Comp.Contains(poly10Contained)); + ASSERT(bigPoly20Comp.Intersects(poly10Contained)); + + // A 30x30 square centered at [0,0], so that bigPoly20Comp contains its complement entirely, + // which is not allowed by S2. + S2Polygon poly30(loopVec(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + ASSERT_LESS_THAN(poly30.GetArea(), bigPoly20Comp.GetArea()); + ASSERT_FALSE(bigPoly20Comp.Contains(poly30)); + ASSERT_TRUE(bigPoly20Comp.Intersects(poly30)); + } + + TEST(BigSimplePolygon, BasicIntersects) { + + // Everything *not* in a 20x20 square centered at [0,0] + BigSimplePolygon bigPoly20(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + bigPoly20.Invert(); + + // A 10x10 square centered at [10,10] (partial overlap) + S2Polygon poly10(loopVec(points() << LatLng(15.0, 15.0) << LatLng(15.0, 5.0) + << LatLng(5.0, 5.0) << LatLng(5.0, 15.0))); + + ASSERT_FALSE(bigPoly20.Contains(poly10)); + ASSERT(bigPoly20.Intersects(poly10)); + } + + TEST(BigSimplePolygon, BasicComplementWithHole) { + // A 30x30 square centered at [0,0] with a 20X20 hole + vector<S2Loop*> loops; + loops.push_back(loop(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + loops.push_back(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + + S2Polygon holePoly(&loops); + + // 1. BigPolygon doesn't touch holePoly + // Everything *not* in a 40x40 square centered at [0,0] + BigSimplePolygon bigPoly40Comp(loop(points() << LatLng(20.0, 20.0) << LatLng(20.0, -20.0) + << LatLng(-20.0, -20.0) + << LatLng(-20.0, 20.0))); + bigPoly40Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly40Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly40Comp.Contains(holePoly)); + ASSERT_FALSE(bigPoly40Comp.Intersects(holePoly)); + + // 2. BigPolygon intersects holePoly + // Everything *not* in a 24X24 square centered at [0,0] + BigSimplePolygon bigPoly24Comp(loop(points() << LatLng(12.0, 12.0) << LatLng(12.0, -12.0) + << LatLng(-12.0, -12.0) + << LatLng(-12.0, 12.0))); + bigPoly24Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly24Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly24Comp.Contains(holePoly)); + ASSERT_TRUE(bigPoly24Comp.Intersects(holePoly)); + + // 3. BigPolygon contains holePoly + // Everything *not* in a 16X16 square centered at [0,0] + BigSimplePolygon bigPoly16Comp(loop(points() << LatLng(8.0, 8.0) << LatLng(8.0, -8.0) + << LatLng(-8.0, -8.0) + << LatLng(-8.0, 8.0))); + bigPoly16Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly16Comp.GetArea(), 2 * M_PI); + ASSERT_TRUE(bigPoly16Comp.Contains(holePoly)); + ASSERT_TRUE(bigPoly16Comp.Intersects(holePoly)); + + // 4. BigPolygon contains the right half of holePoly + // Everything *not* in a 40x40 square centered at [0,20] + BigSimplePolygon bigPoly40CompOffset(loop(points() << LatLng(20.0, 40.0) + << LatLng(20.0, 0.0) + << LatLng(-20.0, 0.0) + << LatLng(-20.0, 40.0))); + bigPoly40CompOffset.Invert(); + ASSERT_GREATER_THAN(bigPoly40CompOffset.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly40CompOffset.Contains(holePoly)); + ASSERT_TRUE(bigPoly40CompOffset.Intersects(holePoly)); + } + + TEST(BigSimplePolygon, BasicComplementWithHoleAndShell) { + // A 30x30 square centered at [0,0] with a 20X20 hole and 10X10 shell + vector<S2Loop*> loops; + // Border + loops.push_back(loop(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + // Hole + loops.push_back(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + // Shell + loops.push_back(loop(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + S2Polygon shellPoly(&loops); + + // 1. BigPolygon doesn't touch shellPoly + // Everything *not* in a 40x40 square centered at [0,0] + BigSimplePolygon bigPoly40Comp(loop(points() << LatLng(20.0, 20.0) << LatLng(20.0, -20.0) + << LatLng(-20.0, -20.0) + << LatLng(-20.0, 20.0))); + bigPoly40Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly40Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly40Comp.Contains(shellPoly)); + ASSERT_FALSE(bigPoly40Comp.Intersects(shellPoly)); + + // 2. BigPolygon intersects shellPoly + // Everything *not* in a 24X24 square centered at [0,0] + BigSimplePolygon bigPoly24Comp(loop(points() << LatLng(12.0, 12.0) << LatLng(12.0, -12.0) + << LatLng(-12.0, -12.0) + << LatLng(-12.0, 12.0))); + bigPoly24Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly24Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly24Comp.Contains(shellPoly)); + ASSERT_TRUE(bigPoly24Comp.Intersects(shellPoly)); + + // 3. BigPolygon contains shellPoly's outer ring + // Everything *not* in a 16X16 square centered at [0,0] + BigSimplePolygon bigPoly16Comp(loop(points() << LatLng(8.0, 8.0) << LatLng(8.0, -8.0) + << LatLng(-8.0, -8.0) + << LatLng(-8.0, 8.0))); + bigPoly16Comp.Invert(); + ASSERT_GREATER_THAN(bigPoly16Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly16Comp.Contains(shellPoly)); + ASSERT_TRUE(bigPoly16Comp.Intersects(shellPoly)); + + // 4. BigPolygon contains the right half of shellPoly + // Everything *not* in a 40x40 square centered at [0,20] + BigSimplePolygon bigPoly40CompOffset(loop(points() << LatLng(20.0, 40.0) + << LatLng(20.0, 0.0) + << LatLng(-20.0, 0.0) + << LatLng(-20.0, 40.0))); + bigPoly40CompOffset.Invert(); + ASSERT_GREATER_THAN(bigPoly40CompOffset.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly40CompOffset.Contains(shellPoly)); + ASSERT_TRUE(bigPoly40CompOffset.Intersects(shellPoly)); + + // 5. BigPolygon contain shellPoly (CW) + BigSimplePolygon bigPolyCompOffset(loop(points() << LatLng(6.0, 6.0) + << LatLng(6.0, 8.0) + << LatLng(-6.0, 8.0) + << LatLng(-6.0, 6.0))); + ASSERT_GREATER_THAN(bigPolyCompOffset.GetArea(), 2 * M_PI); + ASSERT_TRUE(bigPolyCompOffset.Contains(shellPoly)); + ASSERT_TRUE(bigPolyCompOffset.Intersects(shellPoly)); + } + + TEST(BigSimplePolygon, BasicWinding) { + + // A 20x20 square centered at [0,0] (CCW) + BigSimplePolygon bigPoly20(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + + // Everything *not* in a 20x20 square centered at [0,0] (CW) + BigSimplePolygon bigPoly20Comp(loop(points() << LatLng(10.0, 10.0) << LatLng(-10.0, 10.0) + << LatLng(-10.0, -10.0) + << LatLng(10.0, -10.0))); + + ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI); + ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI); + } + + TEST(BigSimplePolygon, LineRelations) { + + // A 20x20 square centered at [0,0] + BigSimplePolygon bigPoly20(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) << LatLng(-10.0, 10.0))); + + // A 10x10 line circling [0,0] + S2Polyline line10(pointVec(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + + ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI); + ASSERT(bigPoly20.Contains(line10)); + ASSERT(bigPoly20.Intersects(line10)); + + // Line segment disjoint from big polygon + S2Polyline lineDisjoint(pointVec(points() << LatLng(15.0, 5.0) << LatLng(15.0, -5.0))); + ASSERT_FALSE(bigPoly20.Contains(lineDisjoint)); + ASSERT_FALSE(bigPoly20.Intersects(lineDisjoint)); + + // Line segment intersects big polygon + S2Polyline lineIntersect(pointVec(points() << LatLng(0.0, 0.0) << LatLng(15.0, 0.0))); + ASSERT_FALSE(bigPoly20.Contains(lineIntersect)); + ASSERT_TRUE(bigPoly20.Intersects(lineIntersect)); + } + + TEST(BigSimplePolygon, LineRelationsComplement) { + + // A 20x20 square centered at [0,0] + BigSimplePolygon bigPoly20Comp(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0) + << LatLng(-10.0, -10.0) + << LatLng(-10.0, 10.0))); + bigPoly20Comp.Invert(); + + // A 10x10 line circling [0,0] + S2Polyline line10(pointVec(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + + ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly20Comp.Contains(line10)); + ASSERT_FALSE(bigPoly20Comp.Intersects(line10)); + + // Line segment (0, 0) -> (0, 15) + S2Polyline lineIntersect(pointVec(points() << LatLng(0.0, 0.0) << LatLng(0.0, 15.0))); + ASSERT_FALSE(bigPoly20Comp.Contains(lineIntersect)); + ASSERT_TRUE(bigPoly20Comp.Intersects(lineIntersect)); + + // A 10x10 line circling [0,0] + S2Polyline line30(pointVec(points() << LatLng(15.0, 15.0) << LatLng(15.0, -15.0) + << LatLng(-15.0, -15.0) << LatLng(-15.0, 15.0))); + ASSERT_TRUE(bigPoly20Comp.Contains(line30)); + ASSERT_TRUE(bigPoly20Comp.Intersects(line30)); + } + + TEST(BigSimplePolygon, LineRelationsWinding) { + + // Everything *not* in a 20x20 square centered at [0,0] (CW winding) + BigSimplePolygon bigPoly20Comp(loop(points() << LatLng(10.0, 10.0) << LatLng(-10.0, 10.0) + << LatLng(-10.0, -10.0) + << LatLng(10.0, -10.0))); + + // A 10x10 line circling [0,0] + S2Polyline line10(pointVec(points() << LatLng(5.0, 5.0) << LatLng(5.0, -5.0) + << LatLng(-5.0, -5.0) << LatLng(-5.0, 5.0))); + + ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI); + ASSERT_FALSE(bigPoly20Comp.Contains(line10)); + ASSERT_FALSE(bigPoly20Comp.Intersects(line10)); + } + + TEST(BigSimplePolygon, PolarContains) { + + // Square 10 degrees from the north pole [90,0] + BigSimplePolygon bigNorthPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(80.0, 90.0) + << LatLng(80.0, 180.0) << LatLng(80.0, -90.0))); + + // Square 5 degrees from the north pole [90, 0] + S2Polygon northPoly(loopVec(points() << LatLng(85.0, 0.0) << LatLng(85.0, 90.0) + << LatLng(85.0, 180.0) << LatLng(85.0, -90.0))); + + ASSERT_LESS_THAN(bigNorthPoly.GetArea(), 2 * M_PI); + ASSERT_LESS_THAN(northPoly.GetArea(), bigNorthPoly.GetArea()); + ASSERT(bigNorthPoly.Contains(northPoly)); + ASSERT(bigNorthPoly.Intersects(northPoly)); + } + + TEST(BigSimplePolygon, PolarContainsWithHoles) { + + // Square 10 degrees from the north pole [90,0] + BigSimplePolygon bigNorthPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(80.0, 90.0) + << LatLng(80.0, 180.0) << LatLng(80.0, -90.0))); + + // Square 5 degrees from the north pole [90, 0] with a concentric hole 1 degree from the + // north pole + vector<S2Loop*> loops; + loops.push_back(loop(points() << LatLng(85.0, 0.0) << LatLng(85.0, 90.0) + << LatLng(85.0, 180.0) << LatLng(85.0, -90.0))); + loops.push_back(loop(points() << LatLng(89.0, 0.0) << LatLng(89.0, 90.0) + << LatLng(89.0, 180.0) << LatLng(89.0, -90.0))); + S2Polygon northPolyHole(&loops); + + ASSERT_LESS_THAN(northPolyHole.GetArea(), bigNorthPoly.GetArea()); + ASSERT(bigNorthPoly.Contains(northPolyHole)); + ASSERT(bigNorthPoly.Intersects(northPolyHole)); + } + + TEST(BigSimplePolygon, PolarIntersectsWithHoles) { + + // Square 10 degrees from the north pole [90,0] + BigSimplePolygon bigNorthPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(80.0, 90.0) + << LatLng(80.0, 180.0) << LatLng(80.0, -90.0))); + + // 5-degree square with 1-degree-wide concentric hole, centered on [80.0, 0.0] + vector<S2Loop*> loops; + loops.push_back(loop(points() << LatLng(85.0, 5.0) << LatLng(85.0, -5.0) + << LatLng(75.0, -5.0) << LatLng(75.0, 5.0))); + loops.push_back(loop(points() << LatLng(81.0, 1.0) << LatLng(81.0, -1.0) + << LatLng(79.0, -1.0) << LatLng(79.0, 1.0))); + S2Polygon northPolyHole(&loops); + + ASSERT_LESS_THAN(northPolyHole.GetArea(), bigNorthPoly.GetArea()); + ASSERT_FALSE(bigNorthPoly.Contains(northPolyHole)); + ASSERT(bigNorthPoly.Intersects(northPolyHole)); + } + + // Edge cases + // + // No promise in terms of points on border - they may be inside or outside the big polygon. + // But we need to ensure the result is consistent: + // 1. If a polygon/line is contained by a big polygon, they must intersect with each other. + // 2. Relation doesn't change as long as the touch point doesn't change, no matter the big + // polygon is larger or less then a hemisphere. + // 3. Relations for big polygons less than a hemisphere are consistent with ordinary (simple) + // polygon results. + + template <typename TShape> + void checkConsistency(const BigSimplePolygon& bigPoly, + const BigSimplePolygon& expandedBigPoly, + const TShape& shape) { + // Contain() => Intersects() + if (bigPoly.Contains(shape)) ASSERT(bigPoly.Intersects(shape)); + if (expandedBigPoly.Contains(shape)) ASSERT(expandedBigPoly.Intersects(shape)); + // Relation doesn't change + ASSERT_EQUALS(bigPoly.Contains(shape), expandedBigPoly.Contains(shape)); + ASSERT_EQUALS(bigPoly.Intersects(shape), expandedBigPoly.Intersects(shape)); + } + + // Polygon shares big polygon's edge (disjoint) + TEST(BigSimplePolygon, ShareEdgeDisjoint) { + // Big polygon smaller than a hemisphere. + BigSimplePolygon bigPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, 90.0) << LatLng(80.0, 90.0))); + ASSERT_LESS_THAN(bigPoly.GetArea(), 2 * M_PI); + + // Vertex point and collinear point + S2Point point = LatLng(80.0, 0.0).ToPoint(); + S2Point collinearPoint = LatLng(0.0, 0.0).ToPoint(); + + // Polygon shares one edge + S2Polygon poly(loopVec(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, -10.0) << LatLng(80.0, -10.0))); + // Polygon shares a segment of one edge + S2Polygon collinearPoly(loopVec(points() << LatLng(50.0, 0.0) << LatLng(-50.0, 0.0) + << LatLng(-50.0, -10.0) << LatLng(50.0, -10.0))); + + // Line + S2Polyline line(pointVec(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, -10.0))); + // Line share a segment of one edge + S2Polyline collinearLine(pointVec(points() << LatLng(50.0, 0.0) << LatLng(-50.0, 0.0) + << LatLng(-50.0, -10.0))); + + // Big polygon larger than a hemisphere. + BigSimplePolygon expandedBigPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, 90.0) + << LatLng(-80.0, 180.0) + << LatLng(-80.0, -90.0) + << LatLng(80.0, -90.0) << LatLng(80.0, 180.0) + << LatLng(80.0, 90.0))); + ASSERT_GREATER_THAN(expandedBigPoly.GetArea(), 2 * M_PI); + + checkConsistency(bigPoly, expandedBigPoly, point); + checkConsistency(bigPoly, expandedBigPoly, collinearPoint); + checkConsistency(bigPoly, expandedBigPoly, poly); + checkConsistency(bigPoly, expandedBigPoly, collinearPoly); + checkConsistency(bigPoly, expandedBigPoly, line); + checkConsistency(bigPoly, expandedBigPoly, collinearLine); + + // Check the complement of big polygon + bigPoly.Invert(); + ASSERT_GREATER_THAN(bigPoly.GetArea(), 2 * M_PI); + expandedBigPoly.Invert(); + ASSERT_LESS_THAN(expandedBigPoly.GetArea(), 2 * M_PI); + + checkConsistency(bigPoly, expandedBigPoly, point); + checkConsistency(bigPoly, expandedBigPoly, collinearPoint); + checkConsistency(bigPoly, expandedBigPoly, poly); + checkConsistency(bigPoly, expandedBigPoly, collinearPoly); + checkConsistency(bigPoly, expandedBigPoly, line); + checkConsistency(bigPoly, expandedBigPoly, collinearLine); + } + + // Polygon/line shares big polygon's edge (contained by big polygon) + TEST(BigSimplePolygon, ShareEdgeContained) { + // Big polygon smaller than a hemisphere. + BigSimplePolygon bigPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, 90.0) << LatLng(80.0, 90.0))); + ASSERT_LESS_THAN(bigPoly.GetArea(), 2 * M_PI); + + // Polygon + S2Polygon poly(loopVec(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, 10.0) << LatLng(80.0, 10.0))); + // Polygon shares a segment of one edge + S2Polygon collinearPoly(loopVec(points() << LatLng(50.0, 0.0) << LatLng(-50.0, 0.0) + << LatLng(-50.0, 10.0) << LatLng(50.0, 10.0))); + // Line + S2Polyline line(pointVec(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(0.0, 10.0))); + // Line shares a segment of one edge + S2Polyline collinearLine(pointVec(points() << LatLng(50.0, 0.0) << LatLng(-50.0, 0.0) + << LatLng(-50.0, 10.0))); + + // Big polygon larger than a hemisphere. + BigSimplePolygon expandedBigPoly(loop(points() << LatLng(80.0, 0.0) << LatLng(-80.0, 0.0) + << LatLng(-80.0, 90.0) + << LatLng(-80.0, 180.0) + << LatLng(-80.0, -90.0) + << LatLng(80.0, -90.0) << LatLng(80.0, 180.0) + << LatLng(80.0, 90.0))); + ASSERT_GREATER_THAN(expandedBigPoly.GetArea(), 2 * M_PI); + + checkConsistency(bigPoly, expandedBigPoly, poly); + checkConsistency(bigPoly, expandedBigPoly, collinearPoly); + checkConsistency(bigPoly, expandedBigPoly, line); + checkConsistency(bigPoly, expandedBigPoly, collinearLine); + + // Check the complement of big polygon + bigPoly.Invert(); + ASSERT_GREATER_THAN(bigPoly.GetArea(), 2 * M_PI); + expandedBigPoly.Invert(); + ASSERT_LESS_THAN(expandedBigPoly.GetArea(), 2 * M_PI); + + checkConsistency(bigPoly, expandedBigPoly, poly); + checkConsistency(bigPoly, expandedBigPoly, collinearPoly); + checkConsistency(bigPoly, expandedBigPoly, line); + checkConsistency(bigPoly, expandedBigPoly, collinearLine); + } + +} |