Class 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 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.
  • 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

      public String toString()
      Overrides:
      toString in class SpatialPrefixTree
    • getWorldCell

      public Cell getWorldCell()
      Description copied from class: SpatialPrefixTree
      Returns the level 0 cell which encompasses all spatial data. Equivalent to SpatialPrefixTree.readCell(BytesRef,Cell) with no bytes.
      Overrides:
      getWorldCell in class QuadPrefixTree
    • getCell

      public Cell getCell(org.locationtech.spatial4j.shape.Point p, int level)
      Returns the cell containing point p at the specified level.
      Overrides:
      getCell in class QuadPrefixTree
    • 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-using scratch if provided), initialized to the state as read by the bytes. Warning: An implementation may refer to the same byte array (no copy). If Cell.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 call remove() 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)
      Like RecursivePrefixTreeStrategy.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 class SpatialPrefixTree
      Parameters:
      level - [1 to maxLevels]
      Returns:
      > 0