NAME

Math::PlanePath::CornerReplicate -- replicating U parts

SYNOPSIS

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

DESCRIPTION

This path is a self-similar replicating corner fill with 2x2 blocks. It's sometimes called a "U order" since the base N=0 to N=3 is like a "U".

     7  | 63--62  59--58  47--46  43--42
        |      |       |       |       |
     6  | 60--61  56--57  44--45  40--41
        |          |               |
     5  | 51--50  55--54  35--34  39--38
        |      |       |       |       |
     4  | 48--49  52--53  32--33  36--37
        |                  |
     3  | 15--14  11--10  31--30  27--26
        |      |       |       |       |
     2  | 12--13   8-- 9  28--29  24--25
        |          |               |
     1  |  3-- 2   7-- 6  19--18  23--22
        |      |       |       |       |
    Y=0 |  0-- 1   4-- 5  16--17  20--21
        +--------------------------------
          X=0  1   2   3   4   5   6   7

The pattern is the initial N=0 to N=3 section,

    +-------+-------+
    |       |       |
    |   3   |   2   |
    |       |       |
    +-------+-------+
    |       |       |
    |   0   |   1   |
    |       |       |
    +-------+-------+

It repeats as 2x2 blocks arranged in the same pattern, then 4x4 blocks, etc. There's no rotations or reflections within sub-parts.

The X axis N=0,1,4,5,16,17,etc is all the integers which use only digits 0 and 1 in base 4. For example N=17 is 101 in base 4.

The Y axis N=0,3,12,15,48,etc is all the integers which use only digits 0 and 3 in base 4. For example N=51 is 303 in base 4.

The X=Y diagonal N=0,2,8,10,32,34,etc is all the integers which use only digits 0 and 2 in base 4.

The X axis is the same as the ZOrderCurve, and the Y axis here is the X=Y diagonal of the ZOrderCurve, and conversely the X=Y diagonal here is the Y axis of the ZOrderCurve.

The N value at a given X,Y is converted to or from the ZOrderCurve by transforming base 4 digit values 2->3 and 3->2. This can be done by a bitwise "X xor Y". When Y has a 1-bit the xor swaps 2<->3.

    ZOrder X  = Crep X  xor Crep Y
    ZOrder Y  = Crep Y

    Crep X  = ZOrder X  xor ZOrder Y
    Crep Y  = ZOrder Y

Level Ranges

A given replication extends to

    Nlevel = 4^level - 1
    - (2^level - 1) <= X <= (2^level - 1)
    - (2^level - 1) <= Y <= (2^level - 1)

Hamming Distance

The Hamming distance between integers X and Y is the number of bit positions where the two values differ when written in binary. In this corner replicate each bit-pair of N becomes a bit of X and a bit of Y,

       N      X   Y
    ------   --- ---
    0 = 00    0   0
    1 = 01    1   0     <- difference 1 bit
    2 = 10    1   1
    3 = 11    0   1     <- difference 1 bit

So the Hamming distance is the number of base4 bit-pairs of N which are 01 or 11. If bit positions are counted from 0 for the least significant bit then

    HammingDist(X,Y) = count 1-bits at even bit positions in N    

FUNCTIONS

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

$path = Math::PlanePath::CornerReplicate->new ()

Create and return a new path object.

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

Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.

($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.

OEIS

This path is in Sloane's Online Encyclopedia of Integer Sequences as

    http://oeis.org/A000695  (etc)

    A059906    Y coordinate
    A059905    X bitxor Y (is ZOrderCurve X)
    A139351    HammingDist(X,Y), count 1-bits at even positions in N

    A000695    N on X axis, base 4 digits 0,1 only
    A001196    N on Y axis, base 4 digits 0,3 only
    A062880    N on diagonal, base 4 digits 0,2 only
    A163241    base-4 flip 2<->3,
                 converts N to ZOrderCurve N (and back)

    A048647    permutation N at transpose Y,X
                 base4 digits 1<->3 and 0,2 unchanged

SEE ALSO

Math::PlanePath, Math::PlanePath::LTiling, Math::PlanePath::SquareReplicate, Math::PlanePath::GosperReplicate, Math::PlanePath::ZOrderCurve, Math::PlanePath::GrayCode

HOME PAGE

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

LICENSE

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

cpanm Math::PlanePath

perl -MCPAN -e shell
install Math::PlanePath