Robert Muir created LUCENE-7239:
-----------------------------------
Summary: 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
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: [email protected]
For additional commands, e-mail: [email protected]
