[
https://issues.apache.org/jira/browse/LUCENE-8736?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16817579#comment-16817579
]
Ignacio Vera commented on LUCENE-8736:
--------------------------------------
[~nknize] it would be good to have an example where the determinant overflows
as I haven't been able to exercise such an error.
Regarding the pnoply algorithm, I see the properties and simplicity that
[~rcmuir] likes. One interesting thing to notice is that the algorithm cannot
be really used on a finite space. For example in the geo case, you have
problems for points with longitude = 180 or points with latitude = 90 as those
points cannot be contained by a polygon. This is actually corrected with the
encoding as points are pulled southwards and westwards and there is no points
in the index with those values. The penalty is that you get false positives
(points pulled inside the polygon) and true negatives (points pulled outside of
the polygon).
This is ok in the case of points as the effect is very small and difficult to
notice. On the other hand this effect is pretty big when working with shapes.
Following the example of country shapes, imagine we are indexing now those
countries. If a user executes a query for shapes that intersect one country,
the user would expect to get all neighbour countries. In this case due to the
encoding effect, some of those polygons will be pulled inside the query polygon
and some away so you only get a partial result (neighbour countries north and
east) which is no good in this case. My feeling is that we need to eliminate
the situation where we get true negatives when working with shapes.
One of the possibilities here is to quantise the query polygon as in theory it
should remove true negatives. The problem with doing that is that the pnoply
algorithm won't work anymore because now you have problems again for points
with longitude = 180 and points with latitude = 90. This is the reason I like
the approach of Nick as it removes that problem.
Maybe one possibility is to use different algorithms for points and for shapes
although that means that results will differ depending if you index points as
points or as shapes.
> 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
