1Math::PlanePath::AlternUasteerPaCpoenrt(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::AlternatePaper(3)
2
6 Math::PlanePath::AlternatePaper -- alternate paper folding curve
7
9 use Math::PlanePath::AlternatePaper;
10 my $path = Math::PlanePath::AlternatePaper->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an integer version of the alternate paper folding curve (a
15 variation on the DragonCurve paper folding).
16 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 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 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 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 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 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 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 The first segment N=0 to N=1 unfolds clockwise, pivoting at the
67 endpoint "1",
68 2
70 -> |
71 unfold / |
72 ===> | |
73 |
74 0------1 0-------1
75 Then that "L" shape unfolds again, pivoting at the end "2", but anti-
77 clockwise, on the opposite side to the first unfold,
78 2-------3
80 2 | |
81 | unfold | ^ |
82 | ===> | _/ |
83 | | |
84 0------1 0-------1 4
85 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 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 . N
95 /| / \
96 / | / \
97 / | / \
98 / | / \
99 / | / \
100 /_____N /___________\
101 0,0 0,0
102 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 +
109 /|
110 / |
111 / |
112 / 2>|
113 +----+
114 /|\ 3|
115 / | \ v|
116 / |^ \ |
117 / 0>| 1 \|
118 +----+----+
119 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 arms => 2
126 | | | | | |
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 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 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 arms => 4
149 | | | | |
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 -----------------------------------------
160 -1 -2 X=0 1 2
161 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 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 arms => 8
171 | | | | | |
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 ^
187 -3 -2 -1 X=0 1 2
188
190 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
191 classes.
192 "$path = Math::PlanePath::AlternatePaper->new ()"
194 "$path = Math::PlanePath::AlternatePaper->new (arms => $integer)"
195 Create and return a new path object.
196 "($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 Fractional positions give an X,Y position along a straight line
202 between the integer points.
203 "@n_list = $path->xy_to_n_list ($x,$y)"
205 Return a list of N point numbers for coordinates "$x,$y".
206 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 "$n = $path->n_start()"
213 Return 0, the first N in the path.
214 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 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
225 Various formulas for coordinates, lengths and area can be found in the
226 author's mathematical write-up
227 <http://user42.tuxfamily.org/alternate/index.html>
229 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 N = 0b...z100..00 (including possibly no trailing 0s)
236 ^
237 pos, counting from 0 for least significant bit
238 (z bit) XOR (pos&1) Turn
240 ------------------- ----
241 0 right
242 1 left
243 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 Next Turn
248 The bits also give the turn after next by looking at the bit above the
249 lowest 0.
250 N = 0b...w011..11 (including possibly no trailing 1s)
252 ^
253 pos, counting from 0 for least significant bit
254 (w bit) XOR (pos&1) Next Turn
256 ------------------- ---------
257 0 right
258 1 left
259 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 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 Total Turn
270 The total turn can be calculated from the segment replacements
271 resulting from the bits of N.
272 each bit of N from high to low
274 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 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 (bit positions numbered from 0 for the least significant bit)
286 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 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 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 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 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 if N even then dX = (-1)^(count even length runs of 1 bits in N)
313 if N odd then dX = 0
314 This (-1)^count is related to the Golay-Rudin-Shapiro sequence,
316 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 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 dX = / GRS(N) if N even
328 \ 0 if N odd
329 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 dY = / 0 if N even
340 \ GRS(N) if N odd
341 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 dX = GRS(2k)
347 = GRS(k)
348 dY = GRS(2k+1)
350 = GRS(k) * (-1)^k
351 = / GRS(k) if k even
352 \ -GRS(k) if k odd
353 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 dSum
360 From the dX and dY formulas above it can be seen that their sum is
361 simply GRS(N),
362 dSum = dX + dY = GRS(N)
364 The sum X+Y is a numbering of anti-diagonal lines,
366 | \ \ \
368 |\ \ \ \
369 | \ \ \ \
370 |\ \ \ \ \
371 | \ \ \ \ \
372 |\ \ \ \ \ \
373 +------------
374 0 1 2 3 4 5
375 The curve steps each time either up to the next or back to the previous
377 according to dSum=GRS(N).
378 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 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
392 The alternate paper folding curve is in Sloane's Online Encyclopedia of
393 Integer Sequences as
394 <http://oeis.org/A106665> (etc)
396 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 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 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 A077957 Y at N=2^k, being alternately 0 and 2^(k/2)
416 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 A126684 N single-visited points, either X axis or diagonal
424 A176237 N double-visited points
425 A270804 N segments of X=Y diagonal stair-step
427 A270803 0,1 predicate for these segments
428 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 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 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 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 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 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 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 A000225 convex hull area*2, being 2^k-1
467 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 A052955 single-visited points to N=2^k
475 A052940 single-visited points to N=4^k, being 3*2^n-1
476 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 arms=2
481 A062880 N on X axis, base 4 digits 0,2 only
482 arms=3
484 A001196 N on X axis, base 4 digits 0,3 only
485
487 House of Graphs entries for the alternate paperfolding curve as a graph
488 include
489 level=3, <https://hog.grinvin.org/ViewGraphInfo.action?id=27008>
491 level=4, <https://hog.grinvin.org/ViewGraphInfo.action?id=27010>
492 level=5, <https://hog.grinvin.org/ViewGraphInfo.action?id=27012>
493
495 Math::PlanePath, Math::PlanePath::AlternatePaperMidpoint
496 Math::PlanePath::DragonCurve, Math::PlanePath::CCurve,
498 Math::PlanePath::HIndexing, Math::PlanePath::ZOrderCurve
499 Math::NumSeq::GolayRudinShapiro,
501 Math::NumSeq::GolayRudinShapiroCumulative
502 Michel Mendès France and G. Tenenbaum, "Dimension des Courbes Planes,
504 Papiers Plies et Suites de Rudin-Shapiro", Bulletin de la S.M.F.,
505 volume 109, 1981, pages 207-215.
506 <http://www.numdam.org/item?id=BSMF_1981__109__207_0>
507
509 <http://user42.tuxfamily.org/math-planepath/index.html>
510
512 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
513 This file is part of Math-PlanePath.
515 Math-PlanePath is free software; you can redistribute it and/or modify
517 it under the terms of the GNU General Public License as published by
518 the Free Software Foundation; either version 3, or (at your option) any
519 later version.
520 Math-PlanePath is distributed in the hope that it will be useful, but
522 WITHOUT ANY WARRANTY; without even the implied warranty of
523 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
524 General Public License for more details.
525 You should have received a copy of the GNU General Public License along
527 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
528perl v5.30.1 2020-01-30Math::PlanePath::AlternatePaper(3)