Class NumberPairing

java.lang.Object
com.github.yellowstonegames.grid.NumberPairing
public final class NumberPairing extends Object
Utility functions for pairing (and tripling) functions, which take two (or three) numbers, typically ints, and return an int with magnitude dependent on the input number with maximum magnitude. The results can be organized into "shells" (also called "gnomons") based on the scale of the inputs; if any input is very large, the shell will be very far from the origin, but if all inputs are small, the shell will be closer to the origin. All pairing functions map each unique pair of valid inputs to one valid output, where valid inputs must be in a particular range. This also permits an inverse to exist for any pairing function, which takes one number and produces two results. Here, the inverses mutate a Point2Int or Point3Int to avoid allocating a new object every time.
The classic example of a pairing function is the Cantor pairing function, which assigns increasing results to pairs of ints, with the "shell" based on the sum of the two inputs. Another, lesser-known example is the Rosenberg-Strong pairing function, which has its "shell" based on the greater of the two inputs. The Cantor pairing function forms right-triangle shapes for its shells, whereas the Rosenberg-Strong pairing function forms squares.

  • Method Details

    • cantor

      public static int cantor(int x, int y)
      2D Cantor pairing function. This is a way of getting a unique int result for small enough x and y values, where "small enough" can safely be considered "between 0 and 32766." This can overflow if the sum of x and y is greater than 65533, so it can't reasonably deal with all int inputs. This is permitted to have adjacent results "jump" from non-adjacent inputs, but only when the shell changes. The shell is defined as the sum of x and y. Adjacency here permits diagonal movement.
      Parameters:
      x - non-negative horizontal input, between 0 and 32766, inclusive
      y - non-negative vertical input, between 0 and 32766, inclusive
      Returns:
      pair of x and y as one int via the Cantor pairing function

    • cantorInverse

      public static Point2Int cantorInverse(Point2Int p, int d)
      Inverse of the 2D Cantor pairing function.
      Parameters:
      p - a point that will have its contents overwritten with the decoded x and y of the given distance
      d - pair of x and y via the Cantor function, from the origin, between 0 and 2147385344, inclusive
      Returns:
      p, after modifications

    • rosenbergStrong

      public static int rosenbergStrong(int x, int y)
      2D Rosenberg-Strong pairing function. See Steven Pigeon's blog. This is permitted to have adjacent results "jump" from non-adjacent inputs, but only when the shell changes. The shell is defined as the greater of x and y. Adjacency here does not permit diagonal movement.
      Parameters:
      x - non-negative horizontal input, between 0 and 46339, inclusive
      y - non-negative vertical input, between 0 and 46339, inclusive
      Returns:
      pair of x and y as one int via the Rosenberg-Strong function

    • rosenbergStrongInverse

      public static Point2Int rosenbergStrongInverse(Point2Int p, int d)
      Inverse of the 2D Rosenberg-Strong pairing function. See Steven Pigeon's blog.
      Parameters:
      p - a point that will have its contents overwritten with the decoded x and y of the given distance
      d - pair of x and y via the Rosenberg-Strong function, from the origin, between 0 and 2147395599, inclusive
      Returns:
      p, after modifications

    • windingRosenbergStrong

      public static int windingRosenbergStrong(int x, int y)
      2D Boustrophedonic ("ox-turning", or "sidewinding") Rosenberg-Strong pairing function. See Steven Pigeon's blog. All adjacent results will come from adjacent inputs, even when the shell changes. The shell is defined as the greater of x and y. Adjacency here does not permit diagonal movement.
      Parameters:
      x - non-negative horizontal input, between 0 and 46339, inclusive
      y - non-negative vertical input, between 0 and 46339, inclusive
      Returns:
      distance on the Boustrophedonic Rosenberg-Strong curve, from the origin

    • windingRosenbergStrongInverse

      public static Point2Int windingRosenbergStrongInverse(Point2Int p, int d)
      Inverse of the 2D Boustrophedonic ("ox-turning", or "sidewinding") Rosenberg-Strong pairing function. See Steven Pigeon's blog.
      Parameters:
      p - a point that will have its contents overwritten with the decoded x and y of the given distance
      d - the distance on the Boustrophedonic Rosenberg-Strong curve, from the origin, between 0 and 2147395599, inclusive
      Returns:
      p, after modifications

    • szudzik

      public static int szudzik(int x, int y)
      2D Szudzik Elegant pairing function. See Wikipedia. This pairing function does not guarantee that results in the same shell will be adjacent for adjacent inputs; that is, it is permitted to "jump" even within a shell.
      Parameters:
      x - non-negative horizontal input, between 0 and 46339, inclusive
      y - non-negative vertical input, between 0 and 46339, inclusive
      Returns:
      pair of x and y as one int via the Szudzik Elegant function

    • szudzikInverse

      public static Point2Int szudzikInverse(Point2Int p, int d)
      Inverse of the 2D Szudzik Elegant pairing function. See Wikipedia.
      Parameters:
      p - a point that will have its contents overwritten with the decoded x and y of the given distance
      d - pair of x and y via the Szudzik Elegant function, from the origin, between 0 and 2147395599, inclusive
      Returns:
      p, after modifications

    • pers

      public static int pers(int x, int y, int z)
      3D Pigeon-Ettinger-Rosenberg-Strong Triple (PERS) function. This gets a single integer that encodes three non-negative ints (between 0 and 1289, inclusive) into one distance along a space-filling curve starting at (0,0,0). The curve is organized into cube-shaped "shells" or "gnomons," each shell being completely returned before an outer shell can be returned. That is, the distance to a point inside a cube will always be less than the distance to a point that is outside that cube (if both have inputs that are in range). Two different shells will connect at one of two edges, either y=0,z=0 for an even shell connecting to a larger odd shell, or z=0,y=0 for an odd shell connecting to a larger even shell.
      Notably, the distance will always be less than Math.pow(Math.max(x, Math.max(y, z)) + 1, 3) for inputs that are in range. All adjacent results will come from adjacent inputs, even when the shell changes. The shell is defined as the greater of x, y, and z. Adjacency here does not permit diagonal movement.
      This is based on a boustrophedonic Rosenberg-Strong pairing function (see Steven Pigeon's blog for more), but extended to three dimensions. The blog post suggests using the pair of x with the pair of y and z as a triple function, but that doesn't act like the 2D pairing function regarding shells.
      "We could, of course, devise some complicated function for 3..." -- Steven Pigeon
      "Yes! It works!" -- Tommy Ettinger
      Parameters:
      x - 3D coordinate, between 0 and 1289, inclusive
      y - 3D coordinate, between 0 and 1289, inclusive
      z - 3D coordinate, between 0 and 1289, inclusive
      Returns:
      the distance along a space-filling curve from the origin to the given point.

    • persInverse

      public static Point3Int persInverse(Point3Int p, int d)
      Inverse of the 3D Pigeon-Ettinger-Rosenberg-Strong (PERS) Triple function. This takes a single double d for distance and a Point3Int p that will be modified in-place, and sets p to hold the coordinates of the point at distance Math.floor(d) along the Pigeon-Ettinger-Rosenberg-Strong space-filling curve, starting at the origin (0,0,0). The curve is organized into cube-shaped "shells" or "gnomons," each shell being completely returned before an outer shell can be returned. That is, the distance to a point inside a cube will always be less than the distance to a point that is outside that cube (if both have inputs that are in range). Two different shells will connect at one of two edges, either y=0,z=0 for an even shell connecting to a larger odd shell, or z=0,y=0 for an odd shell connecting to a larger even shell.
      Notably, the distance will always be less than Math.pow(Math.max(x, Math.max(y, z)) + 1, 3) for inputs that are between 0 and 2146688999, inclusive.
      This is based on a boustrophedonic Rosenberg-Strong pairing function (see Steven Pigeon's blog for more), but extended to three dimensions. The blog post suggests using the pair of x with the pair of y and z as a triple function, but that doesn't act like the 2D pairing function regarding shells.
      "We could, of course, devise some complicated function for 3..." -- Steven Pigeon
      "Yes! It works!" -- Tommy Ettinger
      Parameters:
      p - a non-null Point3Int that will be modified in-place
      d - the distance along the space-filling curve from the origin, between 0 and 2146688999, inclusive
      Returns:
      p, containing the point at distance d along the curve