[SERVER-52928] Cannot insert GeoJSON polygon with colinear edges Created: 18/Nov/20  Updated: 27/Dec/23

Status: Backlog
Project: Core Server
Component/s: Geo
Affects Version/s: 3.2.22, 4.2.10
Fix Version/s: None

Type: Bug Priority: Major - P3
Reporter: Ales Pecha Assignee: Backlog - Query Integration
Resolution: Unresolved Votes: 0
Labels: qi-geo
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified
Environment:

standalone server 3.2, Atlas 4.2.10


Attachments: PNG File Screen Shot 2020-11-20 at 3.28.45 PM.png     PNG File mongodb-polygon-error.PNG    
Issue Links:
Related
related to SERVER-75393 Update vendored copy of s2 geometry l... Backlog
Assigned Teams:
Query Integration
Operating System: ALL
Steps To Reproduce:

db.data.createIndex(

{ "geom": "2dsphere" }

,

{ "2dsphereIndexVersion": 3 }

);

db.data.insertOne({
geom:

{ "type": "Polygon", "coordinates": [ [ [ -157.515, 4.937 ], [ -142.529, -89.999 ], [ -142.529, -43.676 ], [ -12.529, -42.767 ], [ -142.529, -6.001 ], [ -142.529, 50.047 ], [ -157.515, 4.937 ] ] ] }

});

Sprint: Query 2021-01-11
Participants:

 Description   

Inserting what seems like a perfectly valid CCW polygon (checked in QGIS, geojsonlint.com, geojson.io) results in this error:

MongoError: Can't extract geo keys: \{ _id: ObjectId('5fb4fbe26a989905900a0f90'), geom: { type: "Polygon", coordinates: [ [ [ -157.515, 4.937 ], [ -142.529, -89.999 ], [ -142.529, -43.676 ], [ -12.529, -42.767 ], [ -142.529, -6.001 ], [ -142.529, 50.047 ], [ -157.515, 4.937 ] ] ] } } Loop is not valid: [ [ 157.515, 4.937 ], [ -142.529, -89.999 ], [ -142.529, -43.676 ], [ -12-.-529, -42.767 ], [ -142.529, -6.001 ], [ -142.529, 50.047 ], [ -157.515, 4.937 ] ] *Edges 1 and 4 cross. Edge locations in degrees: [-142.5290000, -89.9990000]**[-142.5290000, -43.6760000] and [-142.5290000, -6.0010000]-[-142.5290000, 50.0470000]*

But those two offending collinear edges are not even touching.

 

I guess it boils down to this line in the S2 library:

https://github.com/mongodb/mongo/blob/master/src/third_party/s2/s2loop.cc#L148
 



 Comments   
Comment by Kyle Suarez [ 05/Mar/21 ]

Hi ales.pecha@email.cz,

Thank you for reporting this issue and for your patience during our investigation. We've looked into upgrading MongoDB's version of S2 and have determined that we will require more dedicated engineering time to pursue this upgrade. Furthermore, the latest version of s2loop.cc and MongoDB's version are exactly the same, so an upgrade is unlikely to resolve the issue with precision.

We've placed this ticket on our backlog and you may continue watching this for updates.

Kind regards,
Kyle

Comment by Edwin Zhou [ 24/Nov/20 ]

Hi ales.pecha@email.cz,

Thanks a lot for your help investigating the issue. I'm able to reproduce your issue for MongoDB 4.4.2 on various Linux distros and confirm that it's a bug. It appears on Debian 10, Ubuntu 16.04, and Atlas clusters.

Best,

Edwin

Comment by Ales Pecha [ 24/Nov/20 ]

Edwin,

I also tried to track down what I guess might be the source of the problem and found a C# port of the S2 library with comments concerning our issue:

// WORKAROUND(shakusa, ericv): S2.robustCCW() currently
// requires arbitrary-precision arithmetic to be truly robust. That
// means it can give the wrong answers in cases where we are trying
// to determine edge intersections. The workaround is to ignore
// intersections between edge pairs where all four points are
// nearly colinear.

https://github.com/novotnyllc/s2-geometry-library-csharp/blob/master/S2Geometry/S2Loop.cs#L263

I'd say the code to mitigate the issue is missing in your fork of the S2 library as you probably had forked the S2 library before this change.

What do you think?

Best regards,
Ales

Comment by Ales Pecha [ 24/Nov/20 ]

Edwin, many thanks for looking into this. We first encountered the problem on a standalone MongoDB 3.2 running on - I guess - Debian Buster (I'll add detailed version info later). We then tried it on an Atlas instance, just to verify if it is a 3.2 specific problem or not. I haven't been aware that the standalone and Atlas codebases differ though.

Thanks for pointing me to your tool for geojson data visualisation. In our case the offending lines are colinear with meridians (it's timezones dataset), so it shouldn't make a difference I hope.

I can confirm the issue is quite sensitive to the coordinate precision, however it is not very easy for us to identify and tweak every offending line (there are many) in our workflow (the source data is in ESRI's FileGDB).

Best regards,
Ales

Comment by Edwin Zhou [ 24/Nov/20 ]

Hi ales.pecha@email.cz,

Upon further investigation, it looks to be a rounding issue. We changed the coordinates [-142.529, -89.999] to [-142.529, -89.998] and found that it successfully inserts on Atlas. 

What operating system are you inserting this document when you perform it on the standalone server?

Edwin

Comment by Edwin Zhou [ 20/Nov/20 ]

Hi ales.pecha@email.cz,

Thanks for your submission. This looks to be an Atlas issue. I was able to reproduce your issue in Atlas, but not on a local 3.2 and 4.2 mongod instance, where I successfully inserted the document. I can pass your bug report over to the Atlas team.

I also recommend against using geojsonlint.com and geojson.io for displaying your coordinates as those websites attempt to map orthogonal cartesian coordinates on a spherical shape. I recommend using https://geodndmap.mongodb.com, opening up devtools, and running 

loadGeoJson({ "type": "Polygon", "coordinates": [ [ [ -157.515, 4.937 ], [ -142.529, -89.999 ], [ -142.529, -43.676 ], [ -12.529, -42.767 ], [ -142.529, -6.001 ], [ -142.529, 50.047 ], [ -157.515, 4.937 ] ] ] })

Here's how the plotted coordinates should look:

 

Kind regards,
Edwin
 

Generated at Thu Feb 08 05:29:24 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.