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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org