SERVER-14510 Custom CRS for strict winding order enforcement

Add BigSimplePolygon implementation and unit tests.

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);
+    }
+
+}