geos::shape::fractal::HilbertCode Class Reference

`#include <HilbertCode.h>`

## Static Public Member Functions

static geom::Coordinate | decode (uint32_t level, uint32_t i)
static uint32_t | encode (uint32_t level, uint32_t x, uint32_t y)
static uint32_t | levelSize (uint32_t level)
static uint32_t | maxOrdinate (uint32_t level)
static uint32_t | level (uint32_t numPoints)

## Static Public Attributes

static constexpr int | MAX_LEVEL = 16

## Detailed Description

Encodes points as the index along finite planar Hilbert curves.

The planar Hilbert Curve is a continuous space-filling curve. In the limit the Hilbert curve has infinitely many vertices and fills the space of the unit square. A sequence of finite approximations to the infinite Hilbert curve is defined by the level number. The finite Hilbert curve at level n H(n) contains 2^n+1 points. Each finite Hilbert curve defines an ordering of the points in the 2-dimensional range square containing the curve. Curves fills the range square of side 2^level. Curve points have ordinates in the range [0, 2^level - 1]. The index of a point along a Hilbert curve is called the Hilbert code. The code for a given point is specific to the level chosen.

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

The Hilbert 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 Hilbert order is an effective way of linearizing space to support range queries.

Author
  Martin Davis

See also
  MortonCode

## Member Function Documentation

## level()

uint32_t geos::shape::fractal::HilbertCode::level | ( | uint32_t | numPoints | ) |

static

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

Parameters

  numPoints | the number of points required

Returns
  the level of the curve

References level().

Referenced by level(), levelSize(), and maxOrdinate().

## levelSize()

uint32_t geos::shape::fractal::HilbertCode::levelSize | ( | uint32_t | level | ) |

static

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

References level().

## maxOrdinate()

uint32_t geos::shape::fractal::HilbertCode::maxOrdinate | ( | uint32_t | level | ) |

static

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

References level().

## Member Data Documentation

## MAX_LEVEL

int geos::shape::fractal::HilbertCode::MAX_LEVEL = 16

static constexpr

The maximum curve level that can be represented.

The documentation for this class was generated from the following file:

- HilbertCode.h