[
https://issues.apache.org/jira/browse/LUCENE-7239?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15252776#comment-15252776
]
Robert Muir commented on LUCENE-7239:
-------------------------------------
{quote}
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?
{quote}
Yes, I'm using {{-points -polyMedium}} from the luceneutil benchmark. Total
vertex count is 186318.
Note that this solution is still sandy. Imagine the russia polygon from
geonames where you have 1000 components (one for each island). This will still
be slow, because we don't yet "squash" the polygon all into one gon with
separators. Our algorithms support that, but we'd still have to keep an
additional tree of just the holes to answer CELL_OUTSIDE_QUERY when its fully
contained in the holes. Also i want to make sure it doesn't blow the tree all
to hell. Followup :)
{quote}
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)?
{quote}
See https://en.wikipedia.org/wiki/Interval_tree#Higher_dimensions_2 for some
discussion. I am not as familiar with how the 3D polygon algorithms work though
to offer anything intelligent. I'm still fighting with 2D :)
> 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
