Class HilbertCurve

java.lang.Object
com.github.yellowstonegames.grid.HilbertCurve
public final class HilbertCurve extends Object
Calculates and stores 2D and optionally 3D Hilbert Curves up to a reasonable size. This can be used for various purposes, from creating a path in dungeon generation to optimizing certain kinds of compression that benefit from the qualities of a Hilbert Curve. A Hilbert Curve is, at its simplest, a way of passing through each point on a (typically square) grid without ever crossing its own path or taking a diagonal step. Hilbert Curves are self-similar, like many fractals; if you cut out a quarter of any large Hilbert Curve, the part cut out will be shaped similarly to the original Curve. The biggest area where Hilbert Curves find application is in applications that demand nearby locations in 2D or 3D space to have nearby numerical values (here, the distance traveled along the Hilbert Curve to get to that location) as often as possible. A Hilbert Curve is a path, so a distance down that path is a single number, but because it touches all grid points, that one number can be used to identify any grid point in 2D, 3D, or higher-dimensional space. Unlike some other "space-filling curves," like the more-common and easier-to-calculate Z-order curve, the Hilbert Curve doesn't move diagonally or jump long distances between sequential points, so it very often tends to have very close distances for very nearby 2D points.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    DEPTH
     
    static char[]
    hilbert3Distances
     
    static char[]
    hilbert3X
     
    static char[]
    hilbert3Y
     
    static char[]
    hilbert3Z
     
    static char[]
    hilbertDistances
     
    static char[]
    hilbertX
     
    static char[]
    hilbertY
     
    static char[]
    mooreDistances
     
    static char[]
    mooreX
     
    static char[]
    mooreY
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static int
    coordToHilbert(Coord pt)
    Takes a position as a Coord called pt and returns the length to travel along the 256x256 Hilbert curve to reach that position.
    static int
    coordToMoore(Coord pt)
    Takes a position as a Coord called pt and returns the length to travel along the 16x16 Moore curve to reach that position.
    static int
    getXMoore3D(int index, int n)
    Gets the x coordinate for a given index into the 16x16x(8*n) Moore curve.
    static int
    getYMoore3D(int index, int n)
    Gets the y coordinate for a given index into the 16x16x(8*n) Moore curve.
    static int
    getZMoore3D(int index, int n)
    Gets the z coordinate for a given index into the 16x16x(8*n) Moore curve.
    static int
    grayDecode(int n)
    Decode a number from a Gray code n; Gray codes have a relation to the Hilbert curve and may be useful.
    static int
    grayEncode(int n)
    Encode a number n as a Gray code; Gray codes have a relation to the Hilbert curve and may be useful.
    static Coord
    hilbertToCoord(int hilbert)
    Takes a distance to travel along the 256x256 Hilbert curve and returns a Coord representing the position in 2D space that corresponds to that point on the Hilbert curve.
    static int
    hilbertToMorton(int hilbert)
    Takes a distance to travel along the 256x256 Hilbert curve and returns a Morton code representing the position in 2D space that corresponds to that point on the Hilbert Curve; the Morton code will have interleaved x and y bits and x in the least significant bit.
    static void
    init2D()
     
    static void
    init3D()
     
    static Coord
    mooreToCoord(int moore)
    Takes a distance to travel along the 16x16 Hilbert curve and returns a Coord representing the position in 2D space that corresponds to that point on the Hilbert curve.
    static int
    mortonBitDecode3D(int morton)
    Given a 15-bit Morton code (typically produced by mortonEncode3D(int, int, int)), this unpacks the three interleaved numbers into contiguous 5-bit sections of the returned int.
    static Coord
    mortonDecode(int morton)
    Takes a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the Coord representing the same x, y position.
    static int
    mortonEncode(int index1, int index2)
    Takes two 8-bit unsigned integers index1 and index2, and returns a Morton code, with interleaved index1 and index2 bits and index1 in the least significant bit.
    static int
    mortonEncode3D(int index1, int index2, int index3)
    Given three 5-bit index parameters, encodes them all into a 15-bit Morton code.
    static int
    mortonToHilbert(int morton)
    Takes a position as a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the length to travel along the 256x256 Hilbert Curve to reach that position.
    static int
    posToHilbert(int x, int y)
    Takes an x, y position and returns the length to travel along the 256x256 Hilbert curve to reach that position.
    static int
    posToHilbert3D(int x, int y, int z)
    Takes an x, y, z position and returns the length to travel along the 8x8x8 Hilbert curve to reach that position.
    static int
    posToMoore(int x, int y)
    Takes an x, y position and returns the length to travel along the 16x16 Moore curve to reach that position.

    Methods inherited from class Object

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

  • Field Details

    • DEPTH

      public static final int DEPTH
      See Also:

    • hilbertX

      public static char[] hilbertX

    • hilbertY

      public static char[] hilbertY

    • hilbertDistances

      public static char[] hilbertDistances

    • mooreX

      public static char[] mooreX

    • mooreY

      public static char[] mooreY

    • mooreDistances

      public static char[] mooreDistances

    • hilbert3X

      public static char[] hilbert3X

    • hilbert3Y

      public static char[] hilbert3Y

    • hilbert3Z

      public static char[] hilbert3Z

    • hilbert3Distances

      public static char[] hilbert3Distances

  • Method Details

    • init2D

      public static void init2D()

    • init3D

      public static void init3D()

    • grayEncode

      public static int grayEncode(int n)
      Encode a number n as a Gray code; Gray codes have a relation to the Hilbert curve and may be useful. Source: 2π.com (page no longer exists), The Aggregate Magic Algorithms
      Parameters:
      n - any int
      Returns:
      the gray code for n

    • grayDecode

      public static int grayDecode(int n)
      Decode a number from a Gray code n; Gray codes have a relation to the Hilbert curve and may be useful. Source: 2π.com (page no longer exists), The Aggregate Magic Algorithms
      Parameters:
      n - a gray code, as produced by grayEncode
      Returns:
      the decoded int

    • posToHilbert

      public static int posToHilbert(int x, int y)
      Takes an x, y position and returns the length to travel along the 256x256 Hilbert curve to reach that position. This assumes x and y are between 0 and 255, inclusive. This uses a lookup table for the 256x256 Hilbert Curve, which should make it faster than calculating the distance along the Hilbert Curve repeatedly. Source: and-what-happened blog post.
      Parameters:
      x - between 0 and 255 inclusive
      y - between 0 and 255 inclusive
      Returns:
      the distance to travel along the 256x256 Hilbert Curve to get to the given x, y point.

    • posToHilbert3D

      public static int posToHilbert3D(int x, int y, int z)
      Takes an x, y, z position and returns the length to travel along the 8x8x8 Hilbert curve to reach that position. This assumes x, y, and z are between 0 and 7, inclusive. This uses a lookup table for the 8x8x8 Hilbert Curve, which should make it faster than calculating the distance along the Hilbert Curve repeatedly. Source: and-what-happened blog post.
      Parameters:
      x - between 0 and 7 inclusive
      y - between 0 and 7 inclusive
      z - between 0 and 7 inclusive
      Returns:
      the distance to travel along the 8x8x8 Hilbert Curve to get to the given x, y, z point.

    • posToMoore

      public static int posToMoore(int x, int y)
      Takes an x, y position and returns the length to travel along the 16x16 Moore curve to reach that position. This assumes x and y are between 0 and 15, inclusive. This uses a lookup table for the 16x16 Moore Curve, which should make it faster than calculating the distance along the Moore Curve repeatedly.
      Parameters:
      x - between 0 and 15 inclusive
      y - between 0 and 15 inclusive
      Returns:
      the distance to travel along the 16x16 Moore Curve to get to the given x, y point.

    • mortonToHilbert

      public static int mortonToHilbert(int morton)
      Takes a position as a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the length to travel along the 256x256 Hilbert Curve to reach that position. This uses 16 bits of the Morton code and requires that the code is non-negative. Source: and-what-happened blog post.
      Parameters:
      morton - a Morton code that interleaves two 8-bit unsigned numbers, with x as index1 and y as index2.
      Returns:
      a distance to travel down the Hilbert Curve to reach the location that can be decoded from morton.

    • hilbertToMorton

      public static int hilbertToMorton(int hilbert)
      Takes a distance to travel along the 256x256 Hilbert curve and returns a Morton code representing the position in 2D space that corresponds to that point on the Hilbert Curve; the Morton code will have interleaved x and y bits and x in the least significant bit. This uses a lookup table for the 256x256 Hilbert curve, which should make it faster than calculating the position repeatedly. The parameter hilbert is an int but only 16 unsigned bits are used.
      Parameters:
      hilbert - a distance to travel down the Hilbert Curve
      Returns:
      a Morton code that stores x and y interleaved; can be converted to a Coord with other methods.

    • hilbertToCoord

      public static Coord hilbertToCoord(int hilbert)
      Takes a distance to travel along the 256x256 Hilbert curve and returns a Coord representing the position in 2D space that corresponds to that point on the Hilbert curve. This uses a lookup table for the 256x256 Hilbert curve, which should make it faster than calculating the position repeatedly. The parameter hilbert is an int but only 16 unsigned bits are used.
      Parameters:
      hilbert - a distance to travel down the Hilbert Curve
      Returns:
      a Coord corresponding to the position in 2D space at the given distance down the Hilbert Curve

    • mooreToCoord

      public static Coord mooreToCoord(int moore)
      Takes a distance to travel along the 16x16 Hilbert curve and returns a Coord representing the position in 2D space that corresponds to that point on the Hilbert curve. This uses a lookup table for the 16x16 Hilbert curve, which should make it faster than calculating the position repeatedly. The parameter moore is an int but only 8 unsigned bits are used, and since the Moore Curve loops, it is calculated as moore & 255.
      Parameters:
      moore - a distance to travel down the Moore Curve
      Returns:
      a Coord corresponding to the position in 2D space at the given distance down the Hilbert Curve

    • coordToHilbert

      public static int coordToHilbert(Coord pt)
      Takes a position as a Coord called pt and returns the length to travel along the 256x256 Hilbert curve to reach that position. This assumes pt.x and pt.y are between 0 and 255, inclusive. Source: and-what-happened blog post.
      Parameters:
      pt - a Coord with values between 0 and 255, inclusive
      Returns:
      a distance from the start of the 256x256 Hilbert curve to get to the position of pt

    • coordToMoore

      public static int coordToMoore(Coord pt)
      Takes a position as a Coord called pt and returns the length to travel along the 16x16 Moore curve to reach that position. This assumes pt.x and pt.y are between 0 and 15, inclusive.
      Parameters:
      pt - a Coord with values between 0 and 15, inclusive
      Returns:
      a distance from the "start" of the 16x16 Moore curve to get to the position of pt

    • mortonEncode3D

      public static int mortonEncode3D(int index1, int index2, int index3)
      Given three 5-bit index parameters, encodes them all into a 15-bit Morton code. Source: and-what-happened blog post.
      Parameters:
      index1 - an int between 0 and 31, both inclusive
      index2 - an int between 0 and 31, both inclusive
      index3 - an int between 0 and 31, both inclusive
      Returns:
      a 15-bit int encoding all three index parameters

    • mortonBitDecode3D

      public static int mortonBitDecode3D(int morton)
      Given a 15-bit Morton code (typically produced by mortonEncode3D(int, int, int)), this unpacks the three interleaved numbers into contiguous 5-bit sections of the returned int. The low 5 bits (bits 0-4) will store what was originally index1, the 5 bits above that (5-9) will store what was originally index2, and the 5 bits above that (10-14) will store what was originally index2. Source: and-what-happened blog post.
      Parameters:
      morton - a 15-bit Morton code, typically produced by mortonEncode3D(int, int, int)
      Returns:
      a different encoding of the three 5-bit values, with bits 0-4, 5-9, and 10-14 storing the 3 indices

    • getXMoore3D

      public static int getXMoore3D(int index, int n)
      Gets the x coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0)
      Parameters:
      index - the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000
      n - the number of 8-deep layers to use as part of the box shape this travels through
      Returns:
      the x coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve

    • getYMoore3D

      public static int getYMoore3D(int index, int n)
      Gets the y coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0)
      Parameters:
      index - the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000
      n - the number of 8-deep layers to use as part of the box shape this travels through
      Returns:
      the y coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve

    • getZMoore3D

      public static int getZMoore3D(int index, int n)
      Gets the z coordinate for a given index into the 16x16x(8*n) Moore curve. Expects indices to touch the following corners of the 16x16x(8*n) cube in this order, using x,y,z syntax: (0,0,0) (0,0,(8*n)) (0,16,(8*n)) (0,16,0) (16,16,0) (16,16,(8*n)) (16,0,(8*n)) (16,0,0)
      Parameters:
      index - the index into the 3D 16x16x(8*n) Moore Curve, must be less than 0x1000
      n - the number of 8-deep layers to use as part of the box shape this travels through
      Returns:
      the z coordinate of the given distance traveled through the 3D 16x16x(8*n) Moore Curve

    • mortonEncode

      public static int mortonEncode(int index1, int index2)
      Takes two 8-bit unsigned integers index1 and index2, and returns a Morton code, with interleaved index1 and index2 bits and index1 in the least significant bit. With this method, index1 and index2 can have up to 8 bits. This returns a 32-bit Morton code but only uses 16 bits, and will not encode information in the sign bit. Source: and-what-happened blog post.
      Parameters:
      index1 - a non-negative integer using at most 8 bits, to be placed in the "x" slots
      index2 - a non-negative integer using at most 8 bits, to be placed in the "y" slots
      Returns:
      a Morton code that interleaves the two numbers as one 32-bit int, but only in 16 bits of it

    • mortonDecode

      public static Coord mortonDecode(int morton)
      Takes a Morton code, with interleaved x and y bits and x in the least significant bit, and returns the Coord representing the same x, y position. This uses 16 bits of the Morton code and requires that the code is non-negative. Source: and-what-happened blog post.
      Parameters:
      morton - an int containing two interleaved numbers, from 0 to 255 each
      Returns:
      a Coord matching the x and y extracted from the Morton code