[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: |
|
||||||||||||||||||||||||
| Assigned Teams: |
Query Integration
|
||||||||||||||||||||||||
| Operating System: | ALL | ||||||||||||||||||||||||
| Participants: | |||||||||||||||||||||||||
| Case: | (copied to CRM) | ||||||||||||||||||||||||
| Description |
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, 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 ] | ||||||||||
|
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 | ||||||||||
| 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
is, however, incorrect. The full quote reads:
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 ] | ||||||||||
ProblemThere 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 - LineLet'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 - PolygonPolygon 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.
Point in PolygonIn 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
Degenerate occurs when the point is its cell's vertex, like the case reported in the first comment.
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.
Line - PolygonLine - 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. ImpactsDegeneracies 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 StepWe 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: 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
Existing Polygons:
Result:
|