org.geolatte.geom.curve

Class MortonCode<P extends C2D>

java.lang.Object

org.geolatte.geom.curve.MortonCode<P>

public class MortonCode<P extends C2D>
extends java.lang.Object

Calculates the Morton code (Morton-order or Z-order) of Geometries

Morton codes are labels for the nodes of a QuadTree. A QuadTree is a partition of a spatial extent by recursively decomposing it into four equal quadrants. A QuadTree is determined by a spatial extent and depth of the tree (the number of recursive subdivisions of the extent). Both are specified by the MortonContext passed during construction of instances of this class.

The Morton code of a Geometry can be viewed as a path to the quadrant containing the envelope of that Geometry. The left-most character of the code contains the label of the quadrant at depth 1, the second at depth 2, etc. If the Morton code is the empty string, then the envelope fits in no single quandrant of the QuadTree.

At each level the four quadrants are labeled:

• O : lower-left quadrant
• 1 : upper-left quadrant
• 2 : lower-right quadrant
• 3 : upper-right quadrant

Field Summary

Fields

Modifier and Type	Field and Description
private double	gridHeight The height of the leaves of the quadtree implied by the MortonContext
private double	gridWidth The width of the leaves of the quadtree implied by the MortonContext
private int	maxGridCellCoordinate
private MortonContext<P>	mortonContext
private java.util.regex.Pattern	VALID_MORTONCODE_PATTERN

Constructor Summary

Constructors

Constructor and Description
MortonCode(MortonContext<P> mortonContext) Constructs an instance with the given Mortoncontext

Method Summary

Modifier and Type	Method and Description
private void	checkForNull(java.lang.Object object)
private void	checkWithinExtent(Envelope<P> envelope)
private void	checkWithinExtent(P pos)
private java.lang.String	commonMortonCodePrefixAsString(long mc1, long mc2) Returns the common prefix of two morton codes.
Envelope<P>	envelopeOf(java.lang.String mortoncode) Returns the extent that corresponds to the specified morton code
private Envelope<P>	envelopeOf(java.lang.String mortoncode, int index, Envelope<P> extent)
private int	getCol(double x)
int	getMaxLength() Returns the maximum length of a morton code generated by this instance.
private int	getRow(double y)
private long	interleave(int col, int row)
private boolean	isValidMortonCode(java.lang.String mortoncode)
java.lang.String	ofEnvelope(Envelope<P> envelope) Returns the Morton code for the specified Envelope.
java.lang.String	ofGeometry(Geometry<P> geometry) Returns the Morton code for the specified Geometry.
java.lang.String	ofPosition(P pos) Returns the Morton code for the specified Point.
private java.lang.String	pointMortonCodeAsString(long interleaved)
private java.lang.String	toRadix4String(long interleaved, int level) Transforms the morton code long value into a string such that each character is a label for the quadrant.

Methods inherited from class java.lang.Object

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

Field Detail

VALID_MORTONCODE_PATTERN

private final java.util.regex.Pattern VALID_MORTONCODE_PATTERN

mortonContext

private final MortonContext<P extends C2D> mortonContext

gridWidth

private final double gridWidth

The width of the leaves of the quadtree implied by the MortonContext

gridHeight

private final double gridHeight

The height of the leaves of the quadtree implied by the MortonContext

maxGridCellCoordinate

private final int maxGridCellCoordinate

Constructor Detail

MortonCode

public MortonCode(MortonContext<P> mortonContext)

Constructs an instance with the given Mortoncontext

The specified MortonCode determines a QuadTree for which this instance calculates labels.

Parameters:

mortonContext - the context to use when calculating morton codes.

Method Detail

ofGeometry

public java.lang.String ofGeometry(Geometry<P> geometry)

Returns the Morton code for the specified Geometry.

This method is equivalent to ofEnvelope(geometry.getEnvelope()).

Parameters:

geometry - a {code Geometry} value.

Returns:

the morton code for the envelope of the specified Geometry.

Throws:

java.lang.IllegalArgumentException - if the geometry is null, or has an envelope which is not contained in the spatial extent of this instance's MortonContext

ofEnvelope

public java.lang.String ofEnvelope(Envelope<P> envelope)

Returns the Morton code for the specified Envelope.

Parameters:

envelope - an Envelope value.

Returns:

the morton code for the specified Envelope value.

Throws:

java.lang.IllegalArgumentException - if the value of the envelope parameter is null, or is not contained in the spatial extent of this instance's MortonContext

ofPosition

public java.lang.String ofPosition(P pos)

Returns the Morton code for the specified Point.

Parameters:

pos - an Point value.

Returns:

the morton code for the specified Point value.

Throws:

java.lang.IllegalArgumentException - if the value of the point parameter is null, or is not contained in the spatial extent of this instance's MortonContext

getMaxLength

public int getMaxLength()

Returns the maximum length of a morton code generated by this instance.

Returns:

the maximum length of a morton code generated by this instance.

envelopeOf

public Envelope<P> envelopeOf(java.lang.String mortoncode)

Returns the extent that corresponds to the specified morton code

Parameters:

mortoncode - a morton code String

Returns:

the envelope representing the specified morton code

envelopeOf

private Envelope<P> envelopeOf(java.lang.String mortoncode,
                               int index,
                               Envelope<P> extent)

isValidMortonCode

private boolean isValidMortonCode(java.lang.String mortoncode)

getRow

private int getRow(double y)

getCol

private int getCol(double x)

checkWithinExtent

private void checkWithinExtent(P pos)

checkWithinExtent

private void checkWithinExtent(Envelope<P> envelope)

interleave

private long interleave(int col,
                        int row)

pointMortonCodeAsString

private java.lang.String pointMortonCodeAsString(long interleaved)

commonMortonCodePrefixAsString

private java.lang.String commonMortonCodePrefixAsString(long mc1,
                                                        long mc2)

Returns the common prefix of two morton codes.

The common prefix is the morton code for the quadtree node that is the common ancestor node for the nodes specified by the argument morton codes.

Parameters:

mc1 - first mortonCode (as an interleaved long)

mc2 - second mortonCode

Returns:

the common prefix of the specified morton codes

toRadix4String

private java.lang.String toRadix4String(long interleaved,
                                        int level)

Transforms the morton code long value into a string such that each character is a label for the quadrant.

(note: Long.toString(interleaved, 4) was not used since this turns morton code '001' into '1')

Parameters:

interleaved - the morton code as a long

level - the level of the morton code

Returns:

a String representation of the MortonCode

checkForNull

private void checkForNull(java.lang.Object object)