[SERVER-16557] $geoWithin does not return all documents within polygon Created: 15/Dec/14  Updated: 15/Apr/16  Resolved: 14/Jan/15

Status: Closed
Project: Core Server
Component/s: Geo
Affects Version/s: 2.6.5
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Andre Spiegel Assignee: Siyuan Zhou
Resolution: Done Votes: 0
Labels: None
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Related
related to SERVER-19328 $geoIntersects does not work as expected Closed
Backwards Compatibility: Fully Compatible
Operating System: ALL
Participants:

 Description   

I'm creating a collection with 1000 random points roughly in the area where Canada would be on the globe:

for (i=0; i<1000; i++) {
   var lon = -25 - Math.random() * 75;
   var lat = 35 + Math.random() * 35;
   db.data.insert({"loc": { "type" : "Point",
                             "coordinates" : [ lon, lat ] } });
}

In other words, longitude is between -100 and -25, and latitude is between 35 and 70. I'm defining a 2dsphere index on it:

db.data.ensureIndex({"loc":"2dsphere"})

and then query with a bounding rectange that should encompass all the points:

db.data.find({"loc":
  {"$geoWithin":
    {"$geometry":{"type":"Polygon",
                  "coordinates":[[[-110, 30], [-110, 75], [-20, 75], [-20, 30], [-110, 30]]]}}}}
)

(The polygon runs from -110 to -20 longitude and 30 to 75 latitude.) However, the query does not return all 1000 documents (in one particular example, I only got 919). If I make the rectangle even larger, it actually returns even less documents. This can be confirmed both by .count() and .toArray().length.

Is there anything wrong in my setup or assumptions how $geoWithin works?



 Comments   
Comment by Zane Mccaig [ 15/Apr/16 ]

I ran into this issue as well and I decided to generate a new $geometry `Polygon` type that will approximate a $box query.
You can find my code here https://gist.github.com/zanemcca/02c31cdde49e7043d68bfb04be60330a

Comment by Siyuan Zhou [ 14/Jan/15 ]

Hey andre.spiegel@10gen.com - I am closing this as "Work as Designed". If you have any further question, please reopen this ticket.

Comment by Siyuan Zhou [ 17/Dec/14 ]

The edges of a polygon are indeed interpreted as being located on the spherical surface themselves. The shortest path on spherical surface between two points is actually a part of the Great Circle passing those two points.

Lon/Lat is a mapping from a sphere to a two dimensional coordinate system. It's kind of counter-intuitive inevitably, in terms of range, e.g. lon 180 == lon -180 and longitude doesn't matter at North/South Pole.

After consulting a GIS PhD in MongoGIS group, I believe in GIS, people usually don't compute the geometries on a sphere in the way MongoDB does. They project a particular region on a globe to a flat map, trying to maintain the correct relationships between geometries as much as possible, and then do the computation on it, since plane geometry is easier. There are many different kinds of projections, see d3.geo.projections for graphs and Google Help for examples. The projection used by Google Map and Leatlet is a Simple Cylindrical projection, where the meridians and parallels are equidistant, straight lines, with the two sets crossing at right angles. This projection doesn't preserve the angles or distances for all points. Actually, no projection does both well at a global scale, but some prefer right angles and others prefer right distances. That's why we have this problem you are facing now.

This definition of segment makes things a little difficult sometimes. For instance, the border of some US states are defined using parallels. To represent them accurately enough, we need to add more middle points. However, in my opinion, MongoDB did the right thing here. Imagine we have a series of waypoints of a flight. We'd like to know which states this flight has passed through. MongoDB gives the correct answers, since a plane goes along the shorted path rather than parallels.

Comment by Andre Spiegel [ 16/Dec/14 ]

Thanks for the explanation. I would however expect that the edges of a polygon are interpreted as being located on the spherical surface themselves. It seems counter-intuitive that a point with lon/lat that is numerically in the range of the polygon effectively lies outside of it. How do other geo/gis systems handle this? I think mongo should do the same. At the very least, this should be clearly explained in the documentation. (I'll be happy to file a doc ticket if that's what we agree on.)

Comment by Siyuan Zhou [ 16/Dec/14 ]

Hi Andre, this is because a segment on a globe is defined by the shortest path between the two points and a polygon is enclosed by these segments. On a map, the segments are shown as curves due to distortion.

To visualize this issue, try to select, drag and drop the following GeoJSON to http://map.visualzhou.com respectively.

{
    "type": "Polygon",
    "coordinates": [
        [
            [-110, 30],
            [-110, 75],
            [-20, 75],
            [-20, 30],
            [-110, 30]
        ]
    ]
}

{
    "type": "Point",
    "coordinates": [-60, 36]
}

It's clear that the point is out of the polygon. As a workaround, adding more middle points will alleviate this problem, but we can't eliminate it.

Generated at Thu Feb 08 03:41:26 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.