[ https://issues.apache.org/jira/browse/LUCENE-7229?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15246445#comment-15246445 ]
Ryan Ernst commented on LUCENE-7229: ------------------------------------ +1 to the new patch, thanks for the improved var names! > Improve Polygon.relate > ---------------------- > > Key: LUCENE-7229 > URL: https://issues.apache.org/jira/browse/LUCENE-7229 > Project: Lucene - Core > Issue Type: Improvement > Reporter: Robert Muir > Attachments: LUCENE-7229.patch, LUCENE-7229.patch > > > This method is currently quite slow and in many cases does more work than is > required. The speed actually directly impacts queries (tree traversal) and > bounds grid size to something tiny making it less effective. > I think we should replace it line intersections based on orientation methods > described here http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf and > https://www.cs.cmu.edu/~quake/robust.html > For one, a naive implementation is considerably faster than the method today: > both because it reduces the cost of BKD tree traversals and also because it > makes grid construction cheaper. This means we can increase its level of > detail with similar or lower startup cost. Now its more like a Mario Brothers > 2 picture of your polygon instead of Space Invaders. > Synthetic polygons from luceneUtil > ||vertices||old QPS||new QPS||old startup cost||new startup cost|| > |50|20.4|21.7|1ms|1ms| > |500|11.2|14.4|5ms|4ms| > |1000|7.4|10.0|9ms|8ms| > Real polygons (33 london districts: > http://data.london.gov.uk/2011-boundary-files) > ||vertices||old QPS||new QPS||old startup cost||new startup cost|| > |avg 5.6k|4.9|8.6|94ms|85ms| > But I also like using this method because its possible to extend it to remove > floating point error completely in the future with techniques described in > those links. This may be necessary if we want to do smarter things (e.g. not > linear time). -- 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