1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
divert(-1)
# Copyright 2013 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/>.
# Usage: m4 dragon.m4
#
# This is a bit of fun generating the dragon curve with the predicate
# algorithms of xy_is_visited() from DragonMidpoint and DragonCurve. The
# output is generated row by row and and column by column with no image
# array or storage.
#
# The macros which return a pair of values x,y expand to an unquoted 123,456
# which is suitable as arguments to a further macro. The quoting is slack
# because the values are always integers and so won't suffer unwanted macro
# expansion.
# 0,1 Vertex and segment x,y numbering.
# |
# | Segments are numbered as if a
# |s=0,1 square grid turned anti-clockwise
# | by 45 degrees.
# |
# -1,0 -------- 0,0 -------- 1,0 vertex_to_seg_east(x,y) returns
# s=-1,1 | s=0,0 the segment x,y to the East,
# | so vertex_to_seg_east(0,0) is 0,0
# |
# |s=-1,0 vertex_to_seg_west(x,y) returns
# | the segment x,y to the West,
# 0,-1 so vertex_to_seg_west(0,0) is -1,1
#
define(`vertex_to_seg_east', `eval($1 + $2), eval($2 - $1)')
define(`vertex_to_seg_west', `eval($1 + $2 - 1), eval($2 - $1 + 1)')
define(`vertex_to_seg_south', `eval($1 + $2 - 1), eval($2 - $1)')
# Some past BSD m4 didn't have "&" operator, so mod2(n) using % instead.
# mod2() returns 0,1 even if "%" gives -1 for negative odds.
#
define(`mod2', `ifelse(eval($1 % 2),0,0,1)')
# seg_to_even(x,y) returns x,y moved to an "even" position by subtracting an
# offset in a way which suits the segment predicate test.
#
# seg_offset_y(x,y) is a repeating pattern
#
# | 1,1,0,0
# | 1,1,0,0
# | 0,0,1,1
# | 0,0,1,1
# +---------
#
# seg_offset_x(x,y) is the same but offset by 1 in x,y
#
# | 0,1,1,0
# | 1,0,0,1
# | 1,0,0,1
# | 0,1,1,0
# +---------
#
# Incidentally these offset values also give n which is the segment number
# along the curve. "x_offset XOR y_offset" is 0,1 and is a bit of n from
# low to high.
#
define(`seg_offset_y', `mod2(eval(($1 >> 1) + ($2 >> 1)))')
define(`seg_offset_x', `seg_offset_y(eval($1+1), eval($2+1))')
define(`seg_to_even', `eval($1 - seg_offset_x($1,$2)),
eval($2 - seg_offset_y($1,$2))');
# xy_div_iplus1(x,y) returns x,y divided by complex number i+1.
# So (x+i*y)/(i+1) which means newx = (x+y)/2, newy = (y-x)/2.
# Must have x,y "even", meaning x+y even, so newx and newy are integers.
#
define(`xy_div_iplus1', `eval(($1 + $2)/2), eval(($2 - $1)/2)')
# seg_is_final(x,y) returns 1 if x,y is one of the final four points.
# On these four points xy_div_iplus1(seg_to_even(x,y)) returns x,y
# unchanged, so the seg_pred() recursion does not reduce any further.
#
# .. | ..
# final | final y=+1
# final | final y=0
# -------+--------
# .. | ..
# x=-1 x=0
#
define(`seg_is_final', `eval(($1==-1 || $1==0) && ($2==1 || $2==0))')
# seg_pred(x,y) returns 1 if segment x,y is on the dragon curve.
# If the final point reached is 0,0 then the original x,y was on the curve.
# (If a different final point then x,y was one of four rotated copies of the
# curve.)
#
define(`seg_pred', `ifelse(seg_is_final($1,$2), 1,
`eval($1==0 && $2==0)',
`seg_pred(xy_div_iplus1(seg_to_even($1,$2)))')')
# vertex_pred(x,y) returns 1 if point x,y is on the dragon curve.
# The curve always turns left or right at a vertex, it never crosses itself,
# so if a vertex is visited then either the segment to the east or to the
# west must have been traversed. Prefer ifelse() for the two checks since
# eval() || operator is not a short-circuit.
#
define(`vertex_pred', `ifelse(seg_pred(vertex_to_seg_east($1,$2)),1,1,
`seg_pred(vertex_to_seg_west($1,$2))')')
# forloop(varname, start,end, body)
# Expand body with varname successively define()ed to integers "start" to
# "end" inclusive. "start" to "end" can go either increasing or decreasing.
#
define(`forloop', `define(`$1',$2)$4`'dnl
ifelse($2,$3,,`forloop(`$1',eval($2 + 2*($2 < $3) - 1), $3, `$4')')')
#----------------------------------------------------------------------------
# dragon01(xmin,xmax, ymin,ymax) prints an array of 0s and 1s which are the
# vertex_pred() values. `y' runs from ymax down to ymin so that y
# coordinate increases up the screen.
#
define(`dragon01',
`forloop(`y',$4,$3, `forloop(`x',$1,$2, `vertex_pred(x,y)')
')')
# dragon_ascii(xmin,xmax, ymin,ymax) prints an ascii art dragon curve.
# Each y value results in two output lines. The first has "+" vertices and
# "--" horizontals. The second has "|" verticals.
#
define(`dragon_ascii',
`forloop(`y',$4,$3,
`forloop(`x',$1,$2,
`ifelse(vertex_pred(x,y),1, `+', ` ')dnl
ifelse(seg_pred(vertex_to_seg_east(x,y)), 1, `--', ` ')')
forloop(`x',$1,$2,
`ifelse(seg_pred(vertex_to_seg_south(x,y)), 1, `| ', ` ')')
')')
#--------------------------------------------------------------------------
divert`'dnl
# 0s and 1s directly from vertex_pred().
#
dragon01(-7,23, dnl X range
-11,10) dnl Y range
# ASCII art lines.
#
dragon_ascii(-6,5, dnl X range
-10,2) dnl Y range
|
