[
https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15252755#comment-15252755
]
Karl Wright commented on LUCENE-7239:
-------------------------------------
Indeed, very impressive speed-up. Are you using the same borough polygons I am
looking at, where the total vertex count is 186,000 or thereabouts?
For geo3d, I would love to be able to do some similar edge tree construction,
but I don't yet have a firm idea what the tree hierarchy criteria would be.
Can't split on latitude, that's for sure. Maybe the z in (x,y,z)?
> 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
