[
https://issues.apache.org/jira/browse/LUCENE-7229?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15246505#comment-15246505
]
Nicholas Knize commented on LUCENE-7229:
----------------------------------------
bq. Well it fails the tests which have nothing to do with BKD or anything else
With Large rectangles (i.e. those that can be created either by BKD inner nodes
or generated by a test) the earth's curvature may have an effect such that an
edge of the box can cross the edge of a polygon. This is the same effect seen
in the distance queries and it will not be caught using 2d cartesian math.
> 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
