[
https://issues.apache.org/jira/browse/LUCENE-7229?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Robert Muir resolved LUCENE-7229.
---------------------------------
Resolution: Fixed
Fix Version/s: 6.1
master
> Improve Polygon.relate
> ----------------------
>
> Key: LUCENE-7229
> URL: https://issues.apache.org/jira/browse/LUCENE-7229
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Robert Muir
> Fix For: master, 6.1
>
> 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: [email protected]
For additional commands, e-mail: [email protected]
