You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Robert Muir (JIRA)" <ji...@apache.org> on 2016/04/21 22:18:13 UTC
[jira] [Created] (LUCENE-7239) Speed up LatLonPoint's polygon
queries when there are many vertices
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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org