[SERVER-82435] 2dsphere index thinks clearly parallel lines intersect Created: 25/Oct/23  Updated: 01/Nov/23  Resolved: 30/Oct/23

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

Type: Bug Priority: Major - P3
Reporter: Bill Mills Assignee: Adam Harrison
Resolution: Works as Designed Votes: 0
Labels: 2dsphere, geojson
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Attachments: PNG File Both Edges.png     PNG File Intersection.png    
Operating System: ALL
Steps To Reproduce:

> db.createCollection('xx')
{ "ok" : 1 }
> db.xx.createIndex({geolocation:'2dsphere'})
{
    "numIndexesBefore" : 1,
    "numIndexesAfter" : 2,
    "createdCollectionAutomatically" : false,
    "ok" : 1
}
> db.xx.insertOne({'_id': 'busted', geolocation: {'type': 'Polygon', 'coordinates': [[[101.5625,-45.25],[76.5625,-45.25],[82.1875,-45.75],[89.6875,-45.75],[101.5625,-45.25]]]}})
WriteError({
    "index" : 0,
    "code" : 16755,
    "errmsg" : "Can't extract geo keys: { _id: \"busted\", geolocation: { type: \"Polygon\", coordinates: [ [ [ 101.5625, -45.25 ], [ 76.5625, -45.25 ], [ 82.1875, -45.75 ], [ 89.6875, -45.75 ], [ 101.5625, -45.25 ] ] ] } }  Loop is not valid: [ [ 101.5625, -45.25 ], [ 76.5625, -45.25 ], [ 82.1875, -45.75 ], [ 89.6875, -45.75 ], [ 101.5625, -45.25 ] ] Edges 0 and 2 cross. Edge locations in degrees: [-45.2500000, 101.5625000]-[-45.2500000, 76.5625000] and [-45.7500000, 82.1875000]-[-45.7500000, 89.6875000]",
    "op" : {
        "_id" : "busted",
        "geolocation" : {
            "type" : "Polygon",
            "coordinates" : [
                [
                    [
                        101.5625,
                        -45.25
                    ],
                    [
                        76.5625,
                        -45.25
                    ],
                    [
                        82.1875,
                        -45.75
                    ],
                    [
                        89.6875,
                        -45.75
                    ],
                    [
                        101.5625,
                        -45.25
                    ]
                ]
            ]
        }
    }
}) :
WriteError({
    "index" : 0,
    "code" : 16755,
    "errmsg" : "Can't extract geo keys: { _id: \"busted\", geolocation: { type: \"Polygon\", coordinates: [ [ [ 101.5625, -45.25 ], [ 76.5625, -45.25 ], [ 82.1875, -45.75 ], [ 89.6875, -45.75 ], [ 101.5625, -45.25 ] ] ] } }  Loop is not valid: [ [ 101.5625, -45.25 ], [ 76.5625, -45.25 ], [ 82.1875, -45.75 ], [ 89.6875, -45.75 ], [ 101.5625, -45.25 ] ] Edges 0 and 2 cross. Edge locations in degrees: [-45.2500000, 101.5625000]-[-45.2500000, 76.5625000] and [-45.7500000, 82.1875000]-[-45.7500000, 89.6875000]",
    "op" : {
        "_id" : "busted",
        "geolocation" : {
            "type" : "Polygon",
            "coordinates" : [
                [
                    [
                        101.5625,
                        -45.25
                    ],
                    [
                        76.5625,
                        -45.25
                    ],
                    [
                        82.1875,
                        -45.75
                    ],
                    [
                        89.6875,
                        -45.75
                    ],
                    [
                        101.5625,
                        -45.25
                    ]
                ]
            ]
        }
    }
})
WriteError@src/mongo/shell/bulk_api.js:465:48
mergeBatchResults@src/mongo/shell/bulk_api.js:871:49
executeBatch@src/mongo/shell/bulk_api.js:940:13
Bulk/this.execute@src/mongo/shell/bulk_api.js:1182:21
DBCollection.prototype.insertOne@src/mongo/shell/crud_api.js:264:9
@(shell):1:1 

Participants:

 Description   

Inserting a geojson polygon in a field indexed with 2dsphere fails, claiming two separate parallel lines of constant latitude intersect. Full repro in 5.0.9 below.

 



 Comments   
Comment by Bill Mills [ 01/Nov/23 ]

Hi adam.harrison@mongodb.com, thanks for taking the time! I'm really surprised by this, there must be something I don't understand about how MongoDB is interpreting these coordinates.

I understand this geometry is on a sphere, but even (or especially) on a sphere, lines of constant latitude do not intersect. The only conclusion I can draw here, is that a line segment such as [101.5625, -45.25], [76.5625, -45.25] is not interpreted as being a line of constant latitude even though it starts and ends on the same circle. What is the correct way to define a polygon edge of constant latitude for a 2dsphere index?

I suppose we can approximate it by putting lots of vertexes along the line rather than traversing 25 degrees at a time, but I'd rather avoid this because I suspect this is going to bloat the index size.

Thanks again for your attention on this.

Comment by Adam Harrison [ 30/Oct/23 ]

Hi Bill, 

Thanks for the clear reproduction! 

This looks like it is expected behavior. Note that 2dsphere indexes perform geospatial operations on an earth-like sphere. While these specific edges are parallel on an X-Y coordinate plane, they are actually intersect when mapped over a sphere like surface.

I've attached screenshots showing both of these edges graphed across a sphere and the corresponding intersection that would be generated a result.

We hope this helps!
 

Generated at Thu Feb 08 06:49:13 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.