lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Robert Muir (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (LUCENE-7229) Improve Polygon.relate
Date Mon, 18 Apr 2016 20:20:25 GMT

    [ https://issues.apache.org/jira/browse/LUCENE-7229?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15246459#comment-15246459
] 

Robert Muir commented on LUCENE-7229:
-------------------------------------

I don't refer to the short cut... there are only 2 line-crosses-line calls in {{lineCrossesRect()}}.
that is the problem there: this is what caused test failures as soon as we improved random
polygon testing to test more than boxes.

> 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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message