Robert Muir created LUCENE-7229:
-----------------------------------
Summary: Improve Polygon.relate
Key: LUCENE-7229
URL: https://issues.apache.org/jira/browse/LUCENE-7229
Project: Lucene - Core
Issue Type: Improvement
Reporter: Robert Muir
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]
