[SERVER-5915] Polygon::contains() can return wrong result with points on edge Created: 23/May/12  Updated: 28/Dec/23

Status: Backlog
Project: Core Server
Component/s: Geo
Affects Version/s: 2.0.5, 2.4.1
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Hal St. Clair Assignee: Backlog - Query Integration
Resolution: Unresolved Votes: 1
Labels: qi-geo, query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PNG File diagram.png     File mongotest.js    
Issue Links:
Related
is related to SERVER-17851 $geoWithin and $geoIntersects do not ... Backlog
Assigned Teams:
Query Integration
Operating System: Linux
Participants:

 Description   

The result set from the attached example code, depending on the value of 'increment', should always contain a square number of entries: 1, 9, 25, 49, 81, 121...

when 'increment' is .1, the number produced should be 441 but only 400 are generated. Further, when 'offset' is 2, 391 entries are generated.

Dude, what gives?



 Comments   
Comment by Jason Giles [ 30/May/12 ]

I'm working with Hal on this issue (he's out of town right now).
We started with simple tests written in groovy...here is an example we converted and ran directly from the Mongo shell:

use testDb
 
db.locations.save( { loc: { x: 1, y: 1 } } )
db.locations.save( { loc: { x: 2, y: 0 } } )
db.locations.save( { loc: { x: 3, y: 1 } } )
 
db.locations.find()
 
db.locations.ensureIndex( { loc: "2d" } )
 
box = [ [0, 0], [3, 3] ]
db.locations.find( { "loc": { "$within": { "$box": box } } } )
 
polygon = [ [0, 0], [2, 2], [4, 0] ]
db.locations.find( { "loc": { "$within": { "$polygon": polygon } } } )

When I run the example above, the box search finds all the saved points as expected.
The polygon search, however, only finds points (2, 0) and (3, 1).
Point (1, 1) should have been found also.

We have also tested using more saved points and search polygons created with different rotation. These tests have consistently failed to find all points. If you need more examples, please let me know. The simple test above seemed like a good place to start.

Comment by Eliot Horowitz (Inactive) [ 26/May/12 ]

floats are't perfectly precise, so you're hitting a precision edge case in javascript

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