Math::...gonals(3pm)

📦
version 129 · 3 versions
, in debian bookworm, debian trixie, ubuntu jammy, ubuntu noble, ubuntu resolute, ubuntu stonking

✨ NAME ✨

Math::PlanePath::Diagonals — points in diagonal stripes 💅

(yes bestie, this is the Math::...gonals(3pm) page, straight outta the User Contributed Perl Documentation — ik the name got clipped, she's just Like That 💀)

🎀 SYNOPSIS 🎀

use Math::PlanePath::Diagonals;
my $path = Math::PlanePath::Diagonals->new;
my ($x, $y) = $path->n_to_xy (123);

🦋 DESCRIPTION 🦋

Okay so the whole vibe of this path is: it walks successive diagonals, going from the Y axis down to the X axis. Slay.

      6  |  22
      5  |  16  23
      4  |  11  17  24
      3  |   7  12  18  ...
      2  |   4   8  13  19
      1  |   2   5   9  14  20
    Y=0  |   1   3   6  10  15  21
         +-------------------------
           X=0   1   2   3   4   5

N=1,3,6,10,etc sitting on the X axis? Those are the triangular numbers, periodt. And N=1,2,4,7,11,etc on the Y axis is the triangular plus 1 — aka the next point visited after the X axis. No cap.

🌸 Direction 🌸

The option direction => 'up' flips the order within each diagonal so it counts upward from the X axis instead. It's giving "same path, different walk" ✨

    direction => "up"

      5  |  21
      4  |  15  20
      3  |  10  14  19 ...
      2  |   6   9  13  18  24
      1  |   3   5   8  12  17  23
    Y=0  |   1   2   4   7  11  16  22
         +-----------------------------
           X=0   1   2   3   4   5   6

Real talk: this is merely a transpose swapping X,Y for Y,X, but it's the same as in "DiagonalsOctant", and it can be handy to control the direction when you're combining "Diagonals" with some other path or calculation. Lowkey useful 🫶

💜 N Start 💜

Default is numbering the points starting from N=1, like the diagram above. An optional n_start can give a different start, in the same diagonals sequence. For example, to start at 0:

    n_start => 0,                    n_start=>0
    direction=>"down"                direction=>"up"

      4  |  10                       |  14
      3  |   6 11                    |   9 13
      2  |   3  7 12                 |   5  8 12
      1  |   1  4  8 13              |   2  4  7 11
    Y=0  |   0  2  5  9 14           |   0  1  3  6 10
         +-----------------          +-----------------
           X=0  1  2  3  4             X=0  1  2  3  4

N=0,1,3,6,10,etc on the Y axis of "down", or on the X axis of "up", is the triangular numbers Y*(Y+1)/2. 🤓

🌈 X,Y Start 🌈

The options x_start => $x and y_start => $y give a starting position for the diagonals. For example, to start at X=1,Y=1:

      7  |   22               x_start => 1,
      6  |   16 23            y_start => 1
      5  |   11 17 24
      4  |    7 12 18 ...
      3  |    4  8 13 19
      2  |    2  5  9 14 20
      1  |    1  3  6 10 15 21
    Y=0  |
         +------------------
         X=0  1  2  3  4  5

ngl the effect is merely to add a fixed offset to all the X,Y values taken and returned — but it can be handy to have the path do that for you when you wanna step through non-negatives or something similar. Main character convenience ✨

💅 FUNCTIONS 💅

Peep "FUNCTIONS" in Math::PlanePath for the behaviour that's common to all path classes.

  • $path = Math::PlanePath::Diagonals->new ()
  • $path = Math::PlanePath::Diagonals->new (direction => $str, n_start => $n, x_start => $x, y_start => $y)

Creates and returns a new path object. The direction option (a string) can be:

direction => "down"       the default
direction => "up"         number upwards from the X axis
  • ($x,$y) = $path->n_to_xy ($n)

Returns the X,Y coordinates of point number $n on the path.

For "$n < 0.5" the return is an empty list, it being considered the path begins at 1.

  • $n = $path->xy_to_n ($x,$y)

Returns the point number for coordinates "$x,$y". $x and $y are each rounded to the nearest integer, which has the effect of treating each point $n as a square of side 1, so the quadrant x>=-0.5, y>=-0.5 is entirely covered.

  • ($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)

The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in the rectangle. Iconic behaviour honestly 💖

🧚 FORMULAS 🧚

🔥 X,Y to N 🔥

The sum d=X+Y numbers each diagonal from d=0 upwards, corresponding to the Y coordinate where the diagonal starts (or X if direction=up).

    d=2
        \
    d=1  \
        \ \
    d=0  \ \
        \ \ \

N is then given by

    d = X+Y
    N = d*(d+1)/2 + X + Nstart

The d*(d+1)/2 shows how the triangular numbers fall on the Y axis when X=0 and Nstart=0. For the default Nstart=1 it's 1 more than the triangulars, as noted above.

d can be expanded out to the following quite symmetric form. This almost suggests something parabolic but is still the straight line diagonals.

        X^2 + 3X + 2XY + Y + Y^2
    N = ------------------------ + Nstart
                   2

        (X+Y)^2 + 3X + Y
      = ---------------- + Nstart       (using one square)
                2

⭐ N to X,Y ⭐

The above formula N=d*(d+1)/2 can be solved for d as

    d = floor( (sqrt(8*N+1) - 1)/2 )
    # with n_start=0

For example N=12 is d=floor((sqrt(8*12+1)-1)/2)=4 as that N falls in the fifth diagonal. Then the offset from the Y axis NY=d*(d-1)/2 is the X position,

    X = N - d*(d+1)/2
    Y = X - d

In the code, fractional N is handled by imagining each diagonal beginning 0.5 back from the Y axis. That's handled by adding 0.5 into the sqrt, which is +4 onto the 8*N.

    d = floor( (sqrt(8*N+5) - 1)/2 )
    # N>=-0.5

The X and Y formulas are unchanged, since N=d*(d-1)/2 is still the Y axis. But each diagonal d begins up to 0.5 before that and therefore X extends back to -0.5.

🫶 Rectangle to N Range 🫶

Within each row, increasing X is increasing N, and in each column, increasing Y is increasing N. So in a rectangle the lower left corner is minimum N and the upper right is maximum N.

    |            \     \ N max
    |       \ ----------+
    |        |     \    |\
    |        |\     \   |
    |       \| \     \  |
    |        +----------
    |  N min  \  \     \
    +-------------------------

👑 OEIS 👑

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

    <http://oeis.org/A002262> (etc)

    direction=down (the default)
      A002262    X coordinate, runs 0 to k
      A025581    Y coordinate, runs k to 0
      A003056    X+Y coordinate sum, k repeated k+1 times
      A114327    Y-X coordinate diff
      A101080    HammingDist(X,Y)

      A127949    dY, change in Y coordinate

      A000124    N on Y axis, triangular numbers + 1
      A001844    N on X=Y diagonal

      A185787    total N in row to X=Y diagonal
      A185788    total N in row to X=Y-1
      A100182    total N in column to Y=X diagonal
      A101165    total N in column to Y=X-1
      A185506    total N in rectangle 0,0 to X,Y

    either direction=up,down
      A097806    turn 0=straight, 1=not straight

    direction=down, x_start=1, y_start=1
      A057555    X,Y pairs
      A057046    X at N=2^k
      A057047    Y at N=2^k

    direction=down, n_start=0
      A057554    X,Y pairs
      A023531    dSum = dX+dY, being 1 at N=triangular+1 (and 0)
      A000096    N on X axis, X*(X+3)/2
      A000217    N on Y axis, the triangular numbers
      A129184    turn 1=left,0=right
      A103451    turn 1=left or right,0=straight, but extra initial 1
      A103452    turn 1=left,0=straight,-1=right, but extra initial 1
    direction=up, n_start=0
      A129184    turn 0=left,1=right

    direction=up, n_start=-1
      A023531    turn 1=left,0=right
    direction=down, n_start=-1
      A023531    turn 0=left,1=right

    in direction=up the X,Y coordinate forms are the same but swap X,Y

    either direction=up,down
      A038722    permutation N at transpose Y,X
                   which is direction=down <-> direction=up

    either direction, x_start=1, y_start=1
      A003991    X*Y coordinate product
      A003989    GCD(X,Y) greatest common divisor starting (1,1)
      A003983    min(X,Y)
      A051125    max(X,Y)

    either direction, n_start=0
      A049581    abs(X-Y) coordinate diff
      A004197    min(X,Y)
      A003984    max(X,Y)
      A004247    X*Y coordinate product
      A048147    X^2+Y^2
      A109004    GCD(X,Y) greatest common divisor starting (0,0)
      A004198    X bit-and Y
      A003986    X bit-or Y
      A003987    X bit-xor Y
      A156319    turn 0=straight,1=left,2=right

      A061579    permutation N at transpose Y,X
                   which is direction=down <-> direction=up

🌟 SEE ALSO 🌟

  • Math::PlanePath
  • Math::PlanePath::DiagonalsAlternating
  • Math::PlanePath::DiagonalsOctant
  • Math::PlanePath::Corner
  • Math::PlanePath::Rows
  • Math::PlanePath::Columns

🌈 HOME PAGE 🌈

<http://user42.tuxfamily.org/math-planepath/index.html>

💖 LICENSE 💖

Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.

okay bestie that's the whole page 🎀 this one's perl v5.32.0, dated 2021-01-23 — a lil vintage moment, but she still eats. go build some diagonals, you got this 💅✨🦋

📦 where this page comes from