Kevin Ryde > Math-PlanePath > Math::PlanePath::DekkingCurve

Download:
Math-PlanePath-118.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

Open  1
View/Report Bugs
Module Version: 118   Source  

NAME ^

Math::PlanePath::DekkingCurve -- 5x5 self-similar edge curve

SYNOPSIS ^

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

DESCRIPTION ^

This is an integer version of a 5x5 self-similar curve by Dekking,

     10 |             123-124-125-...      86--85
        |               |                   |   |
      9 | 115-116-117 122-121  90--89--88--87  84
        |   |       |       |   |               |
      8 | 114-113 118-119-120  91--92--93  82--83
        |       |                       |   |
      7 |     112 107-106 103-102  95--94  81  78--77
        |       |   |   |   |   |   |       |   |   |
      6 |     111 108 105-104 101  96--97  80--79  76
        |       |   |           |       |           |
      5 |     110-109  14--15 100--99--98  39--40  75          66--65
        |               |   |               |   |   |           |   |
      4 |  10--11--12--13  16  35--36--37--38  41  74  71--70  67  64
        |   |               |   |               |   |   |   |   |   |
      3 |   9---8---7  18--17  34--33--32  43--42  73--72  69--68  63
        |           |   |               |   |                       |
      2 |       5---6  19  22--23  30--31  44  47--48  55--56--57  62--61
        |       |       |   |   |   |       |   |   |   |       |       |
      1 |       4---3  20--21  24  29--28  45--46  49  54--53  58--59--60
        |           |           |       |           |       |
    Y=0 |   0---1---2          25--26--27          50--51--52
        +----------------------------------------------------------------
          X=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15

The base pattern is the N=0 to N=25 section. It repeats with rotations or reversals which make the ends join. For example N=75 to N=100 is the base pattern in reverse, ie. from N=25 down to N=0. Or N=50 to N=75 is reverse and also rotate by -90.

The curve segments are edges of squares in a 5x5 arrangement.

     +- - -+- - -+- - 14----15  ---+
     |     |     |     |  v  |>    |
        ^     ^       <|     |
    10----11----12----13- - 16   --+
     |              v        |>    |
     |>       ^           ^  |
     9-----8-----7 -- 18----17   --+
        v  |     |     |>          |
     |        ^  |>    |        ^
     +- -  5-----6 -  19    22----23
           |          <|     |    <|
     |    <|  ^        |    <|     |
     +- -  4-----3    20----21 -- 24
                 |       v        <|
        ^     ^  |>    |     |     |
     0-----1-----2  -- + -- -+-   25

The little notch marks show which square each edge represents. This is the side the curve expands into at the next level. For example N=1 to N=2 has its notch on the left so the next level N=25 to N=50 expands on the left.

All the directions are made by rotating the base pattern. When the expansion is on the right the segments go in reverse. For example N=2 to N=3 expands on the right and is made by rotating the base pattern clockwise 90 degrees. This means that N=2 becomes the 25 end, and following the curve to the 0 start at N=3.

Arms

The optional arms parameter can give up to four copies of the curve, each advancing successively. Each copy is in a successive quadrant.

    arms => 3                |
                      67-70-73       42-45                  5
                       |              |  |
             43-46-49 64-61 30-33-36-39 48                  4
              |     |     |  |           |
             40-37 52-55-58 27-24-21 54-51                  3
                 |                 |  |
                34 19-16  7--4 15-18 57 66-69               2
                 |  |  |  |  |  |     |  |  |
                31 22 13-10  1 12--9 60-63 72               1
                 |  |              |        |
        ...--74 28-25  5--2  0--3--6       75-...     <-- Y=0
              |        |
             71 62-59  8-11                                -1
              |  |  |     |
             68-65 56 17-14                                -2
                    |  |
                50-53 20-23-26                             -3
                 |           |
                47 38-35-32-29                             -4
                 |  |
                44-41                                      -5
                             ^
         ... -5 -4 -3 -2 -1 X=0 1  2  3  4  5 ...

The origin is N=0 only and is on the first arm. The second and subsequent arms begin 1,2,etc. The curves interleave perfectly on the Y axis where the first and second arms meet, and the same on the other axes. The result is that 4 arms fill the plane visiting each integer X,Y exactly once and not touching.

FUNCTIONS ^

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

$path = Math::PlanePath::DekkingCurve->new ()
$path = Math::PlanePath::DekkingCurve->new (arms => $a)

Create and return a new path object.

The optional arms parameter gives between 1 and 4 copies of the curve successively advancing.

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

Level Methods

($n_lo, $n_hi) = $path->level_to_n_range($level)

Return (0, 25**$level), or for multiple arms return (0, $arms * 25**$level).

There are 25^level + 1 points in a level, numbered starting from 0. On the second and third arms the origin is omitted (so as not to repeat that point) and so just 25^level for them, giving 25^level+1 + (arms-1)*25^level = arms*25^level + 1 many points starting from 0.

FORMULAS ^

X Axis Segments

In the sample points above there are some line segments on the X axis. A segment X to X+1 is traversed or not according to

    X digits in base 5

    traversed        if X==0
    traversed        if low digit 1
    not-traversed    if low digit 2 or 3 or 4
    when low digit == 0
      traversed      if lowest non-zero 1 or 2
      not-traversed  if lowest non-zero 3 or 4

In the samples the segments at X=1, X=6 and X=11 segments traversed are the low digit 1 rule. Their preceding X=5 and X=10 segments are low digit==0 and the lowest non-zero 1 or 2 (respectively). At X=15 however the lowest non-zero is 3 and so not-traversed.

In general in groups of 5 there is always X==1 mod 5 traversed but its preceding X==0 mod 5 is traversed or not according to lowest non-zero 1,2 or 3,4.

This pattern is found by considering how the base pattern expands. The plain base pattern has its south edge on the X axis. The first two sub-parts of that south edge are the base pattern unrotated, so the south edge again, but the other parts rotated. In general the sides are

           0 1 2 3 4
    S  ->  S,S,E,N,W
    E  ->  S,S,E,N,N
    N  ->  W,S,E,N,N
    W  ->  W,S,E,N,W

Starting in S and taking digits high to low a segment is traversed when the final state is S again.

Any digit 1,2,3 goes to S,E,N respectively. If no 1,2,3 at all then the start is S. At the lowest 1,2,3 there are only digits 0,4 below. If no such digits then only digit 1 which is S, or no digits at all for N=0, is traversed. If one or more 0s below then E goes to S so a lowest non-zero 2 means traversed too. If there is any 4 then it goes to N or W and in those states both 0,4 stay in N or W so not-traversed.

The transitions from the lowest 1,2,3 can be drawn in a state diagram,

                +-+
                v |4                           base 5 digits of X
               North  <---+    <-------+       high to low
             /            |            |
            /0            |4           |
           /              |            |3
    +->   v               |       2    |
    +-- West             East  <--- lowest 1,2,3
    0,4   ^               |            |
           \              |            |1
            \4            |0           |or no 1,2,3 at all
             \            |            |
               South  <---+    <-------+
                ^ |0
                +-+

The full diagram, starting from the top digit, is less clear

                +-+
                v |3,4
        +--->  North  <---+
        |    /  | ^  \    |
       3|   /0  1 |  2\   |3,4           base 5 digits of X
        |  /    | |    \  |              high to low
    +-> | v     | |     v |   <-+
    +-- West 2---------> East --+        start in South,
    0,4 | ^     | |     ^ |    2         segment traversed
        |  \    | |    /  |              if end in South
       1|   \4  | 3  2/   |0,1
        |    \  v |  /    |
        +--->  South  <---+
                ^ |0,1
                +-+

but allows usual DFA state machine manipulations to reverse to go low to high.

          +---------- start ----------+
          |       1    0|   2,3,4     |         base 5 digits of X
          |             |             |         low to high
          v       1,2   v   3,4       v
    traversed <------- m1 -------> not-traversed
                      0|^
                       ++

In state m1 a 0 digit loops back to m1 and finds the lowest non-zero. Digit 2 result differs according to whether there are any low 0s.

Y Axis Segments

The Y axis can be treated similarly

    Y digits in base 5  (with a single 0 digit if Y==0)

    traversed        if lowest digit 3
    not-traversed    if lowest digit 0 or 1 or 2
    when lowest digit == 4
      traversed      if lowest non-4 is 2 or 3
      not-traversed  if lowest non-4 is 0 or 1

The Y axis goes around the base square clockwise, so the digits are reversed 0<->4 from the X axis for the state transitions. The initial state is W.

           0 1 2 3 4
    S  ->  W,N,E,S,S
    E  ->  N,N,E,S,S
    N  ->  N,N,E,S,W
    W  ->  W,N,E,S,W

N and W can be merged as equivalent since they differ only in digit 0 destination N or W and both as final state are not-traversed.

Final state S is reached if the lowest digit is 3, or if state S or E are reached by digit 2 or 3 and then only 4s below.

X,Y Axis Interleaving

For multiple arms a copy of the curve is rotated +90 degrees so that the X axis of the rotated copy is on the Y axis. The segments do not overlap nor does the curve touch.

This can be seen from the digit rules above. The 1 mod 5 segment is always traversed by X and never by Y. The 2 mod 5 segment is never traversed by either. The 3 mod 5 segment is always traversed by Y and never by X.

The 0 mod 5 segment is sometimes traversed by X, and never by Y. The 4 mod 5 segment is sometimes traversed by Y, and never by Y.

        0       1       2       3       4
    *-------*-------*-------*-------*-------*
        X       X     never     Y       Y
      maybe  always          always   maybe

A 4 mod 5 segment has one or more trailing 4s and +1 for the next segment makes them 0s and increments the lowest non-4. This means that lowest non-4 digit is traversed 2,3 and not 0,1 becomes 3,4 and 0,1 and for the X axis rule are not-traversed or traversed respectively. So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are traversed.

SEE ALSO ^

Math::PlanePath, Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve

HOME PAGE ^

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

LICENSE ^

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

syntax highlighting: