Description
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 but those solutions are more complex to do.
Attachments
Attachments
Issue Links
- is part of
-
LUCENE-7159 improve spatial point/rect vs. polygon performance
- Closed