1Math::PlanePath::R5DragUosneMridCpoonitnrti(b3u)ted PerlMaDtohc:u:mPelnatnaetPiaotnh::R5DragonMidpoint(3)
2
3
4

NAME

6       Math::PlanePath::R5DragonMidpoint -- R5 dragon curve midpoints
7

SYNOPSIS

9        use Math::PlanePath::R5DragonMidpoint;
10        my $path = Math::PlanePath::R5DragonMidpoint->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This is midpoints of the R5 dragon curve by Jorg Arndt,
15
16                                              31--30                       11
17                                               |   |
18                                              32  29                       10
19                                               |   |
20                      51--50          35--34--33  28--27--26                9
21                       |   |           |                   |
22                      52  49          36--37--38  23--24--25                8
23                       |   |                   |   |
24              55--54--53  48--47--46  41--40--39  22                        7
25               |                   |   |           |
26              56--57--58  63--64  45  42  19--20--21                        6
27                       |   |   |   |   |   |
28              81--80  59  62  65  44--43  18--17--16  11--10                5
29               |   |   |   |   |                   |   |   |
30              82  79  60--61  66--67--68          15  12   9                4
31               |   |                   |           |   |   |
32           ..-83  78--77--76  71--70--69          14--13   8-- 7-- 6        3
33                           |   |                                   |
34                          75  72                           3-- 4-- 5        2
35                           |   |                           |
36                          74--73                           2                1
37                                                           |
38                                                       0-- 1           <- Y=0
39
40               ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
41             -10  -9  -8  -7  -6  -5  -4  -3  -2  -1  X=0  1   2   3
42
43       The points are the middle of each edge of the "R5DragonCurve", rotated
44       -45 degrees, shrunk by sqrt(2). and shifted to the origin.
45
46                     *--11--*     *--7--*     R5DragonCurve
47                     |      |     |     |     and its midpoints
48                    12     10     8     6
49                     |      |     |     |
50              *--17--*--13--*--9--*--5--*
51              |      |      |     |
52             18     16     14     4
53              |      |      |     |
54           ..-*      *--15--*     *--3--*
55                                        |
56                                        2
57                                        |
58                                  +--1--*
59
60   Arms
61       Multiple copies of the curve can be selected, each advancing
62       successively.  Like the main "R5DragonCurve" this midpoint curve covers
63       1/4 of the plane and 4 arms rotated by 0, 90, 180, 270 degrees mesh
64       together perfectly.  With 4 arms all integer X,Y points are visited.
65
66       "arms => 4" begins as follows.  N=0,4,8,12,16,etc is the first arm (the
67       same shape as the plain curve above), then N=1,5,9,13,17 the second,
68       N=2,6,10,14 the third, etc.
69
70           arms=>4     76--80-...                                6
71                        |
72                       72--68--64  44--40                        5
73                                |   |   |
74                       25--21  60  48  36                        4
75                        |   |   |   |   |
76                       29  17  56--52  32--28--24  75--79        3
77                        |   |                   |   |   |
78               41--37--33  13-- 9-- 5  12--16--20  71  83        2
79                |                   |   |           |   |
80               45--49--53   6-- 2   1   8  59--63--67  ...       1
81                        |   |           |   |
82           ... 65--61--57  10   3   0-- 4  55--51--47        <- Y=0
83            |   |           |   |                   |
84           81  69  22--18--14   7--11--15  35--39--43           -1
85            |   |   |                   |   |
86           77--73  26--30--34  54--58  19  31                   -2
87                            |   |   |   |   |
88                           38  50  62  23--27                   -3
89                            |   |   |
90                           42--46  66--70--74                   -4
91                                            |
92                                   ...-82--78                   -5
93
94            ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
95           -6  -5  -4  -3  -2  -1  X=0  1   2   3   4   5
96

FUNCTIONS

98       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
99       classes.
100
101       "$path = Math::PlanePath::R5DragonMidpoint->new ()"
102           Create and return a new path object.
103
104       "($x,$y) = $path->n_to_xy ($n)"
105           Return the X,Y coordinates of point number $n on the path.  Points
106           begin at 0 and if "$n < 0" then the return is an empty list.
107
108           Fractional positions give an X,Y position along a straight line
109           between the integer positions.
110
111       "$n = $path->n_start()"
112           Return 0, the first N in the path.
113
114   Level Methods
115       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
116           Return "(0, 5**$level - 1)", or for multiple arms return "(0, $arms
117           * 5**$level - 1)".
118
119           There are 5^level segments comprising the curve, or arms*5^level
120           when multiple arms, numbered starting from 0.
121

FORMULAS

123   X,Y to N
124       An X,Y point can be turned into N by dividing out digits of a complex
125       base 1+2i.  At each step the low base-5 digit is formed from X,Y and an
126       adjustment applied to move X,Y to a multiple of 1+2i ready to divide
127       out.
128
129       A 10x10 table is used for the digit and adjustments, indexed by Xmod10
130       and Ymod10.  There's probably an a*X+b*Y mod 5 or mod 20 for a smaller
131       table.  But in any case once the adjustment is found the result is
132
133           Ndigit = digit_table[X mod 10, Y mod 10]  # low to high
134           Xm = X + Xadj_table [X mod 10, Y mod 10]
135           Ym = Y + Yadj_table [X mod 10, Y mod 10]
136
137           new X,Y = (Xm,Ym) / (1+2i)
138                   = (Xm,Ym) * (1-2i) / 5
139                   = ((Xm+2*Ym)/5, (Ym-2*Xm)/5)
140
141       These X,Y reductions eventually reach one of the starting points for
142       the four arms
143
144           X,Y endpoint   Arm        +---+---+
145           ------------   ---        | 2 | 1 |  Y=1
146               0, 0        0         +---+---+
147               0, 1        1         | 3 | 0 |  Y=0
148              -1, 1        2         +---+---+
149              -1, 0        3         X=-1 X=0
150
151       For arms 1 and 3 the digits must be flipped 4-digit, so 0,1,2,3,4 ->
152       4,3,2,1,0.  The arm number and hence whether this flip is needed is not
153       known until reaching the endpoint.
154
155           if arm odd
156           then  N = 5^numdigits - 1 - N
157
158       If only some of the arms are of interest then reaching one of the other
159       arm numbers means the original X,Y was outside the desired curve.
160

SEE ALSO

162       Math::PlanePath, Math::PlanePath::R5DragonCurve
163
164       Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonMidpoint
165

HOME PAGE

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

LICENSE

170       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin
171       Ryde
172
173       This file is part of Math-PlanePath.
174
175       Math-PlanePath is free software; you can redistribute it and/or modify
176       it under the terms of the GNU General Public License as published by
177       the Free Software Foundation; either version 3, or (at your option) any
178       later version.
179
180       Math-PlanePath is distributed in the hope that it will be useful, but
181       WITHOUT ANY WARRANTY; without even the implied warranty of
182       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
183       General Public License for more details.
184
185       You should have received a copy of the GNU General Public License along
186       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
187
188
189
190perl v5.32.1                      2021-01-2M7ath::PlanePath::R5DragonMidpoint(3)
Impressum