[
https://issues.apache.org/jira/browse/LUCENE-7159?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15221060#comment-15221060
]
Robert Muir commented on LUCENE-7159:
-------------------------------------
Note: for the second "tree traversal" part we might already have better
algorithms in git: when I added the Polygon class in LUCENE-7153 it used the
exact algorithms (for some reason GeoPoint was using different approximate ones
with less guarantees).
But these guarantees might be compatible yet still with those approximate
methods: the thing that is missing is edge case testing for these operations.
If they are faster and still safe (or can be easily made safe), maybe we should
restore them and cut the polygon class over to them!
These tests don't need to be complicated, e.g. for multipolygon/hole support I
added this one
(https://github.com/apache/lucene-solr/blob/81c83b443182cb5869079924637a4d43e9e7917e/lucene/spatial/src/test/org/apache/lucene/spatial/util/TestPolygon.java#L63-L91).
We can add randomized tests too: but we don't need to index lucene documents
or perform searches to do this and it will be more efficient and easier to
debug/improve things.
> improve spatial point/rect vs. polygon performance
> --------------------------------------------------
>
> Key: LUCENE-7159
> URL: https://issues.apache.org/jira/browse/LUCENE-7159
> Project: Lucene - Core
> Issue Type: Bug
> Reporter: Robert Muir
>
> Now that we can query on complex polygons without going OOM (LUCENE-7153), we
> should do something to address the current 🐢 performance.
> Currently, we use a basic crossings test ({{O\(n)}}) for boundary cases. We
> defer these expensive per-doc checks on boundary cases to a two phase
> iterator (LUCENE-7019, LUCENE-7109), so that it can be avoided if e.g.
> excluded by filters, conjunctions, deleted doc, and so on. This is currently
> important for performance, but basically its shoving the problem under the
> rug and hoping it goes away. At least for point in poly, there are a number
> of faster techniques described here:
> http://erich.realtimerendering.com/ptinpoly/
> Additionally I am not sure how costly our "tree traversal" (rectangle
> intersection algorithms). Maybe its nothing to be worried about, but likely
> it too gets bad if the thing gets complex enough. These don't need to be
> perfect but need to behave like java's Shape#contains (can conservatively
> return false), and Shape#intersects (can conservatively return true). Of
> course, if they are too inaccurate, then things can get slower.
> In cases of precomputed structures we should also consider memory usage: e.g.
> we shouldn't make a horrible tradeoff there.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
