Class PackedQuadPrefixTree
- java.lang.Object
-
- org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree
-
- org.apache.lucene.spatial.prefix.tree.QuadPrefixTree
-
- org.apache.lucene.spatial.prefix.tree.PackedQuadPrefixTree
-
public class PackedQuadPrefixTree extends QuadPrefixTree
Uses a compact binary representation of 8 bytes to encode a spatial quad trie.The binary representation is as follows:
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDL Where C = Cell bits (2 per quad) D = Depth bits (5 with max of 29 levels) L = isLeaf bit
It includes a built-in "pruneLeafyBranches" setting (true by default) similar toRecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean)
although this one only prunes at the target detail level (where it has the most effect). Usually you should disable RPT's prune, since it is very memory in-efficient.- WARNING: This API is experimental and might change in incompatible ways in the next release.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
PackedQuadPrefixTree.Factory
Factory for creatingPackedQuadPrefixTree
instances with useful defaults.protected class
PackedQuadPrefixTree.PackedQuadCell
See binary representation in the javadocs ofPackedQuadPrefixTree
.protected class
PackedQuadPrefixTree.PrefixTreeIterator
This is a streamlined version of TreeCellIterator, with built-in support to prune at detailLevel (but not recursively upwards).-
Nested classes/interfaces inherited from class org.apache.lucene.spatial.prefix.tree.QuadPrefixTree
QuadPrefixTree.QuadCell
-
-
Field Summary
Fields Modifier and Type Field Description protected boolean
leafyPrune
static int
MAX_LEVELS_POSSIBLE
protected static byte[]
QUAD
-
Fields inherited from class org.apache.lucene.spatial.prefix.tree.QuadPrefixTree
DEFAULT_MAX_LEVELS, gridH, gridW, robust, xmax, xmid, xmin, ymax, ymid, ymin
-
Fields inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree
ctx, maxLevels
-
-
Constructor Summary
Constructors Constructor Description PackedQuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
buildNotRobustly(double x, double y, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
protected void
checkBattenbergNotRobustly(byte quad, double cx, double cy, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
Cell
getCell(org.locationtech.spatial4j.shape.Point p, int level)
Returns the cell containing pointp
at the specifiedlevel
.double
getDistanceForLevel(int level)
Given a cell having the specified level, returns the distance from opposite corners.CellIterator
getTreeCellIterator(org.locationtech.spatial4j.shape.Shape shape, int detailLevel)
Gets the intersecting cells for the specified shape, without exceeding detail level.Cell
getWorldCell()
Returns the level 0 cell which encompasses all spatial data.boolean
isPruneLeafyBranches()
Cell
readCell(BytesRef term, Cell scratch)
This creates a new Cell (or re-usingscratch
if provided), initialized to the state as read by the bytes.void
setPruneLeafyBranches(boolean pruneLeafyBranches)
LikeRecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean)
but more memory efficient and only applies to the detailLevel, where it has the most effect.String
toString()
-
Methods inherited from class org.apache.lucene.spatial.prefix.tree.QuadPrefixTree
battenberg, checkBattenbergNotRobustly, getLevelForDistance, printInfo
-
Methods inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree
getMaxLevels, getSpatialContext
-
-
-
-
Field Detail
-
MAX_LEVELS_POSSIBLE
public static final int MAX_LEVELS_POSSIBLE
- See Also:
- Constant Field Values
-
QUAD
protected static final byte[] QUAD
-
leafyPrune
protected boolean leafyPrune
-
-
Method Detail
-
toString
public String toString()
- Overrides:
toString
in classSpatialPrefixTree
-
getWorldCell
public Cell getWorldCell()
Description copied from class:SpatialPrefixTree
Returns the level 0 cell which encompasses all spatial data. Equivalent toSpatialPrefixTree.readCell(BytesRef,Cell)
with no bytes.- Overrides:
getWorldCell
in classQuadPrefixTree
-
getCell
public Cell getCell(org.locationtech.spatial4j.shape.Point p, int level)
Returns the cell containing pointp
at the specifiedlevel
.- Overrides:
getCell
in classQuadPrefixTree
-
buildNotRobustly
protected void buildNotRobustly(double x, double y, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
-
checkBattenbergNotRobustly
protected void checkBattenbergNotRobustly(byte quad, double cx, double cy, int level, List<Cell> matches, long term, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
-
readCell
public Cell readCell(BytesRef term, Cell scratch)
Description copied from class:SpatialPrefixTree
This creates a new Cell (or re-usingscratch
if provided), initialized to the state as read by the bytes. Warning: An implementation may refer to the same byte array (no copy). IfCell.setLeaf()
is subsequently called, it would then modify these bytes.
-
getTreeCellIterator
public CellIterator getTreeCellIterator(org.locationtech.spatial4j.shape.Shape shape, int detailLevel)
Description copied from class:SpatialPrefixTree
Gets the intersecting cells for the specified shape, without exceeding detail level. If a cell is within the query shape then it's marked as a leaf and none of its children are added. For cells at detailLevel, they are marked as leaves too, unless it's a point.IMPORTANT: Cells returned from the iterator can be re-used for cells at the same level. So you can't simply iterate to subsequent cells and still refer to the former cell nor the bytes returned from the former cell, unless you know the former cell is a parent.
- Parameters:
shape
- the shape; possibly null but the caller should liberally callremove()
if so.detailLevel
- the maximum detail level to get cells for- Returns:
- the matching cells
-
isPruneLeafyBranches
public boolean isPruneLeafyBranches()
-
setPruneLeafyBranches
public void setPruneLeafyBranches(boolean pruneLeafyBranches)
LikeRecursivePrefixTreeStrategy.setPruneLeafyBranches(boolean)
but more memory efficient and only applies to the detailLevel, where it has the most effect.
-
getDistanceForLevel
public double getDistanceForLevel(int level)
Description copied from class:SpatialPrefixTree
Given a cell having the specified level, returns the distance from opposite corners. Since this might vary depending on where the cell is, this method may over-estimate.- Specified by:
getDistanceForLevel
in classSpatialPrefixTree
- Parameters:
level
- [1 to maxLevels]- Returns:
> 0
-
-