[
https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15252856#comment-15252856
]
Robert Muir commented on LUCENE-7239:
-------------------------------------
I think most of the logN solutions are too tricky: of course if we can
implement one for 2D and it outperforms this, we can throw this stuff out for
it.
But the logN datastructures i looked at involved tricky calculations (and I
don't want to introduce error): whereas this one is doing "obviously" the same
thing as the slower versions it replaces: since the optimizatation is only
based on comparisons, which are exact, and its the same comparisons the slow
versions do in the iteration of each loop.
I also have the concerns about those complicated logN datastructures
introducing a high overhead (echoed here in "Faster Tests":
http://erich.realtimerendering.com/ptinpoly/) that might mean they are
impractical. Another thing i really am trying to keep is "one codepath" without
specialization for different types of polygons in any way. This makes it easier
to understand what the adversaries are.
We just have to keep in mind this stuff here is still linear time, but I think
its a practical improvement. So maybe there is a similar more 1980s approach
for geo3d that is "good enough" but not too complicated there as well.
> Speed up LatLonPoint's polygon queries when there are many vertices
> -------------------------------------------------------------------
>
> Key: LUCENE-7239
> URL: https://issues.apache.org/jira/browse/LUCENE-7239
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Robert Muir
> Attachments: LUCENE-7239.patch
>
>
> This is inspired by the "reliability and numerical stability" recommendations
> at the end of http://www-ma2.upc.es/geoc/Schirra-pointPolygon.pdf.
> Basically our polys need to answer two questions that are slow today:
> contains(point)
> crosses(rectangle)
> Both of these ops only care about a subset of edges: the ones overlapping a y
> interval range. We can organize these edges in an interval tree to be
> practical and speed things up a lot. Worst case is still O(n) but those
> solutions are more complex to do.
--
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
