summaryrefslogtreecommitdiff
path: root/src/mongo/db/geo/big_polygon_test.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mongo/db/geo/big_polygon_test.cpp')
-rw-r--r--src/mongo/db/geo/big_polygon_test.cpp1010
1 files changed, 491 insertions, 519 deletions
diff --git a/src/mongo/db/geo/big_polygon_test.cpp b/src/mongo/db/geo/big_polygon_test.cpp
index c0c01abdba7..3ac82b03768 100644
--- a/src/mongo/db/geo/big_polygon_test.cpp
+++ b/src/mongo/db/geo/big_polygon_test.cpp
@@ -34,562 +34,534 @@
namespace {
- using namespace mongo;
- using std::unique_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));
+using namespace mongo;
+using std::unique_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;
}
+};
- 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));
- }
+vector<S2Point> pointVec(const PointBuilder& builder) {
+ vector<S2Point> points(builder.points.begin(), builder.points.end());
+ return points;
+}
- 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));
- }
+S2Loop* loop(const PointBuilder& builder) {
+ return new S2Loop(builder.points);
+}
- TEST(BigSimplePolygon, BasicWinding) {
+vector<S2Loop*>* loopVec(const PointBuilder& builder) {
+ static vector<S2Loop*> loops;
+ loops.clear();
+ loops.push_back(loop(builder));
+ return &loops;
+}
- // 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)));
+S2LatLng LatLng(double lat, double lng) {
+ return S2LatLng::FromDegrees(lat, lng);
+}
- // 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)));
+// 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));
+}
- ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI);
- ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
- }
+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, LineRelations) {
+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));
+}
- // A 20x20 square centered at [0,0]
- BigSimplePolygon bigPoly20(loop(points() << LatLng(10.0, 10.0) << LatLng(10.0, -10.0)
+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));
+}
- // 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));
+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();
- // 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));
+ // 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)));
- // 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));
- }
+ ASSERT_FALSE(bigPoly20.Contains(poly10));
+ ASSERT(bigPoly20.Intersects(poly10));
+}
- TEST(BigSimplePolygon, LineRelationsComplement) {
+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));
+}
- // 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();
+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));
+}
- // 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)));
+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)));
- ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
- ASSERT_FALSE(bigPoly20Comp.Contains(line10));
- ASSERT_FALSE(bigPoly20Comp.Intersects(line10));
+ // 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)));
- // 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));
+ ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI);
+ ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
+}
- // 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, 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)));
- TEST(BigSimplePolygon, LineRelationsWinding) {
+ // 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)));
- // 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)));
+ ASSERT_LESS_THAN(bigPoly20.GetArea(), 2 * M_PI);
+ ASSERT(bigPoly20.Contains(line10));
+ ASSERT(bigPoly20.Intersects(line10));
- // 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)));
+ // 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));
- ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
- ASSERT_FALSE(bigPoly20Comp.Contains(line10));
- ASSERT_FALSE(bigPoly20Comp.Intersects(line10));
- }
+ // 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, PolarContains) {
+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();
- // 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)));
+ // 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)));
- // 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_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
+ ASSERT_FALSE(bigPoly20Comp.Contains(line10));
+ ASSERT_FALSE(bigPoly20Comp.Intersects(line10));
- ASSERT_LESS_THAN(bigNorthPoly.GetArea(), 2 * M_PI);
- ASSERT_LESS_THAN(northPoly.GetArea(), bigNorthPoly.GetArea());
- ASSERT(bigNorthPoly.Contains(northPoly));
- ASSERT(bigNorthPoly.Intersects(northPoly));
- }
+ // 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));
- TEST(BigSimplePolygon, PolarContainsWithHoles) {
+ // 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));
+}
- // 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)));
+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)));
- // 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);
+ // 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(northPolyHole.GetArea(), bigNorthPoly.GetArea());
- ASSERT(bigNorthPoly.Contains(northPolyHole));
- ASSERT(bigNorthPoly.Intersects(northPolyHole));
- }
+ ASSERT_GREATER_THAN(bigPoly20Comp.GetArea(), 2 * M_PI);
+ ASSERT_FALSE(bigPoly20Comp.Contains(line10));
+ ASSERT_FALSE(bigPoly20Comp.Intersects(line10));
+}
- TEST(BigSimplePolygon, PolarIntersectsWithHoles) {
+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 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)));
- // 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(bigNorthPoly.GetArea(), 2 * M_PI);
+ ASSERT_LESS_THAN(northPoly.GetArea(), bigNorthPoly.GetArea());
+ ASSERT(bigNorthPoly.Contains(northPoly));
+ ASSERT(bigNorthPoly.Intersects(northPoly));
+}
- ASSERT_LESS_THAN(northPolyHole.GetArea(), bigNorthPoly.GetArea());
- ASSERT_FALSE(bigNorthPoly.Contains(northPolyHole));
- ASSERT(bigNorthPoly.Intersects(northPolyHole));
- }
+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));
+}
- // 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));
- }
+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));
+}
- // 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);
- }
+// 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/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);
- }
+// 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);
+}
}
View Lorry Controller Status