1Math::PlanePath::DragonUMsiedrpoCionntt(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::DragonMidpoint(3)
2
3
4

NAME

6       Math::PlanePath::DragonMidpoint -- dragon curve midpoints
7

SYNOPSIS

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

DESCRIPTION

14       This is the midpoint of each segment of the dragon curve of Heighway,
15       Harter, et al, per Math::PlanePath::DragonCurve.
16
17                           17--16           9---8                5
18                            |   |           |   |
19                           18  15          10   7                4
20                            |   |           |   |
21                           19  14--13--12--11   6---5---4        3
22                            |                           |
23                           20--21--22                   3        2
24                                    |                   |
25           33--32          25--24--23                   2        1
26            |   |           |                           |
27           34  31          26                       0---1    <- Y=0
28            |   |           |
29           35  30--29--28--27                                   -1
30            |
31           36--37--38  43--44--45--46                           -2
32                    |   |           |
33                   39  42  49--48--47                           -3
34                    |   |   |
35                   40--41  50                                   -4
36                            |
37                           51                                   -5
38                            |
39                           52--53--54                           -6
40                                    |
41           ..--64          57--56--55                           -7
42                |           |
43               63          58                                   -8
44                |           |
45               62--61--60--59                                   -9
46
47
48            ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
49           -10 -9  -8  -7  -6  -5  -4  -3  -2  -1  X=0  1
50
51       The dragon curve begins as follows.  The midpoints of each segment are
52       numbered starting from 0,
53
54            +--8--+     +--4--+
55            |     |     |     |
56            9     7     5     3
57            |     |     |     |                               |
58            +-10--+--6--+     +--2--+       rotate 45 degrees |
59                  |                 |                         v
60                 11                 1
61                  |                 |
62            +-12--+           *--0--+       * = Origin
63            |
64           ...
65
66       These midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc.  For this
67       "DragonMidpoint" path they're turned clockwise 45 degrees and shrunk by
68       sqrt(2) to be integer X,Y values a unit apart and initial direction to
69       the right.
70
71       The midpoints are distinct X,Y positions because the dragon curve
72       traverses each edge only once.
73
74       The dragon curve is self-similar in 2^level sections due to its
75       unfolding.  This can be seen in the midpoints too as for example above
76       N=0 to N=16 is the same shape as N=16 to N=32, with the latter rotated
77       90 degrees and in reverse.
78
79       For reference, Knuth in "Diamonds and Dragons" has a different
80       numbering for segment midpoints where the dragon orientation is
81       unchanged and instead multiply by 2 to have midpoints as integers.  For
82       example the first dragon midpoint at X=1/2,Y=0 is doubled out to
83       X=1,Y=0.  That can be obtained from the path here by
84
85           KnuthX = X - Y + 1
86           KnuthY = X + Y
87
88   Arms
89       Like the "DragonCurve" the midpoints fill a quarter of the plane and
90       four copies mesh together perfectly when rotated by 90, 180 and 270
91       degrees.  The "arms" parameter can choose 1 to 4 curve arms,
92       successively advancing.
93
94       For example "arms => 4" begins as follows, with N=0,4,8,12,etc being
95       the first arm (the same as the plain curve above), N=1,5,9,13 the
96       second, N=2,6,10,14 the third and N=3,7,11,15 the fourth.
97
98           arms => 4
99
100                           ...-107-103  83--79--75--71             6
101                                     |   |           |
102            68--64          36--32  99  87  59--63--67             5
103             |   |           |   |   |   |   |
104            72  60          40  28  95--91  55                     4
105             |   |           |   |           |
106            76  56--52--48--44  24--20--16  51                     3
107             |                           |   |
108            80--84--88  17--13---9---5  12  47--43--39 ...         2
109                     |   |           |   |           |  |
110           100--96--92  21   6---2   1   8  27--31--35 106         1
111             |           |   |           |   |          |
112           104  33--29--25  10   3   0---4  23  94--98-102    <- Y=0
113             |   |           |   |           |   |
114           ...  37--41--45  14   7--11--15--19  90--86--82        -1
115                         |   |                           |
116                        49  18--22--26  46--50--54--58  78        -2
117                         |           |   |           |   |
118                        53  89--93  30  42          62  74        -3
119                         |   |   |   |   |           |   |
120                65--61--57  85  97  34--38          66--70        -4
121                 |           |   |
122                69--73--77--81 101-105-...                        -5
123
124                                     ^
125            -6  -5  -4  -3  -2  -1  X=0  1   2   3   4   5
126
127       With four arms like this every X,Y point is visited exactly once,
128       because four arms of the "DragonCurve" traverse every edge exactly
129       once.
130
131   Tiling
132       Taking pairs of adjacent points N=2k and N=2k+1 gives little rectangles
133       with the following tiling of the plane repeating in 4x4 blocks.
134
135                +---+---+---+-+-+---+-+-+---+
136                |   | | |   | | |   | | |   |
137                +---+ | +---+ | +---+ | +---+
138                |   | | |9 8| | |   | | |   |
139                +-+-+---+-+-+-+-+-+-+-+-+-+-+
140                | | |   | |7|   | | |   | | |
141                | | +---+ | +---+ | +---+ | |
142                | | |   | |6|5 4| | |   | | |
143                +---+-+-+-+-+-+-+-+-+-+-+-+-+
144                |   | | |   | |3|   | | |   |
145                +---+ | +---+ | +---+ | +---+
146                |   | | |   | |2|   | | |   |
147                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
148                | | |   | | |0 1| | |   | | |   <- Y=0
149                | | +---+ | +---+ | +---+ | |
150                | | |   | | |   | | |   | | |
151                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
152                |   | | |   | | |   | | |   |
153                +---+ | +---+ | +---+ | +---+
154                |   | | |   | | |   | | |   |
155                +---+-+-+---+-+-+---+-+-+---+
156                             ^
157                            X=0
158
159       The pairs follow this pattern both for the main curve N=0 etc shown,
160       and also for the rotated copies per "Arms" above.  This tiling is in
161       the tilingsearch database as
162
163           <http://tilingsearch.org/HTML/data24/K02A.html>
164
165       Taking pairs N=2k+1 and N=2k+2, being each odd N and its successor,
166       gives a regular pattern too, but this time repeating in blocks of
167       16x16.
168
169           |||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
170           |||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
171           -||------||------||------||------||------||------||------||-----
172           -||------||------||------||------||------||------||------||-----
173           |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
174           |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
175           -----||------||------||------||------||------||------||------||-
176           -----||------||------||------||------||------||------||------||-
177           -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
178           -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
179           -||------||------||------||------||------||------||------||-----
180           -||------||------||------||------||------||------||------||-----
181           |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
182           |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
183           -----||------||------||------||------||------||------||------||-
184           -----||------||------||------||------||------||------||------||-
185           |||--||||||--||--||--||||||--||  ||--||||||--||--||--||||||--|||
186           |||--||||||--||--||--||||||--||  ||--||||||--||--||--||||||--|||
187           -||------||------||------||------||------||------||------||-----
188           -||------||------||------||------||------||------||------||-----
189           |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
190           |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
191           -----||------||------||------||------||------||------||------||-
192           -----||------||------||------||------||------||------||------||-
193           -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
194           -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
195           -||------||------||------||------||------||------||------||-----
196           -||------||------||------||------||------||------||------||-----
197           |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
198           |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
199           -----||------||------||------||------||------||------||------||-
200           -----||------||------||------||------||------||------||------||-
201
202   Curve from Midpoints
203       Since the dragon curve always turns left or right, never straight ahead
204       or reverse, its segments are alternately horizontal and vertical.
205       Rotated -45 degrees for the midpoints here this means alternately
206       "opposite diagonal" and "leading diagonal".  They fall on X,Y
207       alternately even or odd.  So the original dragon curve can be recovered
208       from the midpoints by choosing leading diagonal or opposite diagonal
209       segment according to X,Y even or odd, which is the same as N even or
210       odd.
211
212           DragonMidpoint                  dragon segment
213           --------------                 -----------------
214           "even" N==0 mod 2              opposite diagonal
215             which is X+Y==0 mod 2 too
216
217           "odd"  N==1 mod 2              leading diagonal
218             which is X+Y==1 mod 2 too
219
220                      /
221                     3         0 at X=0,Y=0 "even", opposite diagonal
222                    /          1 at X=1,Y=0 "odd", leading diagonal
223                    \          etc
224                     2
225                      \
226                \     /
227                 0   1
228                  \ /
229

FUNCTIONS

231       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
232       classes.
233
234       "$path = Math::PlanePath::DragonMidpoint->new ()"
235           Create and return a new path object.
236
237       "($x,$y) = $path->n_to_xy ($n)"
238           Return the X,Y coordinates of point number $n on the path.  Points
239           begin at 0 and if "$n < 0" then the return is an empty list.
240
241           Fractional positions give an X,Y position along a straight line
242           between the integer positions.
243
244       "$n = $path->n_start()"
245           Return 0, the first N in the path.
246
247   Level Methods
248       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
249           Return "(0, 2**$level - 1)", or for multiple arms return "(0, $arms
250           * 2**$level - 1)".
251
252           There are 2^level segments comprising the dragon, or arms*2^level
253           when multiple arms, numbered starting from 0.
254

FORMULAS

256   X,Y to N
257       An X,Y point is turned into N by dividing out digits of a complex base
258       i+1.  This base is per the doubling of the "DragonCurve" at each level.
259       In midpoint coordinates an adjustment subtracting 0 or 1 must be
260       applied to move an X,Y which is either N=2k or N=2k+1 to the position
261       where dividing out i+1 gives the N=k X,Y.
262
263       The adjustment is in a repeating pattern of 4x4 blocks.  Points N=2k
264       and N=2k+1 both move to the same place corresponding to N=k multiplied
265       by i+1.  The adjustment pattern is a little like the pair tiling shown
266       above, but for some pairs both the N=2k and N=2k+1 positions must move,
267       it's not enough just to shift the N=2k+1 to the N=2k.
268
269                   Xadj               Yadj
270           Ymod4              Ymod4
271             3 | 0 1 1 0        3 | 1 1 0 0
272             2 | 1 0 0 1        2 | 1 1 0 0
273             1 | 1 0 0 1        1 | 0 0 1 1
274             0 | 0 1 1 0        0 | 0 0 1 1
275               +--------          +--------
276                 0 1 2 3            0 1 2 3
277                  Xmod4              Xmod4
278
279       The same tables work for both the main curve and for the rotated copies
280       per "Arms" above.
281
282           until -1<=X<=0 and 0<=Y<=1
283
284             Xm = X - Xadj(X mod 4, Y mod 4)
285             Ym = Y - Yadj(X mod 4, Y mod 4)
286
287             new X,Y = (Xm+i*Ym) / (i+1)
288                     = (Xm+i*Ym) * (1-i)/2
289                     = (Xm+Ym)/2, (Ym-Xm)/2     # Xm+Ym and Ym-Xm are both even
290
291             Nbit = Xadj xor Yadj               # bits of N low to high
292
293       The X,Y reduction stops at one of the start points for the four arms
294
295           X,Y endpoint   Arm        +---+---+
296           ------------   ---        | 2 | 1 |  Y=1
297               0, 0        0         +---+---+
298               0, 1        1         | 3 | 0 |  Y=0
299              -1, 1        2         +---+---+
300              -1, 0        3         X=-1 X=0
301
302       For arms 1 and 3 the N bits must be flipped 0<->1.  The arm number and
303       hence whether this flip is needed is not known until reaching the
304       endpoint.
305
306       For bignum calculations there's no need to apply the "/2" shift in
307       newX=(Xm+Ym)/2 and newY=(Ym-Xm)/2.  Instead keep a bit position which
308       is the logical low end and pick out two bits from there for the
309       Xadj,Yadj lookup.  A whole word can be dropped when the bit position
310       becomes a multiple of 32 or 64 or whatever.
311
312   Boundary
313       Taking unit squares at each point, the boundary MB[k] of the resulting
314       shape from 0 to N=2^k-1 inclusive can be had from the boundary B[k] of
315       the plain dragon curve.  Taking points N=0 to N=2^k-1 inclusive is the
316       midpoints of the dragon curve line segments N=0 to N=2^k inclusive.
317
318           MB[k] = B[k] + 2
319                 = 4, 6, 10, 18, 30, 50, 86, 146, 246, 418, 710, 1202, ...
320
321                                    2 + x + 2*x^2
322           generating function  2 * -------------
323                                    1 - x - 2*x^3
324
325       A unit square at the midpoint is a diamond on a dragon line segment
326
327             / \
328            /   \         midpoint m
329           *--m--*        diamond on dragon curve line segment
330            \   /
331             \ /
332
333       A boundary segment of the dragon curve has two sides of the diamond
334       which are boundary.  But when the boundary makes a right hand turn two
335       such sides touch and are therefore not midpoint boundary.
336
337            /^\
338           / | \        right turn
339           \ | //\      two diamond sides touch
340            \|//  \
341             *<----*
342              \   /
343               \ /
344
345       The dragon curve at N=0 points East and the last segment N=2^k-1 to
346       N=2^k is North.  Since the curve never overlaps itself this means that
347       when going around the right side of the curve there is 1 more left turn
348       than right turn,
349
350           lefts - rights = 1
351
352       The total line segments on the right is the dragon curve R[k] and there
353       are R[k]-1 turns, so the total turns lefts+rights is
354
355           lefts + rights + 1 = R[k]
356
357       So the lefts and rights are obtained separately
358
359           2*lefts            = R[k]       adding the two equations
360           2*rights           = R[k] - 2   subtracting the two equations
361
362       The result is then
363
364           MR[k] = 2*R[k] - 2*rights
365                 = 2*R[k] - 2*(R[k]-2)/2
366                 = R[k] + 2
367
368       A similar calculation is made on the left side of the curve.  The net
369       turn is the same and so the same lefts-rights=1 and thus from the
370       dragon curve L[k] left boundary
371
372           ML[k] = 2*L[k] - 2*lefts
373                 = 2*L[k] - 2*(L[k]/2)
374                 = L[k]
375
376       The total is then
377
378           MB[k] = MR[k] + ML[k]
379                 = R[k]+2 + L[k]
380                 = B[k] + 2                 since B[k]=R[k]+L[k]
381
382       The generating function can be had from the partial fractions form of
383       the dragon curve boundary.  B[k]+2 means adding 2/(1-x) which cancels
384       out the -2/(1-x) in gB(x).
385

OEIS

387       The "DragonMidpoint" is in Sloane's Online Encyclopedia of Integer
388       Sequences as
389
390           <http://oeis.org/A073089> (etc)
391
392           A073089   abs(dY) of n-1 to n, so 0=horizontal,1=vertical
393                       (extra initial 0)
394           A077860   Y at N=2^k, being Re(-(i+1)^k + i-1)
395           A090678   0=straight, 1=not straight  (extra initial 1,1)
396           A203175   boundary of unit squares N=0 to N=2^k-1, value 4 onwards
397
398   A073089
399       For A073089=abs(dY), the midpoint curve is vertical when the
400       "DragonCurve" has a vertical followed by a left turn, or horizontal
401       followed by a right turn.  "DragonCurve" verticals are whenever N is
402       odd, and the turn is the bit above the lowest 0 in N (per "Turn" in
403       Math::PlanePath::DragonCurve).  So
404
405           abs(dY) = lowbit(N) XOR bit-above-lowest-zero(N)
406
407       The n in A073089 is offset by 2 from the N numbering of the path here,
408       so n=N+2.  The initial value at n=1 in A073089 has no corresponding N
409       (it would be N=-1).
410
411       The mod-16 definitions in A073089 express combinations of N odd/even
412       and bit-above-low-0 which are the vertical midpoint segments.  The
413       recurrence a(8n+1)=a(4n+1) acts to strip zeros above a low 1 bit,
414
415           n = 0b..uu0001
416            -> 0b...uu001
417
418       In terms of N=n-2 this reduces
419
420           N = 0b..vv1111
421            -> 0b...vv111
422
423       which has the effect of seeking a lowest 0 in the range of the mod-16
424       conditions.
425

SEE ALSO

427       Math::PlanePath, Math::PlanePath::DragonCurve,
428       Math::PlanePath::DragonRounded
429
430       Math::PlanePath::AlternatePaperMidpoint,
431       Math::PlanePath::R5DragonMidpoint, Math::PlanePath::TerdragonMidpoint
432

HOME PAGE

434       <http://user42.tuxfamily.org/math-planepath/index.html>
435

LICENSE

437       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
438       Kevin Ryde
439
440       Math-PlanePath is free software; you can redistribute it and/or modify
441       it under the terms of the GNU General Public License as published by
442       the Free Software Foundation; either version 3, or (at your option) any
443       later version.
444
445       Math-PlanePath is distributed in the hope that it will be useful, but
446       WITHOUT ANY WARRANTY; without even the implied warranty of
447       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
448       General Public License for more details.
449
450       You should have received a copy of the GNU General Public License along
451       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
452
453
454
455perl v5.32.1                      2021-01-27Math::PlanePath::DragonMidpoint(3)
Impressum