Package org.apache.lucene.spatial.prefix.tree

Class QuadPrefixTree

java.lang.Object
org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree
org.apache.lucene.spatial.prefix.tree.QuadPrefixTree
Direct Known Subclasses:
PackedQuadPrefixTree
public class QuadPrefixTree extends SpatialPrefixTree
A SpatialPrefixTree which uses a quad tree in which an indexed term will be generated for each cell, 'A', 'B', 'C', 'D'.
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 
    QuadPrefixTree.Factory
    Factory for creating QuadPrefixTree instances with useful defaults
    protected class 
    QuadPrefixTree.QuadCell
    individual QuadPrefixTree grid cell

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEFAULT_MAX_LEVELS
     
    final double
    gridH
     
    protected final double
    gridW
     
    static final int
    MAX_LEVELS_POSSIBLE
     
    protected boolean
    robust
     
    protected final double
    xmax
     
    protected final double
    xmid
     
    protected final double
    xmin
     
    protected final double
    ymax
     
    protected final double
    ymid
     
    protected final double
    ymin
     

    Fields inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

    ctx, maxLevels

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx)
     
    QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels)
     
    QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, org.locationtech.spatial4j.shape.Rectangle bounds, int maxLevels)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected int
    battenberg(double xmid, double ymid, double xp, double yp)
    Returns a Z-Order quadrant [0-3].
    protected void
    checkBattenbergNotRobustly(char c, double cx, double cy, int level, List<Cell> matches, BytesRef str, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)
     
    Cell
    getCell(org.locationtech.spatial4j.shape.Point p, int level)
    Returns the cell containing point p at the specified level.
    double
    getDistanceForLevel(int level)
    Given a cell having the specified level, returns the distance from opposite corners.
    int
    getLevelForDistance(double dist)
    Returns the level of the largest grid in which its longest side is less than or equal to the provided distance (in degrees).
    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.
    void
    printInfo(PrintStream out)
     
    Cell
    readCell(BytesRef term, Cell scratch)
    This creates a new Cell (or re-using scratch if provided), initialized to the state as read by the bytes.

    Methods inherited from class org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree

    getMaxLevels, getSpatialContext, toString

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • MAX_LEVELS_POSSIBLE

      public static final int MAX_LEVELS_POSSIBLE
      See Also:

    • DEFAULT_MAX_LEVELS

      public static final int DEFAULT_MAX_LEVELS
      See Also:

    • xmin

      protected final double xmin

    • xmax

      protected final double xmax

    • ymin

      protected final double ymin

    • ymax

      protected final double ymax

    • xmid

      protected final double xmid

    • ymid

      protected final double ymid

    • gridW

      protected final double gridW

    • gridH

      public final double gridH

    • robust

      protected boolean robust

  • Constructor Details

    • QuadPrefixTree

      public QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, org.locationtech.spatial4j.shape.Rectangle bounds, int maxLevels)

    • QuadPrefixTree

      public QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx)

    • QuadPrefixTree

      public QuadPrefixTree(org.locationtech.spatial4j.context.SpatialContext ctx, int maxLevels)

  • Method Details

    • 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.
      Specified by:
      getWorldCell in class SpatialPrefixTree

    • printInfo

      public void printInfo(PrintStream out)

    • getLevelForDistance

      public int getLevelForDistance(double dist)
      Description copied from class: SpatialPrefixTree
      Returns the level of the largest grid in which its longest side is less than or equal to the provided distance (in degrees). Consequently dist acts as an error epsilon declaring the amount of detail needed in the grid, such that you can get a grid with just the right amount of precision.
      Specified by:
      getLevelForDistance in class SpatialPrefixTree
      Parameters:
      dist - >= 0
      Returns:
      level [1 to maxLevels]

    • getCell

      public Cell getCell(org.locationtech.spatial4j.shape.Point p, int level)
      Returns the cell containing point p at the specified level.

    • checkBattenbergNotRobustly

      protected void checkBattenbergNotRobustly(char c, double cx, double cy, int level, List<Cell> matches, BytesRef str, org.locationtech.spatial4j.shape.Shape shape, int maxLevel)

    • battenberg

      protected int battenberg(double xmid, double ymid, double xp, double yp)
      Returns a Z-Order quadrant [0-3].

    • 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

    • 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.
      Specified by:
      readCell in class SpatialPrefixTree

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

      Overrides:
      getTreeCellIterator in class SpatialPrefixTree
      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