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
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 bitIt includes a built-in "pruneLeafyBranches" setting (true by default) similar to
RecursivePrefixTreeStrategy.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
Modifier and TypeClassDescriptionstatic class
Factory for creatingPackedQuadPrefixTree
instances with useful defaults.protected class
See binary representation in the javadocs ofPackedQuadPrefixTree
.protected class
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
Modifier and TypeFieldDescriptionprotected boolean
static final int
protected static final byte[]
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
ConstructorDescriptionPackedQuadPrefixTree
(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels) -
Method Summary
Modifier and TypeMethodDescriptionprotected 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) 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.getTreeCellIterator
(org.locationtech.spatial4j.shape.Shape shape, int detailLevel) Gets the intersecting cells for the specified shape, without exceeding detail level.Returns the level 0 cell which encompasses all spatial data.boolean
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.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 Details
-
MAX_LEVELS_POSSIBLE
public static final int MAX_LEVELS_POSSIBLE- See Also:
-
QUAD
protected static final byte[] QUAD -
leafyPrune
protected boolean leafyPrune
-
-
Constructor Details
-
PackedQuadPrefixTree
public PackedQuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels)
-
-
Method Details
-
toString
- Overrides:
toString
in classSpatialPrefixTree
-
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
Returns the cell containing pointp
at the specifiedlevel
.- Overrides:
getCell
in classQuadPrefixTree
-
buildNotRobustly
-
checkBattenbergNotRobustly
-
readCell
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
-