[jira] [Commented] (LUCENE-8736) LatLonShapePolygonQuery returning incorrect WITHIN results with shared boundaries

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (LUCENE-8736) LatLonShapePolygonQuery returning incorrect WITHIN results with shared boundaries

JIRA jira@apache.org

    [ https://issues.apache.org/jira/browse/LUCENE-8736?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16800456#comment-16800456 ]

Ignacio Vera commented on LUCENE-8736:
--------------------------------------

Thanks [~nknize] for sharing the algorithm, looks pretty powerful.

I had a look into the patch and the first thing I notice is that the test {{testLUCENE8669}} is failing. It seems that the indexed polygons are never added to the index so fix is trivial (Method {{w.addDocument(doc)}} has been removed in the patch):
{code:java}
-    Field[] fields = LatLonShape.createIndexableFields("test", indexPoly1);
-    for (Field f : fields) {
-      doc.add(f);
-    }
-    fields = LatLonShape.createIndexableFields("test", indexPoly2);
-    for (Field f : fields) {
-      doc.add(f);
-    }
-    w.addDocument(doc);
+    addPolygonsToDoc(FIELDNAME, doc, indexPoly1);
+    addPolygonsToDoc(FIELDNAME, doc, indexPoly2);
     w.forceMerge(1);{code}
 

Regarding the new approach, it seems there is still something missing. If we change the test by translating the polygons one degree north and 1 degree east, the change does not have effect due to the encoding of the indexed polygons:

 
{code:java}
public void testWithinFailure() throws Exception {
    Directory dir = newDirectory();
    RandomIndexWriter w = new RandomIndexWriter(random(), dir);

    // test polygons:
    Polygon indexPoly1 = new Polygon(new double[] {4d + 1d, 4d + 1d, 3d + 1d, 3d + 1d, 4d + 1d}, new double[] {3d + 1d, 4d + 1d, 4d + 1d, 3d + 1d, 3d + 1d});
    Polygon indexPoly2 = new Polygon(new double[] {2d + 1d, 2d + 1d, 1d + 1d, 1d + 1d, 2d + 1d}, new double[] {6d + 1d, 7d + 1d, 7d + 1d, 6d + 1d, 6d + 1d});
    Polygon indexPoly3 = new Polygon(new double[] {1d + 1d, 1d + 1d, 0d + 1d, 0d + 1d, 1d + 1d}, new double[] {3d + 1d, 4d + 1d, 4d + 1d, 3d + 1d, 3d + 1d});
    Polygon indexPoly4 = new Polygon(new double[] {2d + 1d, 2d + 1d, 1d + 1d, 1d + 1d, 2d + 1d}, new double[] {0d + 1d, 1d + 1d, 1d + 1d, 0d + 1d, 0d + 1d});

    // index polygons:
    Document doc;
    addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly1);
    w.addDocument(doc);
    addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly2);
    w.addDocument(doc);
    addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly3);
    w.addDocument(doc);
    addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly4);
    w.addDocument(doc);

    ///// search //////
    IndexReader reader = w.getReader();
    w.close();
    IndexSearcher searcher = newSearcher(reader);

    Polygon[] searchPoly = new Polygon[] {new Polygon(new double[] {4d + 1d, 4d + 1d, 0d + 1d, 0d + 1d, 4d + 1d}, new double[] {0d + 1d, 7d + 1d, 7d + 1d, 0d + 1d, 0d + 1d})};

    Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, searchPoly);
    assertEquals(4, searcher.count(q));
    IOUtils.close(w, reader, dir);
  }{code}
 

I have tried to quantize the query polygon but that seems to add other issues.

> LatLonShapePolygonQuery returning incorrect WITHIN results with shared boundaries
> ---------------------------------------------------------------------------------
>
>                 Key: LUCENE-8736
>                 URL: https://issues.apache.org/jira/browse/LUCENE-8736
>             Project: Lucene - Core
>          Issue Type: Bug
>            Reporter: Nicholas Knize
>            Priority: Major
>         Attachments: LUCENE-8736.patch
>
>
> Triangles that are {{WITHIN}} a target polygon query that also share a boundary with the polygon are incorrectly reported as {{CROSSES}} instead of {{INSIDE}}. This leads to incorrect {{WITHIN}} query results  as demonstrated in the following test:
> {code:java}
>   public void testWithinFailure() throws Exception {
>     Directory dir = newDirectory();
>     RandomIndexWriter w = new RandomIndexWriter(random(), dir);
>     // test polygons:
>     Polygon indexPoly1 = new Polygon(new double[] {4d, 4d, 3d, 3d, 4d}, new double[] {3d, 4d, 4d, 3d, 3d});
>     Polygon indexPoly2 = new Polygon(new double[] {2d, 2d, 1d, 1d, 2d}, new double[] {6d, 7d, 7d, 6d, 6d});
>     Polygon indexPoly3 = new Polygon(new double[] {1d, 1d, 0d, 0d, 1d}, new double[] {3d, 4d, 4d, 3d, 3d});
>     Polygon indexPoly4 = new Polygon(new double[] {2d, 2d, 1d, 1d, 2d}, new double[] {0d, 1d, 1d, 0d, 0d});
>     // index polygons:
>     Document doc;
>     addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly1);
>     w.addDocument(doc);
>     addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly2);
>     w.addDocument(doc);
>     addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly3);
>     w.addDocument(doc);
>     addPolygonsToDoc(FIELDNAME, doc = new Document(), indexPoly4);
>     w.addDocument(doc);
>     ///// search //////
>     IndexReader reader = w.getReader();
>     w.close();
>     IndexSearcher searcher = newSearcher(reader);
>     Polygon[] searchPoly = new Polygon[] {new Polygon(new double[] {4d, 4d, 0d, 0d, 4d}, new double[] {0d, 7d, 7d, 0d, 0d})};
>     Query q = LatLonShape.newPolygonQuery(FIELDNAME, QueryRelation.WITHIN, searchPoly);
>     assertEquals(4, searcher.count(q));
>     IOUtils.close(w, reader, dir);
>   }
> {code}



--
This message was sent by Atlassian JIRA
(v7.6.3#76005)

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]