Source Browser ?

if not modules then modules = { } end modules ['mlib-ran'] = {
2    version   = 1.001,
3    comment   = "companion to mlib-ctx.mkiv",
4    author    = "Hans Hagen, PRAGMA-ADE, Hasselt NL",
5    copyright = "PRAGMA ADE / ConTeXt Development Team",
6    license   = "see context related readme files",
7}
8
9local next = next
local ceil, floor, random, sqrt, cos, sin, pi, max, min = math.ceil, math.floor, math.random, math.sqrt, math.cos, math.sin, math.pi, math.min, math.max
11local remove = table.remove
12
13-- Below is a bit of rainy saturday afternoon hobyism, while listening to Judith
14-- Owens redisCOVERed (came there via Leland Sklar who I have on a few live blurays;
15-- and who is also on YT). (Also nice: https://www.youtube.com/watch?v=GXqasIRaxlA)
16
17-- When Aditya pointed me to an article on mazes I ended up at poison distributions
18-- which to me looks nicer than what I normally do, fill a grid and then randomize
19-- the resulting positions. With some hooks this can be used for interesting patterns
20-- too. A few links:
21--
22-- https://bost.ocks.org/mike/algorithms/#maze-generation
23-- https://extremelearning.com.au/
24-- https://www.jasondavies.com/maps/random-points/
25-- http://devmag.org.za/2009/05/03/poisson-disk-sampling
26
27-- The next function is quite close to what us discribed in the poisson-disk-sampling
28-- link mentioned before. One can either use a one dimensional grid array or a two
29-- dimensional one. The example code uses some classes dealing with points. In the
30-- process I added some more control.
31
32-- we could do without the samplepoints list
33
34local function poisson(width, height, mindist, newpointscount, initialx, initialy)
35    local starttime       = os.clock()
36    local cellsize        = mindist / sqrt(2)
37    local nofwidth        = ceil(width // cellsize)
38    local nofheight       = ceil(height // cellsize)
39    local grid            = lua.newtable(nofwidth,0) -- table.setmetatableindex("table")
    local firstx          = initialx or random() * width
    local firsty          = initialy or random() * height
42    local firstpoint      = { firstx, firsty, 1 }
43 -- local samplepoints    = { firstpoint }
44    local processlist     = { firstpoint }
45    local nofprocesslist  = 1
46    local nofsamplepoints = 1
47    local twopi           = 2 * pi
48
49    for i=1,nofwidth do
50        local g = lua.newindex(nofheight,false)
51        grid[i] = g
52    end
53
54    local x = floor(firstx // cellsize) + 1 -- lua indices
55    local y = floor(firsty // cellsize) + 1 -- lua indices
56
57    x = max(1, min(x, width  - 1))
58    y = max(1, min(y, height - 1))
59
60    grid[x][y] = firstpoint
61
62    -- The website shows graphic for this 5*5 grid snippet, if we use a one dimentional
63    -- array then we could have one loop; a first version used a metatable trick so we
64    -- had grid[i+gx][j+gy] but we no we also return the grid, so ... we now just check.
65
66    -- There is no need for the samplepoints list as we can get that from the grid but
67    -- instead we can store the index with the grid.
68
69    while nofprocesslist > 0 do
        local point = remove(processlist,random(1,nofprocesslist))
71        nofprocesslist = nofprocesslist - 1
72        for i=1,newpointscount do -- we start at 1
            local radius = mindist * (random() + 1)
            local angle  = twopi * random()
75            local nx     = point[1] + radius * cos(angle)
76            local ny     = point[2] + radius * sin(angle)
77            if nx > 1 and ny > 1 and nx <= width and ny <= height then -- lua indices
78                local gx = floor(nx // cellsize)
79                local gy = floor(ny // cellsize)
80                -- the 5x5 cells around the point
81                for i=-2,2 do
82                    for j=-2,2 do
83                        local cell = grid[i + gx]
84                        if cell then
85                            cell = cell[j + gy]
86                            if cell and sqrt((cell[1] - nx)^2 + (cell[2] - ny)^2) < mindist then
87                                goto next
88                            end
89                        end
90                    end
91                end
92             -- local newpoint  = { nx, ny }
93                nofprocesslist  = nofprocesslist + 1
94                nofsamplepoints = nofsamplepoints + 1
95                local newpoint  = { nx, ny, nofsamplepoints }
96                processlist [nofprocesslist]  = newpoint
97             -- samplepoints[nofsamplepoints] = newpoint
98                grid[gx][gy] = newpoint
99            end
100            ::next::
101        end
102    end
103
104    return {
105        count  = nofsamplepoints,
106     -- points = samplepoints,
107        grid   = grid,
108        time   = os.clock() - starttime,
109    }
110end
111
112-- For now:
113
local randomizers     = utilities.randomizers or { }
utilities.randomizers = randomizers
116randomizers.poisson   = poisson
117
118-- The MetaFun interface:
119
120local formatters = string.formatters
121local concat = table.concat
122
123local f_macro = formatters["%s(%N,%N);"]
124
125local f_macros = {
126    [2] = formatters["%s(%N,%N);"],
127    [3] = formatters["%s(%N,%N,%i);"],
128    [4] = formatters["%s(%N,%N,%i,%i);"],
129}
130
131local function grid_to_mp(t,f,n)
132    local grid   = t.grid
133    local count  = t.count
134    local result = { }
135    local r      = 0
136    local macro  = f or "draw"
137    local runner = f_macros[n or 2] or f_macros[2]
138    for i=1,#grid do
139        local g = grid[i]
140        if g then
141            for j=1,#g do
142                local v = g[j]
143                if v then
144                    r = r + 1
145                    result[r] = runner(macro,v[1],v[2],v[3],count)
146                end
147            end
148        end
149    end
150    return concat(result, " ")
151end
152
153local getparameter = metapost.getparameter
154
155local function lmt_poisson()
156    local initialx = getparameter { "initialx" }
157    local initialy = getparameter { "initialy" }
158    local width    = getparameter { "width" }
159    local height   = getparameter { "height" }
160    local distance = getparameter { "distance" }
161    local count    = getparameter { "count" }
162
163    local result = poisson (
164        width, height, distance, count,
165        initialx > 0 and initialx or false,
166        initialy > 0 and initialy or false
167    )
168
169    if result then
170        logs.report("poisson","w=%N, h=%N, d=%N, c=%N, n=%i, runtime %.3f",
171            width, height, distance, count, result.count, result.time
172        )
173    end
174
175    return result
176end
177
178function mp.lmt_poisson_generate()
179    local result = lmt_poisson()
180    if result then
181        return grid_to_mp (
182            result,
183            getparameter { "macro" },
184            getparameter { "arguments" }
185        )
186    end
187end
188
189-- -- some playing around showed no benefit
190--
191-- function points_to_mp(t,f)
192--     local points = t.points
193--     local count  = t.count
194--     local result = { }
195--     local r      = 0
196--     local macro  = f or "draw"
197--     local runner = f_macros[n or 2] or f_macros[2]
198--     for i=1,count do
199--         local v = points[i]
200--         r = r + 1
201--         result[r] = runner(macro,v[1],v[2],v[3],count)
202--     end
203--     return concat(result, " ")
204-- end
205--
206-- local result  = false
207-- local i, j, n = 0, 0, 0
208--
209-- function mp.lmt_poison_start()
210--     result = lmt_poisson()
211-- end
212--
213-- function mp.lmt_poisson_stop()
214--     result = false
215-- end
216--
217-- function mp.lmt_poisson_count()
218--     return result and result.count or 0
219-- end
220--
221-- function mp.lmt_poisson_get(i)
222--     if result then
223--         return mp.pair(result.points[i])
224--     end
225-- end
226--
227-- function mp.lmt_poisson_generate()
228--     mp.lmt_poisson_start()
229--     if result then
230--         return grid_to_mp (
231--             result,
232--             getparameter { "macro" },
233--             getparameter { "arguments" }
234--         )
235--     end
236--     mp.lmt_poisson_stop()
237-- end
238