[SERVER-19129] S2 sometimes returns empty coverings Created: 25/Jun/15 Updated: 06/Dec/22 Resolved: 02/Aug/19 |
|
| Status: | Closed |
| Project: | Core Server |
| Component/s: | Geo |
| Affects Version/s: | 3.0.4 |
| Fix Version/s: | None |
| Type: | Bug | Priority: | Major - P3 |
| Reporter: | Kevin Albertson | Assignee: | Backlog - Query Team (Inactive) |
| Resolution: | Done | Votes: | 0 |
| Labels: | query-44-grooming | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Attachments: |
|
||||||
| Assigned Teams: |
Query
|
||||||
| Operating System: | ALL | ||||||
| Steps To Reproduce: | To see the effects of this, you can run the following:
Additionally, attached is a patch including a unit test to reproduce this bug with just the S2 functions. Compile it with: |
||||||
| Participants: |
| Description |
|
Some very specific $near queries with small (but not negligible) $maxDistance values will unexpectedly return empty results. So far this can only be reproduced in the shell by manually setting the coarsestIndexedLevel and finestIndexedLevel. Ultimately, this is caused by S2 returning empty coverings for S2Cap regions. The root of this problem seems to be caused by floating point error in the S2Cap::Contains method. For a full S2Cap (entire sphere) S2Cap::Contains will return false on some points along/near the negative axis. The expected behavior is to return true for any point or geometry, since it is the full sphere. |
| Comments |
| Comment by David Storch [ 02/Aug/19 ] |
|
Per discussion with kevin.albertson, I'm going to close this ticket. It's possible there are other manifestations of a similar problem, but this particular case has been fixed. |
| Comment by Kevin Albertson [ 13/Aug/15 ] |
|
We have added a workaround which avoids the case of the occurrence in this ticket. The annulus regions in geo near are represented as an intersection of the outer cap and the complement of the inner cap (the hole of the annulus). In the first interval, since the inner cap has a radius 0 its complement should be the full sphere. However, S2 may still say that a point is not in the inner cap complement in degenerate cases. Therefore, we removed the inner cap complement on the first interval, fixing this case. |
| Comment by Kevin Albertson [ 17/Jul/15 ] |
|
Similar behavior was found when working on |
| Comment by Kevin Albertson [ 02/Jul/15 ] |
|
milkie Yes it does. |
| Comment by Eric Milkie [ 02/Jul/15 ] |
|
I'm curious, does the test fail in the same way when compiled with gcc, clang, and Visual Studio? |