org.locationtech.jts.shape.fractal

Class MortonCode

java.lang.Object

org.locationtech.jts.shape.fractal.MortonCode

public class MortonCode
extends Object

Encodes points as the index along the planar Morton (Z-order) curve.

The planar Morton (Z-order) curve is a continuous space-filling curve. The Morton curve defines an ordering of the points in the positive quadrant of the plane. The index of a point along the Morton curve is called the Morton code.

A sequence of subsets of the Morton curve can be defined by a level number. Each level subset occupies a square range. The curve at level n M_n contains 2^{n + 1} points. It fills the range square of side 2^level. Curve points have ordinates in the range [0, 2^level - 1]. The code for a given point is identical at all levels. The level simply determines the number of points in the curve subset and the size of the range square.

This implementation represents codes using 32-bit integers. This allows levels 0 to 16 to be handled. The class supports encoding points and decoding the point for a given code value.

The Morton order has the property that it tends to preserve locality. This means that codes which are near in value will have spatially proximate points. The converse is not always true - the delta between codes for nearby points is not always small. But the average delta is small enough that the Morton order is an effective way of linearizing space to support range queries.

Author:

Martin Davis

See Also:

MortonCurveBuilder, HilbertCode

Field Summary

Fields

Modifier and Type	Field and Description
static int	MAX_LEVEL The maximum curve level that can be represented.

Constructor Summary

Constructors

Constructor and Description
MortonCode()

Method Summary

Modifier and Type	Method and Description
static Coordinate	decode(int index) Computes the point on the Morton curve for a given index.
static int	encode(int x, int y) Computes the index of the point (x,y) in the Morton curve ordering.
static int	level(int numPoints) The level of the finite Morton curve which contains at least the given number of points.
static int	maxOrdinate(int level) The maximum ordinate value for points in the curve for the given level.
static int	size(int level) The number of points in the curve for the given level.

Methods inherited from class java.lang.Object

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

Field Detail

MAX_LEVEL

public static final int MAX_LEVEL

The maximum curve level that can be represented.

See Also:

Constant Field Values

Constructor Detail

MortonCode

public MortonCode()

Method Detail

size

public static int size(int level)

The number of points in the curve for the given level. The number of points is 2^{2 * level}.

Parameters:

level - the level of the curve

Returns:

the number of points

maxOrdinate

public static int maxOrdinate(int level)

The maximum ordinate value for points in the curve for the given level. The maximum ordinate is 2^level - 1.

Parameters:

level - the level of the curve

Returns:

the maximum ordinate value

level

public static int level(int numPoints)

The level of the finite Morton curve which contains at least the given number of points.

Parameters:

numPoints - the number of points required

Returns:

the level of the curve

encode

public static int encode(int x,
                         int y)

Computes the index of the point (x,y) in the Morton curve ordering.

Parameters:

x - the x ordinate of the point

y - the y ordinate of the point

Returns:

the index of the point along the Morton curve

decode

public static Coordinate decode(int index)

Computes the point on the Morton curve for a given index.

Parameters:

index - the index of the point on the curve

Returns:

the point on the curve