SERVER-9986 refactor near search for 2D and S2

Adds progressive search functionality for $geoNear operations,
allowing better integration with other cursors.

1 files changed, 44 insertions, 13 deletions

diff --git a/src/mongo/db/geo/shapes.cpp b/src/mongo/db/geo/shapes.cpp
index 95796025590..9c1e5b80745 100644
--- a/src/mongo/db/geo/shapes.cpp
+++ b/src/mongo/db/geo/shapes.cpp
@@ -26,9 +26,7 @@
 *    it in the license file.
 */
 
-#include "mongo/pch.h"
 #include "mongo/db/jsobj.h"
-#include "mongo/db/geo/core.h"
 #include "mongo/db/geo/shapes.h"
 #include "mongo/util/mongoutils/str.h"
 
@@ -444,12 +442,37 @@ namespace mongo {
 
     bool R2Annulus::fastDisjoint(const Box& other) const {
         return !circleIntersectsWithBox(Circle(_outer, _center), other)
-            || circleInteriorContainsBox(Circle(_inner, _center), other);
+               || circleInteriorContainsBox(Circle(_inner, _center), other);
     }
 
+    string R2Annulus::toString() const {
+        return str::stream() << "center: " << _center.toString() << " inner: " << _inner
+                             << " outer: " << _outer;
+    }
 
     /////// Other methods
 
+    double S2Distance::distanceRad(const S2Point& pointA, const S2Point& pointB) {
+        S1Angle angle(pointA, pointB);
+        return angle.radians();
+    }
+
+    double S2Distance::minDistanceRad(const S2Point& point, const S2Polyline& line) {
+        int tmp;
+        S1Angle angle(point, line.Project(point, &tmp));
+        return angle.radians();
+    }
+
+    double S2Distance::minDistanceRad(const S2Point& point, const S2Polygon& polygon) {
+        S1Angle angle(point, polygon.Project(point));
+        return angle.radians();
+    }
+
+    double S2Distance::minDistanceRad(const S2Point& point, const S2Cap& cap) {
+        S1Angle angleToCenter(point, cap.axis());
+        return (angleToCenter - cap.angle()).radians();
+    }
+
     /**
      * Distance method that compares x or y coords when other direction is zero,
      * avoids numerical error when distances are very close to radius but axis-aligned.
@@ -506,16 +529,6 @@ namespace mongo {
         return sqrt((a * a) + (b * b)) - radius;
     }
 
-    // Technically lat/long bounds, not really tied to earth radius.
-    void checkEarthBounds(const Point &p) {
-        uassert(14808, str::stream() << "point " << p.toString()
-                                     << " must be in earth-like bounds of long "
-                                     << ": [-180, 180], lat : [-90, 90] ",
-                p.x >= -180 && p.x <= 180 && p.y >= -90 && p.y <= 90);
-    }
-
-
-    // WARNING: x and y MUST be longitude and latitude in that order
     // note: multiply by earth radius for distance
     double spheredist_rad(const Point& p1, const Point& p2) {
         // this uses the n-vector formula: http://en.wikipedia.org/wiki/N-vector
@@ -549,6 +562,14 @@ namespace mongo {
                               Point(deg2rad(p2.x), deg2rad(p2.y)));
     }
 
+    // Technically lat/long bounds, not really tied to earth radius.
+    void checkEarthBounds(const Point &p) {
+        uassert(14808, str::stream() << "point " << p.toString()
+                                     << " must be in earth-like bounds of long "
+                                     << ": [-180, 180], lat : [-90, 90] ",
+                p.x >= -180 && p.x <= 180 && p.y >= -90 && p.y <= 90);
+    }
+
     double distance(const Point& p1, const Point &p2) {
         double a = p1.x - p2.x;
         double b = p1.y - p2.y;
@@ -600,6 +621,10 @@ namespace mongo {
     static bool circleContainsBoxInternal(const Circle& circle,
                                           const Box& box,
                                           bool includeCircleBoundary) {
+
+        // NOTE: a circle of zero radius is a point, and there are NO points contained inside a
+        // zero-radius circle, not even the point itself.
+
         const Point& a = box._min;
         const Point& b = box._max;
         double compareLL = distanceCompare( circle.center, a, circle.radius ); // Lower left
@@ -628,6 +653,12 @@ namespace mongo {
     static bool circleIntersectsWithBoxInternal(const Circle& circle,
                                                 const Box& box,
                                                 bool includeCircleBoundary) {
+
+        // NOTE: a circle of zero radius is a point, and there are NO points to intersect inside a
+        // zero-radius circle, not even the point itself.
+        if (circle.radius == 0.0 && !includeCircleBoundary)
+            return false;
+
         /* Collapses the four quadrants down into one.
          *   ________
          * r|___B___ \  <- a quarter round corner here. Let's name it "D".