[
https://issues.apache.org/jira/browse/LUCENE-8736?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16802637#comment-16802637
]
Ignacio Vera edited comment on LUCENE-8736 at 3/27/19 10:43 AM:
----------------------------------------------------------------
One thing it worries me about this approach is that it is adding quite a lot of
complexity and a performance penalty on the {{relate}} methods, even for
INTERSECTS queries. I think the problem here is not so much the mathematical
accuracy to know if an edge terminates in another but encoding/decoding
distortion of those edges.
In your original example we take an edge of an indexed polygon, for example
LINESTRING(1 0, 2 0), then after encoding/decoding the edge becomes
LINESTRING(0.9999999403953552 0,1.9999999646097422 0). On the other hand the
query polygon contains the edge LINESTRING(0 0, 7 0). Therefore indexed and
query polygons shared the edge because the latitude value does not change
during encoding/decoding and the logic you propose handles the situation. I
think this is an exception more than the general case.
If the indexed edge is LINESTRING(1 1, 2 1), then after encoding/decoding the
edge becomes LINESTRING( 0.9999999403953552
0.9999999823048711,1.9999999646097422 0.9999999823048711). The query polygon
contains the edge LINESTRING(1 0, 1 7) which is not a shared edge anymore
because the latitude value has changed and the new logic has no effect. I think
this is the general case.
I am more inclined to leave the {{relate}} logic simple and fast and solve this
edge cases in a different way. One of the ideas I am thinking about is to use
some adaptive decoding. In this case INTERSECTS and DISJOINT queries work as
they do now. For WITHIN queries we decode the indexed triangles minimising the
area they cover by rounding up min values and rounding down max values. This
seems to work well when triangles have an area (not points or lines).
was (Author: ivera):
One thing it worries me about this approach is that it is adding quite a lot of
complexity and a performance penalty on the {{relate}} methods, even for
INTERSECTS queries. I think the problem here is not so much the mathematical
accuracy to know if an edge terminates in another but encoding/decoding
distortion of those edges.
In your original example we take an edge of an indexed polygon, for example
LINESTRING(1 0, 2 0), then after encoding and decoding the edge becomes
LINESTRING(0.9999999403953552 0,1.9999999646097422 0). On the other hand the
query polygon contains the edge LINESTRING(0 0, 7 0). Therefore indexed and
query polygons shared the edge because the latitude value does not change one
decoding and the logic you propose handles the situation. I think this is an
exception more than the general case.
For example If the indexed edge is LINESTRING(1 1, 2 1), then after encoding
and decoding the edge becomes LINESTRING( 0.9999999403953552
0.9999999823048711,1.9999999646097422 0.9999999823048711). The query polygon
contains the edge LINESTRING(1 0, 1 7) which is not a shared edge anymore
because the latitude value has changed and the new logic has no effect. I think
this is the general case.
I am more inclined to leave the {{relate}} logic simple and fast and solve this
edge cases in a different way. One of the ideas I am thinking about is to use
some adaptive decoding. In this case INTERSECTS and DISJOINT queries work as
they do now. For WITHIN queries we decode the indexed triangles minimising the
area they cover by rounding up min values and rounding down max values. This
seems to work well when triangles have an area (not points or lines).
> 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: [email protected]
For additional commands, e-mail: [email protected]
