[
https://issues.apache.org/jira/browse/LUCENE-7159?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15224504#comment-15224504
]
ASF subversion and git services commented on LUCENE-7159:
---------------------------------------------------------
Commit 1113443fc683d80720efd42706cb932b00f2cba8 in lucene-solr's branch
refs/heads/branch_6x from [~rcmuir]
[ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=1113443 ]
LUCENE-7159: Speed up LatLonPoint point-in-polygon performance
> 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
> Attachments: LUCENE-7159.patch, LUCENE-7159.patch
>
>
> 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]
