[
https://issues.apache.org/jira/browse/LUCENE-7229?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15246558#comment-15246558
]
Nicholas Knize edited comment on LUCENE-7229 at 4/18/16 9:18 PM:
-----------------------------------------------------------------
bq. Its absolutely unrelated to polygons completely here.
Well actually it is related since {{numberOfCorners}} first checks if all 4
corners are contained in the polygon (which in this test returns 4). Then the
diagonal optimization is used incorrectly in this example test because its
called after {{numberOfCorners}}. So of course this test will fail because the
candidate cell crosses a diagonal. Its being applied in the wrong spot.
Nevertheless, it doesn't really matter. I was originally stating agreement with
the provided orientation approach since it provided a nice performance boost in
5.5 for {{GeoPointField}}.
was (Author: nknize):
bq. Its absolutely unrelated to polygons completely here.
Well actually it is related since {{numberOfCorners}} first checks if all 4
corners are contained in the polygon (which in this test returns 4). Then the
diagonal optimization is used incorrectly in this example test because its
called after {{numberOfCorners}}. So of course this test will fail because the
candidate cell crosses a diagonal. Its being tested in the wrong spot.
Nevertheless, it doesn't really matter. I was originally stating agreement with
the provided orientation approach since it provided a nice performance boost in
5.5 for {{GeoPointField}}.
> 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
