Attached is a patch that implements a spatial "Within" predicate for RecursivePrefixTree.
Summary of changes in patch, which includes some unrelated things:
- Added SpatialPrefixTree.getDistanceForLevel(level):double – used by the Within filter to help it 'buffer' the query shape slightly
- Migrated AbstractPrefixTreeFilter to use FixedBitSet instead of OpenBitSet, because FBS is preferred in Lucene (paraphrasing Uwe)
- Moved some point vs rect interpretation of a cell from AbstractVisitingPrefixTreeFilter to subclass IntersectsPrefixTreeFilter since that logic is not applicable to Within
The test is randomized and thus fairly thorough, notwithstanding that it doesn't test a geospatial context. I'd like to add that but in order to do so, gridSnap would ideally use some utility classes/logic in Spatial4j trunk that isn't here. So I'll add that in the future.
The big thing missing here is that this Within predicate will sometimes match false-positives in cases where the indexed shape for a document is really multi* shape – i.e. is composed of multiple disjoint parts. I'd like to solve that separately using some sort of indexed field of center points of each disjoint part of indexed shapes. Maybe as a separate issue? But it would be nice to get this committed now, notwithstanding this interim limitation.