The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-PlanePath-75
River stage one • 3 direct dependents • 4 total dependents
2 ++
/ Math::PlanePath::MultipleRings

NAME

Math::PlanePath::MultipleRings -- rings of multiples

SYNOPSIS

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

DESCRIPTION

This path puts points on concentric rings. Each ring is "step" many points more than the previous, and the first is also "step" so a successively increasing multiple of that many points. For example with the default step==6,

                24  23
             25        22
                  10
          26   11     9  21  ...

        27  12   3  2   8  20  38

       28  13   4    1   7  19  37        <- Y=0

        29  14   5  6  18  36

          30   15    17  35
                  16
             31        24
                32  33

                  ^
                 X=0

X,Y positions returned are fractional. The innermost ring like the 1,2,...,6 above has points 1 unit apart. Subsequent rings are either packed similarly or spread out to ensure the X axis points like 1,7,19,37 above are 1 unit apart. The latter happens for step <= 6. For step >= 7 the rings are big enough to separate those X points.

The layout is similar to the spiral paths of corresponding step. For example step=6 is like the HexSpiral, but rounded out to circles instead of a hexagonal grid. Similarly step=4 the DiamondSpiral or step=8 the SquareSpiral.

The step parameter is similar to the PyramidRows with the rows stretched around circles, though PyramidRows starts from a 1-wide initial row and increases by the step, whereas for MultipleRings there's no initial.

The starting radial 1,7,19,37 etc on the X axis for step=6 is 6*d*(d-1)/2 + 1, counting the innermost ring as d=1. In general it's a multiple of the triangular numbers, plus 1,

    Nstart = step*d*(d-1)/2 + 1

Straight line radials further around have arise from adding multiples of d, so for example in step=6 shown above the line N=3,11,25,etc is Nstart + 2*d. Multiples of d bigger than the step give lines which are in between the base ones extending out from the innermost ring.

Ring Shape

Option ring_shape => 'polygon' puts the points on concentric polygons of "step" many sides, so successive polygons have 1 more point on each side than the previous polygon. For example step=4 gives 4-sided polygons, ie. diamonds,

    ring_shape=>'polygon', step=>4

                  16
                /    \
             17    7   15    
           /    /     \   \   
        18    8    2    6   14 
      /    /    /     \    \   \ 
    19   9    3         1    5   13 
      \     \   \    /     /   /
        20   10    4   12   24
           \     \    /   /
             21   11   23
                \    /
                  22

The polygons are scaled to keep points 1 unit apart. For step>=6 this means 1 unit apart sideways. step=6 is in fact a honeycomb grid where each points is 1 away its six neighbours.

For step=3, 4 and 5 the polygon sides are 1 apart radially, as measured in the centre of each side. This makes points a little more than 1 apart. Squeezing them up to make the closest points exactly 1 apart is possible, but may require iterating a square root for each ring. step=3 squeezed down would in fact become a variable spacing with four close then one wider.

For step=2 and step=1 in the current code the default circle shape is used. Should that change? Is there a polygon style with 2 sides or 1 side?

The polygon layout is only a little different from a circle, but it lines up points on the sides and that might help show a structure for some sets of points plotted on the path.

Step 3 Pentagonals

For step=3 the pentagonal numbers 1,5,12,22,etc, P(k) = (3k-1)*k/2, are a radial going up to the left, and the second pentagonal numbers 2,7,15,26, S(k) = (3k+1)*k/2 are a radial going down to the left, respectively 1/3 and 2/3 the way around the circles.

As described in "Step 3 Pentagonals" in Math::PlanePath::PyramidRows, those P(k) and preceding P(k)-1, P(k)-2, and S(k) and preceding S(k)-1, S(k)-2 are all composites, so plotting the primes on a step=3 MultipleRings has two radial gaps where there's no primes.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::MultipleRings->new (step => $integer)
$path = Math::PlanePath::MultipleRings->new (step => $integer, ring_shape => $str)

Create and return a new path object.

The step parameter controls how many points are added in each circle. It defaults to 6 which is an arbitrary choice and the suggestion is to always pass in a desired count.

($x,$y) = $path->n_to_xy ($n)

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

$n can be any value $n >= 1 and fractions give positions on the rings in between the integer points. For $n < 1 the return is an empty list since points begin at 1.

Fractional $n currently ends up on the circle arc between the integer points. Would straight line chords between them be better, reflecting the unit spacing of the points? Neither seems particularly important.

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

Return an integer point number for coordinates $x,$y. Each integer N is considered the centre of a circle of diameter 1 and an $x,$y within that circle returns N.

The unit spacing of the points means those circles don't overlap, but they also don't cover the plane and if $x,$y is not within one then the return is undef.

FORMULAS

N to X,Y - Circle

Points on the rings are spaced so they're at least 1 unit apart. The innermost ring has "step" many points which means the vertices of a polygon with "step" many sides each of length 1. The "base_r" radius to such a vertex is

      base_r     ___---*
           ___---      |
     ___--- alpha      | 1/2 = half the polygon side
    o------------------+

    alpha = 2pi/step * 1/2      # "step" many sides
    sin(alpha) = (1/2) / base_r

    base_r = 0.5 / sin(pi/step)

Subsequent rings are then either 1 bigger to keep the points on the X axis 1 unit apart, or they're at the vertices of a polygon with d*step many sides so as to keep the points 1 apart sideways. Reckoning the innermost ring as d=1 (at base_r), the second as d=2, etc, this means

    r = max /  base_r + (d-1)
            \  0.5 / sin(pi/(d*step))

The sin() polygon case is the maximum whenever step>6, so

    if step<=6   r = base_r + (d-1)
    if step>6    r = 0.5 / sin(pi/(d*step))

The angle theta around the ring for N is determined by how much N exceeds the Nstart of that ring (Nstart as described above). d can be found by a square root. (N-1)/step in the formula effectively converts the start into triangular number style.

    d = floor (1 + sqrt(8*(N-1)/step + 1)) / 2

Then the remainder into the ring is

    Nrem = N - Nstart
    theta = 2pi * Nrem / (d*step)

    X = r * cos(theta)
    Y = r * sin(theta)

For a few cases X or Y are exact integers. Special case code for these cases ensures floating point rounding of pi doesn't give small offsets from integers.

If step=6 then base_r=1 exactly since the innermost ring is a little hexagon in this case. This means the points on the X axis are all integers X=1,2,3,etc.

       P-----P
      /   1 / \ 1  <-- innermost points 1 apart
     /     /   \
    P     o-----P   <--  base_r = 1
     \      1  /
      \       /
       P-----P

If theta=pi, which is 2*Nrem==d*step, then the point is on the negative X axis. Returning Y=0 exactly for that avoids sin(pi) generally being some small non-zero due to rounding.

If theta=pi/2 or theta=3pi/2, which is 4*Nrem==d*step or 4*Nrem==3*d*step, then N is on the positive or negative Y axis (respectively). Returning X=0 exactly avoids cos(pi/2) or cos(3pi/2) generally being some small non-zero.

Points on the negative X axis points occur when the step is even. Points on the Y axis points occur when the step is a multiple of 4.

If theta=pi/4, 3pi/4, 5pi/4 or 7pi/4, which is 8*Nrem==d*step, 3*d*step, 5*d*step or 7*d*step then the points are on the 45-degree lines X=Y or X=-Y. The current code doesn't try to ensure X==Y in these cases. The values are not integers and floating point rounding might make them them unequal due to sin(pi/4)!=cos(pi/4).

SEE ALSO

Math::PlanePath, Math::PlanePath::SacksSpiral, Math::PlanePath::TheodorusSpiral, Math::PlanePath::PixelRings

HOME PAGE

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

LICENSE

Copyright 2010, 2011, 2012 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/>.