[jira] [Resolved] (LUCENE-7239) Speed up LatLonPoint's polygon queries when there are many vertices

["Robert Muir (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Robert Muir resolved LUCENE-7239.
---------------------------------
       Resolution: Fixed
    Fix Version/s: 6.1
                   master

> 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
>             Fix For: master, 6.1
>
>         Attachments: LUCENE-7239.patch, 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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org