Class HilbertCode


  • public class HilbertCode
    extends java.lang.Object
    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 Hn contains 2n + 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 2level. Curve points have ordinates in the range [0, 2level - 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:
    HilbertCurveBuilder, MortonCode
    • Field Summary

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

      Constructors 
      Constructor Description
      HilbertCode()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static Coordinate decode​(int level, int index)
      Computes the point on a Hilbert curve of given level for a given code index.
      static int encode​(int level, int x, int y)
      Encodes a point (x,y) in the range of the the Hilbert curve at a given level as the index of the point along the curve.
      static int level​(int numPoints)
      The level of the finite Hilbert 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

      • HilbertCode

        public HilbertCode()
    • 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 22 * 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 2level - 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 Hilbert 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 level,
                                 int x,
                                 int y)
        Encodes a point (x,y) in the range of the the Hilbert curve at a given level as the index of the point along the curve. The index will lie in the range [0, 2level + 1].
        Parameters:
        level - the level of the Hilbert curve
        x - the x ordinate of the point
        y - the y ordinate of the point
        Returns:
        the index of the point along the Hilbert curve
      • decode

        public static Coordinate decode​(int level,
                                        int index)
        Computes the point on a Hilbert curve of given level for a given code index. The point ordinates will lie in the range [0, 2level - 1].
        Parameters:
        level - the Hilbert curve level
        index - the index of the point on the curve
        Returns:
        the point on the Hilbert curve