1Math::PlanePath::AlternUasteerPaCpoenrt(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::AlternatePaper(3)
2
3
4

NAME

6       Math::PlanePath::AlternatePaper -- alternate paper folding curve
7

SYNOPSIS

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

DESCRIPTION

14       This is an integer version of the alternate paper folding curve (a
15       variation on the DragonCurve paper folding).
16
17             8 |                                                      128
18               |                                                       |
19             7 |                                                42---43/127
20               |                                                |      |
21             6 |                                         40---41/45--44/124
22               |                                         |      |      |
23             5 |                                  34---35/39--38/46--47/123
24               |                                  |      |      |      |
25             4 |                           32---33/53--36/52--37/49--48/112
26               |                           |      |      |      |      |
27             3 |                    10---11/31--30/54--51/55--50/58--59/111
28               |                    |      |      |      |      |      |
29             2 |              8----9/13--12/28--29/25--24/56--57/61--60/108
30               |              |     |      |      |      |      |      |
31             1 |        2----3/7---6/14--15/27--26/18--19/23---22/62--63/107
32               |        |     |     |      |      |      |      |      |
33           Y=0 |  0-----1     4-----5     16-----17     20-----21     64---..
34               |
35               +------------------------------------------------------------
36                 X=0    1     2     3      4      5      6      7      8
37
38       The curve visits the X axis points and the X=Y diagonal points once
39       each and visits "inside" points between there twice each.  The first
40       doubled point is X=2,Y=1 which is N=3 and also N=7.  The segments
41       N=2,3,4 and N=6,7,8 have touched, but the curve doesn't cross over
42       itself.  The doubled vertices are all like this, touching but not
43       crossing, and no edges repeat.
44
45       The first step N=1 is to the right along the X axis and the path fills
46       the eighth of the plane up to the X=Y diagonal inclusive.
47
48       The X axis N=0,1,4,5,16,17,etc is the integers which have only digits
49       0,1 in base 4, or equivalently those which have a 0 bit at each odd
50       numbered bit position.
51
52       The X=Y diagonal N=0,2,8,10,32,etc is the integers which have only
53       digits 0,2 in base 4, or equivalently those which have a 0 bit at each
54       even numbered bit position.
55
56       The X axis values are the same as on the ZOrderCurve X axis, and the
57       X=Y diagonal is the same as the ZOrderCurve Y axis, but in between the
58       two are different.  (See Math::PlanePath::ZOrderCurve.)
59
60   Paper Folding
61       The curve arises from thinking of a strip of paper folded in half
62       alternately one way and the other, and then unfolded so each crease is
63       a 90 degree angle.  The effect is that the curve repeats in successive
64       doublings turned 90 degrees and reversed.
65
66       The first segment N=0 to N=1 unfolds clockwise, pivoting at the
67       endpoint "1",
68
69                                           2
70                                      ->   |
71                        unfold       /     |
72                         ===>       |      |
73                                           |
74           0------1                0-------1
75
76       Then that "L" shape unfolds again, pivoting at the end "2", but anti-
77       clockwise, on the opposite side to the first unfold,
78
79                                           2-------3
80                  2                        |       |
81                  |     unfold             |   ^   |
82                  |      ===>              | _/    |
83                  |                        |       |
84           0------1                0-------1       4
85
86       In general after each unfold the shape is a triangle as follows.  "N"
87       marks the N=2^k endpoint in the shape, either bottom right or top
88       centre.
89
90           after even number          after odd number
91              of unfolds,                of unfolds,
92            N=0 to N=2^even            N=0 to N=2^odd
93
94                      .                       N
95                     /|                      / \
96                    / |                     /   \
97                   /  |                    /     \
98                  /   |                   /       \
99                 /    |                  /         \
100                /_____N                 /___________\
101               0,0                     0,0
102
103       For an even number of unfolds the triangle consists of 4 sub-parts
104       numbered by the high digit of N in base 4.  Those sub-parts are self-
105       similar in the direction ">", "^" etc as follows, and with a reversal
106       for parts 1 and 3.
107
108                     +
109                    /|
110                   / |
111                  /  |
112                 / 2>|
113                +----+
114               /|\  3|
115              / | \ v|
116             /  |^ \ |
117            / 0>| 1 \|
118           +----+----+
119
120   Arms
121       The "arms" parameter can choose 1 to 8 curve arms successively
122       advancing.  Each fills an eighth of the plane.  The second arm is
123       mirrored across the X=Y leading diagonal, so
124
125             arms => 2
126
127               |   |     |       |       |       |
128             4 |  33---31/55---25/57---23/63---64/65--
129               |         |       |       |       |
130             3 |  11---13/29---19/27---20/21---22/62--
131               |   |     |       |       |       |
132             2 |   9----7/15---16/17---18/26---24/56--
133               |         |       |       |       |
134             1 |   3----4/5-----6/14---12/28---30/54--
135               |   |     |       |       |       |
136           Y=0 |  0/1----2       8------10      32---
137               |
138               +------------- -------------------------
139                 X=0     1       2       3       4
140
141       Here the even N=0,2,4,6,etc is the plain curve below the X=Y diagonals
142       and odd N=1,3,5,7,9,etc is the mirrored copy.
143
144       Arms 3 and 4 are the same but rotated +90 degrees and starting from
145       X=0,Y=1.  That start point ensures each edge between integer points is
146       traversed just once.
147
148           arms => 4
149
150               |       |       |      |        |
151           --34/35---14/30---18/21--25/57----37/53--        3
152               |       |       |      |        |
153           --15/31---10/11----6/17--13/29----32/33--        2
154               |       |       |      |        |
155            --19       7-----2/3/5---8/9-----12/28--        1
156                               |      |        |
157                              0/1-----4        16--     <- Y=0
158
159           -----------------------------------------
160              -1      -2      X=0     1        2
161
162       Points N=0,4,8,12,etc is the plain curve, N=1,5,9,13,etc the second
163       mirrored arm, N=2,6,10,14,etc is arm 3 which is the plain curve rotated
164       +90, and N=3,7,11,15,etc the rotated and mirrored.
165
166       Arms 5 and 6 start at X=-1,Y=1, and arms 7 and 8 start at X=-1,Y=0 so
167       they too traverse each edge once.  With a full 8 arms each point is
168       visited twice except for the four start points which are three times.
169
170           arms => 8
171
172               |       |       |       |       |       |
173           --75/107--66/67---26/58---34/41---49/113--73/105--        3
174               |       |       |       |       |       |
175           --51/115---27/59---18/19--10/33---25/57---64/65--         2
176               |       |       |       |       |       |
177           --36/43---12/35---4/5/11---2/3/9--16/17---24/56--         1
178               |       |       |       |       |       |
179           --28/60---20/21---6/7/13--0/1/15---8/39---32/47--     <- Y=0
180               |       |       |       |       |       |
181           --68/69---29/61----14/37---22/23--31/63---55/119--       -1
182               |       |       |       |       |       |
183           --77/109--53/117---38/45---30/62--70/71---79/111--       -2
184               |       |       |       |       |       |
185
186                                       ^
187              -3      -2      -1      X=0     1        2
188

FUNCTIONS

190       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
191       classes.
192
193       "$path = Math::PlanePath::AlternatePaper->new ()"
194       "$path = Math::PlanePath::AlternatePaper->new (arms => $integer)"
195           Create and return a new path object.
196
197       "($x,$y) = $path->n_to_xy ($n)"
198           Return the X,Y coordinates of point number $n on the path.  Points
199           begin at 0 and if "$n < 0" then the return is an empty list.
200
201           Fractional positions give an X,Y position along a straight line
202           between the integer points.
203
204       "@n_list = $path->xy_to_n_list ($x,$y)"
205           Return a list of N point numbers for coordinates "$x,$y".
206
207           For arms=1 there may be none, one or two N's for a given "$x,$y".
208           For multiple arms the origin points X=0 or 1 and Y=0 or -1 have up
209           to 3 Ns, being the starting points of the arms.  For arms=8 those 4
210           points have 3 N and every other "$x,$y" has exactly two Ns.
211
212       "$n = $path->n_start()"
213           Return 0, the first N in the path.
214
215   Level Methods
216       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
217           Return "(0, 2**$level)", or for multiple arms return "(0, $arms *
218           2**$level + ($arms-1))".
219
220           This is the same as "Level Methods" in
221           Math::PlanePath::DragonCurve.  Each level is an unfold (on
222           alternate sides left or right).
223

FORMULAS

225       Various formulas for coordinates, lengths and area can be found in the
226       author's mathematical write-up
227
228           <http://user42.tuxfamily.org/alternate/index.html>
229
230   Turn
231       At each point N the curve always turns either left or right, it never
232       goes straight ahead.  The turn is given by the bit above the lowest 1
233       bit in N and whether that position is odd or even.
234
235           N = 0b...z100..00   (including possibly no trailing 0s)
236                    ^
237                    pos, counting from 0 for least significant bit
238
239           (z bit) XOR (pos&1)   Turn
240           -------------------   ----
241                    0            right
242                    1            left
243
244       For example N=10 binary 0b1010 has lowest 1 bit at 0b__1_ and the bit
245       above that is a 0 at even number pos=2, so turn to the right.
246
247   Next Turn
248       The bits also give the turn after next by looking at the bit above the
249       lowest 0.
250
251           N = 0b...w011..11    (including possibly no trailing 1s)
252                    ^
253                    pos, counting from 0 for least significant bit
254
255           (w bit) XOR (pos&1)    Next Turn
256           -------------------    ---------
257                    0             right
258                    1             left
259
260       For example at N=10 binary 0b1010 the lowest 0 is the least significant
261       bit, and above that is a 1 at odd pos=1, so at N=10+1=11 turn right.
262       This works simply because w011..11 when incremented becomes w100..00
263       which is the "z" form above.
264
265       The inversion at odd bit positions can be applied with an xor
266       0b1010..1010.  With that done the turn calculation is then the same as
267       the DragonCurve (see "Turn" in Math::PlanePath::DragonCurve).
268
269   Total Turn
270       The total turn can be calculated from the segment replacements
271       resulting from the bits of N.
272
273           each bit of N from high to low
274
275             when plain state
276              0 -> no change
277              1 -> turn left if even bit pos or turn right if odd bit pos
278                     and go to reversed state
279
280             when reversed state
281              1 -> no change
282              0 -> turn left if even bit pos or turn right if odd bit pos
283                     and go to plain state
284
285           (bit positions numbered from 0 for the least significant bit)
286
287       This is similar to the DragonCurve (see "Total Turn" in
288       Math::PlanePath::DragonCurve) except the turn is either left or right
289       according to an odd or even bit position of the transition, instead of
290       always left for the DragonCurve.
291
292   dX,dY
293       Since there's always a turn either left or right, never straight ahead,
294       the X coordinate changes, then Y coordinate changes, alternately.
295
296               N=0
297           dX   1  0  1  0  1  0 -1  0  1  0  1  0 -1  0  1  0  ...
298           dY   0  1  0 -1  0  1  0  1  0  1  0 -1  0 -1  0 -1  ...
299
300       X changes when N is even, Y changes when N is odd.  Each change is
301       either +1 or -1.  Which it is follows the Golay-Rudin-Shapiro sequence
302       which is parity odd or even of the count of adjacent 11 bit pairs.
303
304       In the total turn above it can be seen that if the 0->1 transition is
305       at an odd position and 1->0 transition at an even position then there's
306       a turn to the left followed by a turn to the right for no net change.
307       Likewise an even and an odd.  This means runs of 1 bits with an odd
308       length have no effect on the direction.  Runs of even length on the
309       other hand are a left followed by a left, or a right followed by a
310       right, for 180 degrees, which negates the dX change.  Thus
311
312           if N even then dX = (-1)^(count even length runs of 1 bits in N)
313           if N odd  then dX = 0
314
315       This (-1)^count is related to the Golay-Rudin-Shapiro sequence,
316
317           GRS = (-1) ^ (count of adjacent 11 bit pairs in N)
318               = (-1) ^ count_1_bits(N & (N>>1))
319               = /  +1 if (N & (N>>1)) even parity
320                 \  -1 if (N & (N>>1)) odd parity
321
322       The GRS is +1 on an odd length run of 1 bits, for example a run 111 is
323       two 11 bit pairs.  The GRS is -1 on an even length run, for example
324       1111 is three 11 bit pairs.  So modulo 2 the power in the GRS is the
325       same as the count of even length runs and therefore
326
327           dX = /  GRS(N)  if N even
328                \  0       if N odd
329
330       For dY the total turn and odd/even runs of 1s is the same 180 degree
331       changes, except N is odd for a Y change so the least significant bit is
332       1 and there's no return to "plain" state.  If this lowest run of 1s
333       starts on an even position (an odd number of 1s) then it's a turn left
334       for +1.  Conversely if the run started at an odd position (an even
335       number of 1s) then a turn right for -1.  The result for this last run
336       is the same "negate if even length" as the rest of the GRS, just for a
337       slightly different reason.
338
339           dY = /  0       if N even
340                \  GRS(N)  if N odd
341
342   dX,dY Pair
343       At a consecutive pair of points N=2k and N=2k+1 the dX and dY can be
344       expressed together in terms of GRS(k) as
345
346           dX = GRS(2k)
347              = GRS(k)
348
349           dY = GRS(2k+1)
350              = GRS(k) * (-1)^k
351              = /  GRS(k) if k even
352                \  -GRS(k) if k odd
353
354       For dY reducing 2k+1 to k drops a 1 bit from the low end.  If the
355       second lowest bit is also a 1 then they were a "11" bit pair which is
356       lost from GRS(k).  The factor (-1)^k adjusts for that, being +1 if k
357       even or -1 if k odd.
358
359   dSum
360       From the dX and dY formulas above it can be seen that their sum is
361       simply GRS(N),
362
363           dSum = dX + dY = GRS(N)
364
365       The sum X+Y is a numbering of anti-diagonal lines,
366
367          | \ \ \
368          |\ \ \ \
369          | \ \ \ \
370          |\ \ \ \ \
371          | \ \ \ \ \
372          |\ \ \ \ \ \
373          +------------
374            0 1 2 3 4 5
375
376       The curve steps each time either up to the next or back to the previous
377       according to dSum=GRS(N).
378
379       The way the curve visits outside edge X,Y points once each and inner
380       X,Y points twice each means an anti-diagonal s=X+Y is visited a total
381       of s many times.  The diagonal has floor(s/2)+1 many points.  When s is
382       odd the first is visited once and the rest visited twice.  When s is
383       even the X=Y point is only visited once.  In each case the total is s
384       many visits.
385
386       The way the coordinate sum s=X+Y occurs s many times is a geometric
387       interpretation to the way the cumulative GRS sequence has each value k
388       occurring k many times.  (See
389       Math::NumSeq::GolayRudinShapiroCumulative.)
390

OEIS

392       The alternate paper folding curve is in Sloane's Online Encyclopedia of
393       Integer Sequences as
394
395           <http://oeis.org/A106665> (etc)
396
397           A020986   X coordinate unduplicated, X+Y coordinate sum
398                       being Golay/Rudin/Shapiro cumulative
399           A020990   Y coordinate unduplicated, X-Y diff starting from N=1
400                       being Golay/Rudin/Shapiro * (-1)^n cumulative
401           A068915   Y when N even, X when N odd
402
403       Since the X and Y coordinates each change alternately, each coordinate
404       appears twice, for instance X=0,1,1,2,2,3,3,2,2,etc.  A020986 and
405       A020990 are "undoubled" X and Y in the sense of just one copy of each
406       of those paired values.
407
408           A209615   turn 1=left,-1=right
409           A292077   turn 0=left,1=right
410           A106665   next turn 1=left,0=right, a(0) is turn at N=1
411           A020985   dX and dY alternately, dSum change in X+Y
412                       being Golay/Rudin/Shapiro sequence +1,-1
413           A020987   GRS with values 0,1 instead of +1,-1
414
415           A077957   Y at N=2^k, being alternately 0 and 2^(k/2)
416
417           A000695   N on X axis, being base 4 digits 0,1 only
418           A007088     in base-4
419           A151666   predicate 0,1 for N on X axis
420           A062880   N on diagonal, being base 4 digits 0,2 only
421           A169965     in base-4
422
423           A126684   N single-visited points, either X axis or diagonal
424           A176237   N double-visited points
425
426           A270804   N segments of X=Y diagonal stair-step
427           A270803     0,1 predicate for these segments
428
429           A022155   N positions of West or South segments,
430                       being GRS < 0,
431                       ie. dSum < 0 so move to previous anti-diagonal
432           A203463   N positions of East or North segments,
433                       being GRS > 0,
434                       ie. dSum > 0 so move to next anti-diagonal
435
436           A212591   N-1 of first time on X+Y=s anti-diagonal
437           A047849   N of first time on X+Y=2^k anti-diagonal
438
439           A020991   N-1 of last time on X+Y=s anti-diagonal
440           A053644   X of last time on X+Y=s anti-diagonal
441           A053645   Y of last time on X+Y=s anti-diagonal
442           A080079   X-Y of last time on X+Y=s anti-diagonal
443
444           A093573   N-1 of points on the anti-diagonals d=X+Y,
445                       by ascending N-1 value within each diagonal
446           A004277   num visits in column X
447
448       A020991 etc have values N-1, ie. the numbering differs by 1 from the N
449       here, since they're based on the A020986 cumulative GRS starting at n=0
450       for value GRS(0).  This matches the turn sequence A106665 starting at
451       n=0 for the first turn, whereas for the path here that's N=1.
452
453           A274230   area to N=2^k = double-visited points to N=2^k
454           A027556   2*area to N=2^k
455           A134057   area to N=4^k
456           A060867   area to N=2*4^k
457           A122746   area increment N=2^k to N=2^(k+1)
458                       = num segments West  N=0 to 2^k-1
459
460           A005418   num segments East  N=0 to 2^k-1
461           A051437   num segments North N=0 to 2^k-1
462           A007179   num segments South N=0 to 2^k-1
463           A097038   num runs of 8 consecutive segments within N=0 to 2^k-1
464                       each segment enclosing a new unit square
465
466           A000225   convex hull area * 2, being 2^k-1
467
468           A027383   boundary/2 to N=2^k
469                      also boundary verticals or horizontals
470                      (boundary is half verticals half horizontals)
471           A131128   boundary to N=4^k
472           A028399   boundary to N=2*4^k
473
474           A052955   single-visited points to N=2^k
475           A052940   single-visited points to N=4^k, being 3*2^n-1
476
477           A181666   n XOR other(n) occurring at double-visited points
478           A086341   graph diameter of level N=0 to 2^k  (for k>=3)
479
480           arms=2
481             A062880   N on X axis, base 4 digits 0,2 only
482
483           arms=3
484             A001196   N on X axis, base 4 digits 0,3 only
485

HOUSE OF GRAPHS

487       House of Graphs entries for the alternate paperfolding curve as a graph
488       include
489
490           <https://hog.grinvin.org/ViewGraphInfo.action?id=19655> etc
491
492           19655     level=0 (1-segment path)
493           32234     level=1 (2-segment path)
494           286       level=2 (4-segment path)
495           27008     level=3
496           27010     level=4
497           27012     level=5
498           33778     level=6
499           33780     level=7
500           33782     level=8
501

SEE ALSO

503       Math::PlanePath, Math::PlanePath::AlternatePaperMidpoint
504
505       Math::PlanePath::DragonCurve, Math::PlanePath::CCurve,
506       Math::PlanePath::HIndexing, Math::PlanePath::ZOrderCurve
507
508       Math::NumSeq::GolayRudinShapiro,
509       Math::NumSeq::GolayRudinShapiroCumulative
510
511       Michel Mendès France and G. Tenenbaum, "Dimension des Courbes Planes,
512       Papiers Plies et Suites de Rudin-Shapiro", Bulletin de la S.M.F.,
513       volume 109, 1981, pages 207-215.
514       <http://www.numdam.org/item?id=BSMF_1981__109__207_0>
515

HOME PAGE

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

LICENSE

520       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020,
521       2021 Kevin Ryde
522
523       This file is part of Math-PlanePath.
524
525       Math-PlanePath is free software; you can redistribute it and/or modify
526       it under the terms of the GNU General Public License as published by
527       the Free Software Foundation; either version 3, or (at your option) any
528       later version.
529
530       Math-PlanePath is distributed in the hope that it will be useful, but
531       WITHOUT ANY WARRANTY; without even the implied warranty of
532       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
533       General Public License for more details.
534
535       You should have received a copy of the GNU General Public License along
536       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
537
538
539
540perl v5.32.1                      2021-01-27Math::PlanePath::AlternatePaper(3)
Impressum