[
https://issues.apache.org/jira/browse/LUCENE-8736?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Nicholas Knize reopened LUCENE-8736:
------------------------------------
Assignee: Nicholas Knize
Lucene Fields: New (was: New,Patch Available)
[~rcmuir] yeah I was thinking about that while working these changes. On the
one hand explicitly accepting boundary failures (especially for such common
cases as shown here and in the test) is annoying (though I get the reasoning).
On the other hand, the determinant equality approach could also [suffer from
overflow|https://www.cs.cmu.edu/~quake/robust.html]. The problem with the
latter is that we don't have a good feel for the rate at which overflow occurs
or the percentage of false positives for when points outside the polygon are
erroneously determined as colinear by an overflowed determinant. I think that
deserves some further exploration.
So for now, I can revert the change for points but I'm curious to your thoughts
around exploring the [adaptive
orientation|https://www.cs.cmu.edu/afs/cs/project/quake/public/code/predicates.c]
(_orient2dadap_) approach to solve the overflow issue. I have a [very rough
port|https://gist.github.com/nknize/dd1dc8a1ccaa8900b70c478cce846f29] that I
can experiment with for points in a separate issue?
> 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
> Assignee: Nicholas Knize
> Priority: Major
> Fix For: 8.1, master (9.0)
>
> Attachments: LUCENE-8736.patch, LUCENE-8736.patch,
> adaptive-decoding.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: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
