1 files changed, 268 insertions, 0 deletions
diff --git a/jstests/core/geo_s2nearComplex.js b/jstests/core/geo_s2nearComplex.js
new file mode 100644
index 00000000000..835dfe88481
--- /dev/null
+++ b/jstests/core/geo_s2nearComplex.js
@@ -0,0 +1,268 @@
+var t = db.get_s2nearcomplex
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+
+/* Short names for math operations */
+Random.setRandomSeed();
+var random = Random.rand;
+var PI = Math.PI;
+var asin = Math.asin;
+var sin = Math.sin;
+var cos = Math.cos;
+var atan2 = Math.atan2
+
+
+var originGeo = {type: "Point", coordinates: [20.0, 20.0]};
+// Center point for all tests.
+var origin = {
+    name: "origin",
+    geo: originGeo 
+}
+
+
+/*
+ * Convenience function for checking that coordinates match.  threshold let's you
+ * specify how accurate equals should be.
+ */
+function coordinateEqual(first, second, threshold){
+    threshold = threshold || 0.001
+    first = first['geo']['coordinates']
+    second = second['geo']['coordinates']
+    if(Math.abs(first[0] - second[0]) <= threshold){
+        if(Math.abs(first[1] - second[1]) <= threshold){
+            return true;
+        }
+    }
+    return false;
+}
+
+/*
+ * Creates `count` random and uniformly distributed points centered around `origin`
+ * no points will be closer to origin than minDist, and no points will be further
+ * than maxDist.  Points will be inserted into the global `t` collection, and will
+ * be returned.
+ * based on this algorithm: http://williams.best.vwh.net/avform.htm#LL
+ */
+function uniformPoints(origin, count, minDist, maxDist){
+    var i;
+    var lng = origin['geo']['coordinates'][0];
+    var lat = origin['geo']['coordinates'][1];
+    var distances = [];
+    var points = [];
+    for(i=0; i < count; i++){
+        distances.push((random() * (maxDist - minDist)) + minDist);
+    }
+    distances.sort();
+    while(points.length < count){
+        var angle = random() * 2 * PI;
+        var distance = distances[points.length];
+        var pointLat = asin((sin(lat) * cos(distance)) + (cos(lat) * sin(distance) * cos(angle)));
+        var pointDLng = atan2(sin(angle) * sin(distance) * cos(lat), cos(distance) - sin(lat) * sin(pointLat));
+        var pointLng = ((lng - pointDLng + PI) % 2*PI) - PI;
+
+        // Latitude must be [-90, 90]
+        var newLat = lat + pointLat;
+        if (newLat > 90) newLat -= 180;
+        if (newLat < -90) newLat += 180;
+
+        // Longitude must be [-180, 180]
+        var newLng = lng + pointLng;
+        if (newLng > 180) newLng -= 360;
+        if (newLng < -180) newLng += 360;
+
+        var newPoint = {
+            geo: {
+                type: "Point",
+                //coordinates: [lng + pointLng, lat + pointLat]
+                coordinates: [newLng, newLat]
+            }
+        };
+
+        points.push(newPoint);
+    }
+    for(i=0; i < points.length; i++){
+        t.insert(points[i]);
+    }
+    return points;
+}
+
+/*
+ * Creates a random uniform field as above, excepting for `numberOfHoles` gaps that
+ * have `sizeOfHoles` points missing centered around a random point. 
+ */
+function uniformPointsWithGaps(origin, count, minDist, maxDist, numberOfHoles, sizeOfHoles){
+    var points = uniformPoints(origin, count, minDist, maxDist);
+    var i;
+    for(i=0; i<numberOfHoles; i++){
+        var randomPoint = points[Math.floor(random() * points.length)];
+        removeNearest(randomPoint, sizeOfHoles);
+    }
+}
+
+/*
+ * Creates a random uniform field as above, expcepting for `numberOfClusters` clusters,
+ * which will consist of N points where `minClusterSize` <= N <= `maxClusterSize.
+ * you may specify an optional `distRatio` parameter which will specify the area that the cluster
+ * covers as a fraction of the full area that points are created on.  Defaults to 10.
+ */
+function uniformPointsWithClusters(origin, count, minDist, maxDist, numberOfClusters, minClusterSize, maxClusterSize, distRatio){
+    distRatio = distRatio || 10
+    var points = uniformPoints(origin, count, minDist, maxDist);
+    for(j=0; j<numberOfClusters; j++){
+        var randomPoint = points[Math.floor(random() * points.length)];
+        var clusterSize = (random() * (maxClusterSize - minClusterSize)) + minClusterSize;
+        uniformPoints(randomPoint, clusterSize, minDist / distRatio, maxDist / distRatio);
+    }
+}
+/*
+ * Function used to create gaps in existing point field.  Will remove the `number` nearest
+ * geo objects to the specified `point`.
+ */
+function removeNearest(point, number){
+    var pointsToRemove = t.find({geo: {$geoNear: {$geometry: point['geo']}}}).limit(number);
+    var idsToRemove = [];
+    while(pointsToRemove.hasNext()){
+        point = pointsToRemove.next();
+        idsToRemove.push(point['_id']);
+    }
+
+    t.remove({_id: {$in: idsToRemove}});
+}
+/*
+ * Validates the ordering of the nearest results is the same no matter how many 
+ * geo objects are requested.  This could fail if two points have the same dist
+ * from origin, because they may not be well-ordered.  If we see strange failures,
+ * we should consider that.
+ */
+function validateOrdering(query){
+    var near10 = t.find(query).limit(10);
+    var near20 = t.find(query).limit(20);
+    var near30 = t.find(query).limit(30);
+    var near40 = t.find(query).limit(40);
+
+    for(i=0;i<10;i++){
+        assert(coordinateEqual(near10[i], near20[i]));
+        assert(coordinateEqual(near10[i], near30[i]));
+        assert(coordinateEqual(near10[i], near40[i]));
+    }
+
+    for(i=0;i<20;i++){
+        assert(coordinateEqual(near20[i], near30[i]));
+        assert(coordinateEqual(near20[i], near40[i]));
+    }
+
+    for(i=0;i<30;i++){
+        assert(coordinateEqual(near30[i], near40[i]));
+    }
+}
+
+var query = {geo: {$geoNear: {$geometry: originGeo}}};
+
+// Test a uniform distribution of 1000 points.
+uniformPoints(origin, 1000, 0.5, 1.5);
+
+validateOrdering({geo: {$geoNear: {$geometry: originGeo}}})
+
+print("Millis for uniform:")
+print(t.find(query).explain().millis)
+print("Total points:");
+print(t.find(query).itcount());
+
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+// Test a uniform distribution with 5 gaps each with 10 points missing.
+uniformPointsWithGaps(origin, 1000, 1, 10.0, 5, 10);
+
+validateOrdering({geo: {$geoNear: {$geometry: originGeo}}})
+
+print("Millis for uniform with gaps:")
+print(t.find(query).explain().millis)
+print("Total points:");
+print(t.find(query).itcount());
+
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+
+// Test a uniform distribution with 5 clusters each with between 10 and 100 points.
+uniformPointsWithClusters(origin, 1000, 1, 10.0, 5, 10, 100);
+
+validateOrdering({geo: {$geoNear: {$geometry: originGeo}}})
+
+print("Millis for uniform with clusters:");
+print(t.find(query).explain().millis);
+print("Total points:");
+print(t.find(query).itcount());
+
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+
+// Test a uniform near search with origin around the pole.
+
+// Center point near pole.
+originGeo = {type: "Point", coordinates: [0.0, 89.0]};
+origin = {
+    name: "origin",
+    geo: originGeo 
+}
+uniformPoints(origin, 50, 0.5, 1.5);
+
+validateOrdering({geo: {$geoNear: {$geometry: originGeo}}})
+
+print("Millis for uniform near pole:")
+print(t.find({geo: {$geoNear: {$geometry: originGeo}}}).explain().millis)
+assert.eq(t.find({geo: {$geoNear: {$geometry: originGeo}}}).itcount(), 50);
+
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+
+// Center point near the meridian
+originGeo = {type: "Point", coordinates: [179.0, 0.0]};
+origin = {
+    name: "origin",
+    geo: originGeo 
+}
+uniformPoints(origin, 50, 0.5, 1.5);
+
+validateOrdering({geo: {$geoNear: {$geometry: originGeo}}})
+
+print("Millis for uniform on meridian:")
+print(t.find({geo: {$near: {$geometry: originGeo}}}).explain().millis)
+assert.eq(t.find({geo: {$geoNear: {$geometry: originGeo}}}).itcount(), 50);
+
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+
+// Center point near the negative meridian
+originGeo = {type: "Point", coordinates: [-179.0, 0.0]};
+origin = {
+    name: "origin",
+    geo: originGeo 
+}
+uniformPoints(origin, 50, 0.5, 1.5);
+
+validateOrdering({geo: {$near: {$geometry: originGeo}}})
+
+print("Millis for uniform on negative meridian:");
+print(t.find({geo: {$near: {$geometry: originGeo}}}).explain().millis);
+assert.eq(t.find({geo: {$near: {$geometry: originGeo}}}).itcount(), 50);
+
+// Near search with points that are really far away.
+t.drop()
+t.ensureIndex({geo: "2dsphere"})
+originGeo = {type: "Point", coordinates: [0.0, 0.0]};
+origin = {
+    name: "origin",
+    geo: originGeo
+}
+
+uniformPoints(origin, 10, 89, 90);
+
+cur = t.find({geo: {$near: {$geometry: originGeo}}})
+
+assert.eq(cur.itcount(), 10);
+cur = t.find({geo: {$near: {$geometry: originGeo}}})
+
+print("Near search on very distant points:");
+print(t.find({geo: {$near: {$geometry: originGeo}}}).explain().millis);
+pt = cur.next();
+assert(pt)