org.apache.lucene.spatial.prefix.tree
Class SpatialPrefixTree

java.lang.Object
  extended by org.apache.lucene.spatial.prefix.tree.SpatialPrefixTree
Direct Known Subclasses:
GeohashPrefixTree, QuadPrefixTree

public abstract class SpatialPrefixTree
extends Object

A spatial Prefix Tree, or Trie, which decomposes shapes into prefixed strings at variable lengths corresponding to variable precision. Each string corresponds to a rectangular spatial region. This approach is also referred to "Grids", "Tiles", and "Spatial Tiers".

Implementations of this class should be thread-safe and immutable once initialized.

WARNING: This API is experimental and might change in incompatible ways in the next release.

Field Summary
protected  com.spatial4j.core.context.SpatialContext ctx
           
protected  int maxLevels
           
protected static Charset UTF8
           
 
Constructor Summary
SpatialPrefixTree(com.spatial4j.core.context.SpatialContext ctx, int maxLevels)
           
 
Method Summary
static List<String> cellsToTokenStrings(Collection<Cell> cells)
          Will add the trailing leaf byte for leaves.
abstract  Cell getCell(byte[] bytes, int offset, int len)
           
 Cell getCell(byte[] bytes, int offset, int len, Cell target)
           
protected  Cell getCell(com.spatial4j.core.shape.Point p, int level)
          Returns the cell containing point p at the specified level.
abstract  Cell getCell(String token)
          The cell for the specified token.
 List<Cell> getCells(com.spatial4j.core.shape.Point p, int detailLevel, boolean inclParents)
          A Point-optimized implementation of getCells(com.spatial4j.core.shape.Shape, int, boolean, boolean).
 List<Cell> getCells(com.spatial4j.core.shape.Shape shape, int detailLevel, boolean inclParents, boolean simplify)
          Gets the intersecting cells for the specified shape, without exceeding detail level.
 double getDistanceForLevel(int level)
          Given a cell having the specified level, returns the distance from opposite corners.
abstract  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).
 int getMaxLevels()
           
 com.spatial4j.core.context.SpatialContext getSpatialContext()
           
 Cell getWorldCell()
          Returns the level 0 cell which encompasses all spatial data.
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

UTF8

protected static final Charset UTF8

maxLevels

protected final int maxLevels

ctx

protected final com.spatial4j.core.context.SpatialContext ctx
Constructor Detail

SpatialPrefixTree

public SpatialPrefixTree(com.spatial4j.core.context.SpatialContext ctx,
                         int maxLevels)
Method Detail

getSpatialContext

public com.spatial4j.core.context.SpatialContext getSpatialContext()

getMaxLevels

public int getMaxLevels()

toString

public String toString()
Overrides:
toString in class Object

getLevelForDistance

public abstract 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). 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.

Parameters:
dist - >= 0
Returns:
level [1 to maxLevels]

getDistanceForLevel

public double getDistanceForLevel(int level)
Given a cell having the specified level, returns the distance from opposite corners. Since this might very depending on where the cell is, this method may over-estimate.

Parameters:
level - [1 to maxLevels]
Returns:
> 0

getWorldCell

public Cell getWorldCell()
Returns the level 0 cell which encompasses all spatial data. Equivalent to getCell(String) with "". This cell is threadsafe, just like a spatial prefix grid is, although cells aren't generally threadsafe. TODO rename to getTopCell or is this fine?


getCell

public abstract Cell getCell(String token)
The cell for the specified token. The empty string should be equal to getWorldCell(). Precondition: Never called when token length > maxLevel.


getCell

public abstract Cell getCell(byte[] bytes,
                             int offset,
                             int len)

getCell

public final Cell getCell(byte[] bytes,
                          int offset,
                          int len,
                          Cell target)

getCell

protected Cell getCell(com.spatial4j.core.shape.Point p,
                       int level)
Returns the cell containing point p at the specified level.


getCells

public List<Cell> getCells(com.spatial4j.core.shape.Shape shape,
                           int detailLevel,
                           boolean inclParents,
                           boolean simplify)
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.

This implementation checks if shape is a Point and if so returns getCells(com.spatial4j.core.shape.Point, int, boolean).

Parameters:
shape - the shape; non-null
detailLevel - the maximum detail level to get cells for
inclParents - if true then all parent cells of leaves are returned too. The top world cell is never returned.
simplify - for non-point shapes, this will simply/aggregate sets of complete leaves in a cell to its parent, resulting in ~20-25% fewer cells.
Returns:
a set of cells (no dups), sorted, immutable, non-null

getCells

public List<Cell> getCells(com.spatial4j.core.shape.Point p,
                           int detailLevel,
                           boolean inclParents)
A Point-optimized implementation of getCells(com.spatial4j.core.shape.Shape, int, boolean, boolean). That method in facts calls this for points.

This implementation depends on getCell(String) being fast, as its called repeatedly when incPlarents is true.


cellsToTokenStrings

public static List<String> cellsToTokenStrings(Collection<Cell> cells)
Will add the trailing leaf byte for leaves. This isn't particularly efficient.



Copyright © 2000-2013 Apache Software Foundation. All Rights Reserved.