LatLonShapePolygon and LineQuery fail on shared dateline queries [LUCENE-8721]

[asfimport]

Indexed shapes should be returned with search geometries that share the dateline on the opposite hemisphere.

For example:

  public void testSharedDateline() throws Exception {
    //// index /////
    Directory dir = newDirectory();
    RandomIndexWriter w = new RandomIndexWriter(random(), dir);
    Document doc = new Document();
    // index western hemisphere geometry
    Polygon indexPoly = new Polygon(
        new double[] {-7.5d, 15d, 15d, 0d, -7.5d},
        new double[] {-180d, -180d, -176d, -176d, -180d}
    );
    Field[] fields = LatLonShape.createIndexableFields("test", indexPoly);
    for (Field f : fields) {
      doc.add(f);
    }
    w.addDocument(doc);
    w.forceMerge(1);

    ///// search //////
    IndexReader reader = w.getReader();
    w.close();
    IndexSearcher searcher = newSearcher(reader);
    // search w/ eastern hemisphere geometry that shares the dateline
    Polygon searchPoly = new Polygon(new double[] {-7.5d, 15d, 15d, 0d, -7.5d},
        new double[] {180d, 180d, 170d, 170d, 180d});
    Query q = LatLonShape.newPolygonQuery("test", QueryRelation.INTERSECTS, searchPoly);
    assertEquals(1, searcher.count(q));
    IOUtils.close(w, reader, dir);
  }

---

Migrated from LUCENE-8721 by Nick Knize (@nknize), updated Mar 13 2019
Attachments: LUCENE-8721.patch (versions: 2)

[asfimport]

Nick Knize (@nknize) (migrated from JIRA)

Simple patch adds shared dateline logic in Polygon2D and Line2D.

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

Should we check whether there is an intersection between the range of latitudes of the query and of the box/triangle? The patch seems to only look at longitudes, which means it might return CROSSES when it could return DISJOINT if latitudes don't overlap?

Unrelated to your change but I find the relate logic a bit hard to follow due to how it's split between EdgeTree and its sub classes via 3 methods: relate, internalComponentRelate and componentRelate.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

In addition, it won't work for all cases for triangles as the coordinates are on the encoded space, so 180 becomes 179.99999991618097 so one side of the equality will never be true.

+1 to simplify the logic on EdgeTree. It is trivial to merge the methods relate &  internalComponentRelate and it makes sense. I will open an issue.

[asfimport]

Nick Knize (@nknize) (migrated from JIRA)

Should we check whether there is an intersection between the range of latitudes of the query and of the box/triangle?

Yes. I posted the wrong patch. Corrected in the new one.

the coordinates are on the encoded space.

The coordinates are in the decoded space but they have been quantized so I've corrected maxLon to use its quantized variant.

+1 to simplify the logic on EdgeTree. It is trivial to merge the methods relate & internalComponentRelate and it makes sense. I will open an issue.

+1 to simplify. I went ahead and started by merging the two methods in this patch since it made sense. The new issue can explore further refactoring the logic for clarity.

[asfimport]

Ignacio Vera (@iverase) (migrated from JIRA)

I tried the patch and I get a failure in another test: testLUCENE8669

It is true that in the current implementation a line on the dateline will never intersects any other shape on the other side but I see that more like a feature. Not sure if about this approach, more over when we have #9680 where an indexed line query by itself might return an empty result.