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 and Description
static class	QuadPrefixTree.Factory Factory for creating QuadPrefixTree instances with useful defaults
protected class	QuadPrefixTree.QuadCell

Field Summary

Fields

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

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

ctx, maxLevels

Constructor Summary

Constructors

Constructor and 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 and 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 Detail

MAX_LEVELS_POSSIBLE

public static final int MAX_LEVELS_POSSIBLE

See Also:

Constant Field Values

DEFAULT_MAX_LEVELS

public static final int DEFAULT_MAX_LEVELS

See Also:

Constant Field Values

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 Detail

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 Detail

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