[ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15254237#comment-15254237 ]
Robert Muir commented on LUCENE-7239: ------------------------------------- Just as a followup: the still-sluggish performance of the synthetic polys in the benchmarks here versus the "real" ones is mostly due to the actual luceneutil poly generation code in the benchmark itself: this is very slow. I will try to fix it so we can have a better understanding of when/where/how things degrade. > Speed up LatLonPoint's polygon queries when there are many vertices > ------------------------------------------------------------------- > > Key: LUCENE-7239 > URL: https://issues.apache.org/jira/browse/LUCENE-7239 > Project: Lucene - Core > Issue Type: Improvement > Reporter: Robert Muir > Fix For: master, 6.1 > > Attachments: LUCENE-7239.patch, LUCENE-7239.patch > > > This is inspired by the "reliability and numerical stability" recommendations > at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf. > Basically our polys need to answer two questions that are slow today: > contains(point) > crosses(rectangle) > Both of these ops only care about a subset of edges: the ones overlapping a y > interval range. We can organize these edges in an interval tree to be > practical and speed things up a lot. Worst case is still O(n) but those > solutions are more complex to do. -- 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