[SERVER-13599] $geoIntersects does not return polygon with shared edge Created: 15/Apr/14  Updated: 28/Dec/23

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

Type: Bug Priority: Major - P3
Reporter: Asya Kamsky Assignee: Backlog - Query Integration
Resolution: Unresolved Votes: 3
Labels: qi-geo, query-44-grooming
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Issue Links:
Documented
Duplicate
is duplicated by SERVER-12462 $geoWithin query doesn't return a poi... Closed
Related
related to DOCS-5193 Degeneracy of geometry relationship w... Closed
is related to SERVER-17851 $geoWithin and $geoIntersects do not ... Backlog
Assigned Teams:
Query Integration
Operating System: ALL
Participants:
Case:

 Description   

db.polygon.drop();
db.polygon.insert([ { "_id" : "Poly1", "shape" : { "type" : "Polygon", "coordinates" : [ [ [0.0000, 0.000],[3.000,0.000],[3.000,3.000],[0.000,3.000], [0.0000, 0.000]]]}},
... { "_id" : "Poly2", "shape" : { "type" : "Polygon", "coordinates" : [ [ [3.00,0.00],[6.00,0.00],[6.00,3.00],[3.00,3.00],[3.00,0.00] ] ] } } ]);
db.polygon.ensureIndex({shape:"2dsphere"});
var box={"type" : "Polygon", "coordinates" : [ [ [ 0.000, 0.0000 ], [ 3.0000, 0.0000 ], [ 3.000, 3.000 ], [ 0.000, 3.000 ], [ 0.000, 0.0000 ] ] ] }
db.polygon.find( {shape: {$geoIntersects: {$geometry: box}}}, {_id:1})
{ "_id" : "Poly1" }

Poly2 and box share two adjacent points [ 3.0000, 0.0000 ] and [ 3.000, 3.000 ] so Poly2 should be returned, but it's not.

Analogously, using box of points from Poly2 will only match Poly2 and not Poly1.

Our docs say: A location intersects a GeoJSON object if the intersection is non-empty. This includes documents that have a shared edge.

This happens in 2.4 (v1) and 2.6(v2). It happens with line/polygon and polygon/polygon intersections.



 Comments   
Comment by Ramon Fernandez Marina [ 14/Apr/15 ]

Actually if the behavior described in a ticket is present in all versions what we do is to leave the "affected versions" field empty.

Comment by Christian Tonhäuser [ 14/Apr/15 ]

asya,
Could you please add 3.0 to the affected versions?

Thanks and regards,

Christian

Comment by Alex Olieman [ 11/Apr/15 ]

Thank you very much asya,

it is good to hear that you are able to make this kind of effort for the geospatial community! I'm looking forward to the update.

Comment by Asya Kamsky [ 11/Apr/15 ]

AliOli,

We are discussing our options internally and will update this ticket when we converge on a solution - we are considering several possible ways to resolve/fix this issue.

Asya Kamsky
Product Management

Comment by Alex Olieman [ 10/Apr/15 ]

I find it interesting that the question of how to deal with degenerate cases in geospatial computation has a decades-old argument at its core. Basically, the issue can be dealt with by the perturbation technique (aka SoS, 1990), as S2 does, or by using algorithms that deal with the degenerate cases directly (Burnikel, Melhorn, & Schirra, 1994).

As siyuan.zhou@10gen.com sufficiently explained, the perturbations used in S2 make it challenging to implement operators that comply with the DE-9IM spatial predicates. The remark that

Degeneracies occur very rare in reality, with probability zero if we draw a finite number of geometries

is, however, incorrect. The full quote reads:

Degeneracies occur with probability zero if we draw a fi nite number of geometric objects, each represented by a fi nite set of numbers from the (inf nite) set of all such objects, provided there is
no bound on the precision of the numbers used. In real-life computing this is not the case; that
is, there is only a fi nite set of available numbers and thus a bound on the precision that can be
achieved. As a consequence, we are doomed to work with degenerate data.

It might be the case that S2 has chosen an unfortunate approach to dealing with degeneracies, but I'm not entirely convinced that the perturbations are the problem. There are some tests that deal with shared edges in s2polygon_test, but I find them hard to read. Can someone who watches this issue verify that S2 actually considers two polygons with a shared edge to be disjoint (i.e. not to intersect)?

If the problem is inherent to S2, would there be any chance that a future MongoDB version will rely on a library for spatial computation/geohashing that does support the DE-9IM predicates? Other databases that offer spatial indexing do comply with the (full suite of) predicates, e.g. with PostGIS and Neo4j Spatial. The most promising library probably is GEOS, because it supports all predicates, is coded in C++, is actively maintained, and is being used successfully in many production environments (underlying PostGIS).

It would be useful for us to get an idea of the MongoDB roadmap for spatial indexing. Of course, nothing is stopping me from using GEOS directly, except that it would be such a shame to have to build custom indexes on top of MongoDB. This may sound blunt, but my real question is: when, if at all, can we expect MongoDB to offer competitive spatial indexing? If this is not a priority, I should consider using an alternative for applications that would benefit from DE-9IM compliance.

Comment by Siyuan Zhou [ 09/Apr/15 ]

Problem

There is an inconsistency between the behavior and the documentation. After investigating into S2 library, I think it's worth summarizing the properties of geometry operations in S2.

Point - Line

Let's start from the basis. We are talking about the line segment as edge of polygon defined internally, not the behavior of LingString of GeoJSON.

In S2, if a point is not a vertex of that line segment, it lies on either the left or the right of the line, never exactly on the line for simplicity, following the idea of the paper "Simulation of Simplicity" to handle degenerate. Which side it lies on is deterministic and depends on both the point and the line. This means no three points are collinear (on the same great circle of sphere), since the tie is always broken.

The relation of a line segment and its vertex is special and discussed in particular context later.

Polygon - Polygon

Polygon containment and intersection are well defined for a polygon. Contains() return true if the interior of this polygon is a superset of the interior of the given other loop. A polygon contains itself.

For shared vertices, S2 tests the interior of both angles, based on counter-clockwise ordering. If two polygons share a same edge, like the case in Description, they don't intersect if their interiors don’t.

If two polygon have collinear edges but not exactly the same, remember S2 doesn't allow collinear points, AB will be above or below AC in the following case. Containment can be defined accordingly.

A--------->B-------->C

Point in Polygon

In MongoDB, a polygon contains / intersects a point if it intersects with the point's cell. A cell is a square with side of 8.67 mm on average, used for geo hashing. We expand a point to its cell to cover edges and vertices of the other geometry. Note that

Polygon.Contains(point) == Polygon.Intersects(point) 

Degenerate occurs when the point is its cell's vertex, like the case reported in the first comment.

         ^
     C' C|______B
         |      |
         |      |
         |O     |A (~7.1e-8, 0)(lng, lat)
---------+------+--->
         |      A'
         |

As shown above, OABC is the tiny cell of point O. It intersects the upper right polygon, but also intersects the upper left and lower right polygons, since C is considered as C' inside upper left polygon, according to "no collinear" rule. The same is true for A to be considered as A'. As a result, the point intersects with 3 out of 4 polygons.

To sum up the rules about point in polygon test.

  • If it's in the interior, everything is intuitive.
  • If it's in the exterior, it may intersect if it's too close due to the cell expansion.
  • If it's on the boundary, its either inside or outside, or both since we expand it to its cell.
  • If it's a vertex of the polygon, it may not may not be contained.
  • Loops do not necessarily contain all (or any) of their vertices.
  • The only guarantee S2 offers is that a shared vertex must be contained by at least one polygon that shares the point. This guarantee is critical for cell's definition, since a point must be hashed to a cell and the cell must contain it.

Line - Polygon

Line - Polygon intersection works find for non-degenerates.

The intersection of a polygon and its edges is the only degenerate case. In a nutshell, there's no guarantee. The intersection test depends on the containment of the first vertex of line and edge clipping against polygon. Reverting a line gives the opposite edge clipping for degenerates, but it also changes the first vertex. Anyway, reverting the line can be a workaround to give better coverage for edges, but I can imagine there'll be some corner cases.

Impacts

Degeneracies occur very rare in reality, with probability zero if we draw a finite number of geometries (ref. Simulation of Simplicity). Besides, the use cases where degenerate must be treated one way or the other are not clear. In most cases, there is a workaround, like expanding geometries or tweaking coordinates.

However, the inconsistency with documentation indeed causes confusion. What properties of degenerate MongoDB should provide and why they are useful is also unclear.

Next Step

We need to update the documentation to reflect the actual behavior. In short term, no code change is planned.

Comment by Christian Tonhäuser [ 24/Mar/15 ]

Error also exists in 3.0.0

However, the example from Google Groups behaves even worse than shown by Asya Kamsky:
Only the first of the four points is returned, on 2.4.10 as well as on 3.0.0!
Didn't get around to test it on a 2.6, yet.

Edit: If the documentation would at least reflect the actual behaviour of the operator, customers might be able to work around the issues. Nevertheless, we'd prefer a fixed bug to updated documentation in this case.

Comment by Asya Kamsky [ 02/Sep/14 ]

Another instance of this reported on Google Groups:

similar issue. Four intersecting polygons exist in a collection as shown below, however, only three are returned when the

 [0, 0] 

intersecting point is queried.

Existing Polygons:

{ "_id" : "1000390", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ 0, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 0 ], [ 0, 0 ] ] ] } }
{ "_id" : "7000499", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ 0, -1 ], [ 0, 0 ], [ 1, 0 ], [ 1, -1 ], [ 0, -1 ] ] ] } }
{ "_id" : "3000100", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ -1, 0 ], [ -1, 1 ], [ 0, 1 ], [ 0, 0 ], [ -1, 0 ] ] ] } }
{ "_id" : "5000209", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ -1, -1], [ -1, 0 ], [ 0, 0 ], [ 0, -1 ], [ -1, -1 ] ] ] } }

> db.mycollection.find( { loc : { $geoIntersects : { $geometry : { type: "Point", coordinates: [0,0] }}}} )

Result:

{ "_id" : "1000390", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ 0, 0 ], [ 0, 1 ], [ 1, 1 ], [ 1, 0 ], [ 0, 0 ] ] ] } }
{ "_id" : "7000499", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ 0, -1 ], [ 0, 0 ], [ 1, 0 ], [ 1, -1 ], [ 0, -1 ] ] ] } }
{ "_id" : "3000100", "loc" : { "type" : "Polygon", "coordinates" : [ [ [ -1, 0 ], [ -1, 1 ], [ 0, 1 ], [ 0, 0 ], [ -1, 0 ] ] ] } }

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