[ https://issues.apache.org/jira/browse/LUCENE-7159?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15224498#comment-15224498 ]
ASF subversion and git services commented on LUCENE-7159: --------------------------------------------------------- Commit c1a3e1b8d04ffc94e502b086e0544c0e0494d5a8 in lucene-solr's branch refs/heads/master from [~rcmuir] [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=c1a3e1b ] 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org