代码

Question

在这个答案由 @Jake 回答这个问题在TikZ中用随机点填充指定区域我了解了泊松盘采样技术来生成美观的随机图案。

Jake 的回答提供了一个页面链接，其中介绍了该算法详细描述，并提供了部分实现（Java、Python和Ruby）。

当然，这立即激发了我去做一个 lualatex 实现的冲动，它将允许从 tikz 生成这种类型的模式。

所以我做了。所以这不是一个真正的问题，因为我有答案（我会简短地发布），但我需要分享它 :-)

但我不想错过询问这项技术在 tikz 中的出色应用的机会。在我的回答中，我将重点介绍模式生成，但也许比我更有想象力的人可以想到更多精彩的展示（例如，标签云生成？）

Answer 1

正如承诺的那样，这是我的实现。它由两个文件组成：

• poisson.lua包含算法的 Lua 实现描述在这里。“主要”函数是，generate_poisson()它返回一个 Lua 点数组，每个点都是一对 (x,y)。此外，还poisson_points_list()提供了函数，它将生成的数据转换为generate_poisson()可以输入到 TikZforeach循环中的数据。
• poisson.sty只是一个使用 TeX 语法调用 Lua 函数的包装器。它提供了\poissonpointslist接收四个参数的宏：要填充的区域的宽度和高度、点之间允许的最小距离以及算法某些步骤中生成的“点数”，通常为 20 或 30。值越小，执行速度越快，但填充区域的某些区域可能会有较少的点。

使用它的预期方式是使用给定的一组参数来评估宏并将结果存储在另一个宏中，例如：

\edef\mylist{\poissonpointslist{5}{5}{1}{20}}

然后这个新的宏可以用作\foreach循环的一部分，如下所示：

\foreach \x,\y in \mylist { ... }

根据循环中的代码，我们可以生成各种有趣的设计（参见“示例”部分）。

代码

泊松

\directlua{dofile("poisson.lua")}
\newcommand{\poissonpointslist}[4]{
    \directlua{poisson_points_list(#1,#2,#3,#4)}
}

泊松.lua

-- This is a lua implementation of the algorithm described in
-- http://devmag.org.za/2009/05/03/poisson-disk-sampling/
--
-- The structure of the algorithm is exactly the same than in 
-- the mentioned article. Its pseudo-code snippets were translated
-- to Lua.
--
-- One detail worths an explanation, though. The article uses a 2D matrix
-- called grid to store coordinates of points. In the article, it is
-- assumed that grid elements can be accesed via grid[point], being point
-- some structure with a pair of x and y integers, so grid[point] should
-- be equivalent to grid[x,y] or grid[x][y]. This grid is assumed to be
-- initially dimensioned and filled by nils.
--
-- In my implementation the grid is dynamic, and it is an associative array
-- indexed by string keys in the form grid["(x,y)"]. The function gridToString()
-- can be used to convert a Point to its string form, so the grid is indeed
-- accesed like this: grid[gridToString(p)] being p a Point with integer
-- coordinates (which in fact is found via imageToGrid, like in the article)

-- UTILITY FUNCTIONS (used in the article, without giving implementation)
-- =====================================================================

-- RandomQueue stores values and gives them in random order
RandomQueue = {}
function RandomQueue.new ()
    return {last=-1}
end

function RandomQueue.push(q, item) 
    local last = q.last + 1
    q.last = last
    q[last] = item
end

function RandomQueue.pop(q)
    if (RandomQueue.empty(q)) then 
        return nil
    end
    local index = math.random(0,q.last) 
    -- A random index is generated. The last element
    -- is swaped with this random item, and the new
    -- last item is popped.
    local last = q.last
    item = q[index]
    q[index] = q[last]
    q[last] = nil
    q.last = last -1
    return item
end

function RandomQueue.empty(q)
    return q.last==-1
end

function RandomQueue.print(q)
    -- For debugging. Not used
    local t = {}
    for i=0, q.last do
        table.insert(t, string.format("(%f,%f)", q[i].x, q[i].y))
    end
    print (string.format("RandomQueue %d elem: %s", q.last+1, table.concat(t, " ")))
end

-- Point stores a coordinate pair
Point = {}

function Point.new(x,y)
    return {x=x, y=y}
end

-- Determines if a point is inside the rendered rectangle
function inRectangle(point, width, height)
  return (point.x>0 and point.y>0 and point.x<width and point.y<height)
end

-- Converts a point to a string representation, to be used as index in the grid
function gridToString(gridPoint)
    return string.format("(%d,%d)", gridPoint.x, gridPoint.y)
end

-- Computes the distance between two points
function distance(p1, p2)
    return math.sqrt(math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2))
end

-- Prints the grid. For debugging. Not used
function printGrid(grid)
    print "==========="
    for k,v in pairs(grid) do
        print (string.format("%s:  %f, %f", k, v.x, v.y))
    end
end

-- THE FUNCTIONS GIVEN IN THE ARTICLE
-- This is the lua implementation of the pseudocode in the article


function generate_poisson(width, height, min_dist, new_points_count)
    local cellSize = min_dist/math.sqrt(2)
    local grid = {} -- Point.new(math.ceil(width/cellSize), math.ceil(height/cellSize))}
    local processList = RandomQueue.new()
    local samplePoints = {};  -- Empty list

    -- Generate the first point
    local firstPoint = Point.new(math.random()*width, math.random()*height)
    -- print (string.format("newPoint: [%f, %f]", firstPoint.x, firstPoint.y))
    RandomQueue.push(processList, firstPoint)
    table.insert(samplePoints, firstPoint)
    grid[gridToString(imageToGrid(firstPoint, cellSize))] = firstPoint

    -- Generate other points from points in queue
    while (not RandomQueue.empty(processList)) do
        -- RandomQueue.print(processList)
        -- printGrid(grid)
        local point = RandomQueue.pop(processList)
        for i=0,new_points_count do
            local newPoint = generateRandomPointAround(point, min_dist)
            -- print (string.format("newPoint: [%f, %f]", newPoint.x, newPoint.y))
            -- Check the point is in the region and not too close
            -- to other points
            if inRectangle(newPoint, width, height) and 
                not inNeighbourhood(grid, newPoint, min_dist, cellSize) then
                -- In this case, the point is accepted
                RandomQueue.push(processList, newPoint)
                table.insert(samplePoints, newPoint)
                grid[gridToString(imageToGrid(newPoint, cellSize))] = newPoint;
            end
        end
    end
    return samplePoints
end

function imageToGrid(point, cellSize)
    local gridX = math.floor(point.x/cellSize)
    local gridY = math.floor(point.y/cellSize)
    return Point.new(gridX, gridY)
end

function generateRandomPointAround(point, mindist)
    local r1 = math.random()
    local r2 = math.random()
    local radius  = mindist * (r1+1)
    local angle   = 2 * math.pi * r2
    newX = point.x + radius * math.cos(angle)
    newY = point.y + radius * math.sin(angle)
    return Point.new(newX, newY)
end

function inNeighbourhood(grid, point, mindist, cellSize)
    local gridPoint = imageToGrid(point, cellSize)
    cellsAroundPoint = squareAroundPoint(grid, gridPoint, 5)
    for k,cell in pairs(cellsAroundPoint) do
        if not (cell==nil) then
            local d = distance(cell, point)
            if distance(cell, point) < mindist then
                return true
            end
        end
    end
    return false
end

-- This one is not given in the article. It returns the
-- values of several cells around the give gridPoint
-- We are using string indexes for the grid, but if we
-- try to access to a key which is not stored, lua gives
-- nil instead of an exception, so it works as expected
-- because we get nils for cells which have no dot inside
function squareAroundPoint(grid, gridPoint, n)
    local extreme = math.floor(n/2)
    local result = {}
    for i=-extreme,extreme do
        for j=-extreme,extreme do
            ii = i + gridPoint.x
            jj = j + gridPoint.y
            data = grid[gridToString(Point.new(ii,jj))]
            if data == nil then
                repr = "nil"
            else
                repr = string.format("(%f,%f)", data.x, data.y)
            end
            table.insert(result, data)
        end
    end
    return result
end


-- Initialize random seed
math.randomseed(os.time())

-- Function to generate the list of dots in a tikz's foreach compatible syntax
function poisson_points_list(width, height, mindist, add_points)
    local data = generate_poisson(width, height, mindist, add_points)
    local str = {}
    for k,v in pairs(data) do
        table.insert(str, string.format("%f/%f", v.x, v.y))
    end
    tex.print(table.concat(str, ", "))
end

例子

1. 密集分布。只需在每个坐标上画一个点：

\documentclass{article}
\usepackage{tikz}
\usepackage{poisson}
\begin{document}
\edef\mylist{\poissonpointslist{5}{5}{0.1}{20}}  % very dense, very slow
\begin{tikzpicture}
     \clip (0,0) rectangle (5,5);
     \foreach \x/\y in \mylist {
       \fill (\x,\y) circle(1pt);
     }
     \draw[very thick] (0,0) rectangle(5,5);
\end{tikzpicture}
\end{document}

2. 稀疏分布。在每个点绘制一个具有随机半径的实体圆盘：

\edef\mylist{\poissonpointslist{5}{5}{0.7}{10}}  % Sparse, fast
\begin{tikzpicture}
    \clip (0,0) rectangle (5,5);
    \foreach \x/\y in \mylist {
      \pgfmathsetmacro{\radius}{1+7*rnd}
      \fill (\x,\y) circle(\radius pt);
    }
    \draw[very thick] (0,0) rectangle(5,5);
\end{tikzpicture}

3. 稀疏密度，在每个坐标处使用花朵图片，随机化大小和角度

\tikzset{
    flower/.pic = {
       \foreach \a in {0,60,...,350}{
         \filldraw[fill=white, draw=black!30, rotate=\a+30] (0.8,0) ellipse(0.6 and 0.3);
         \filldraw[fill=white, draw=black!30, rotate=\a] (0.8,0) ellipse(0.8 and 0.3);
        }
       \filldraw[draw=orange, top color=yellow, bottom color=orange] (0,0) circle(0.4);
    },
}
\edef\mylist{\poissonpointslist{5}{5}{0.7}{10}}  % Sparse, fast
\begin{tikzpicture}
    \clip (0,0) rectangle (5,5);
    \foreach \x/\y in \mylist {
      \pgfmathsetmacro{\size}{0.15+0.1*rnd}
      \pgfmathsetmacro{\angle}{60*rnd}
      \path (\x,\y) pic[scale=\size, rotate=\angle] {flower};
    }
    \draw[very thick] (0,0) rectangle(5,5);
\end{tikzpicture}

4. 更加密集，在每个坐标处使用一个气泡图，随机化大小

\tikzset{
    bubble/.pic = {
       \fill[top color=blue!50!cyan!40!white, bottom color=blue!40!black] circle(0.1);
       \fill[white] (110:0.06) circle(0.02);
    }
}
\edef\mylist{\poissonpointslist{5}{5}{0.2}{15}}  % Dense slow
\begin{tikzpicture}
     \clip (0,0) rectangle (5,5);
     \fill[top color=blue!60!cyan, bottom color=blue!70!black] (0,0) rectangle (5,5);
     \foreach \x/\y in \mylist {
       \pgfmathsetmacro{\size}{0.5+0.5*rnd}
       \path (\x,\y) pic[scale=\size]{bubble};
     }
     \draw[very thick] (0,0) rectangle(5,5);
\end{tikzpicture}

5. 与气泡相同的密度，使用具有随机角度和颜色的线段

\edef\mylist{\poissonpointslist{5}{5}{0.2}{15}}  % Dense slow
\begin{tikzpicture}
     \clip (0,0) rectangle (5,5);
     \fill[orange!10] (0,0) rectangle (5,5);
     \foreach \x/\y in \mylist {
       \pgfmathsetmacro{\shade}{50*rnd}
       \pgfmathsetmacro{\w}{0.4+0.8*rnd}
       \draw[orange!50!black!\shade!white, line width=\w pt] (\x,\y) -- +(180*rnd:3pt);
     }
     \draw[very thick] (0,0) rectangle(5,5);
\end{tikzpicture}

更新：奖金

为了庆祝赏金，我扩展了答案，考虑了一些有关返回列表顺序的因素\poissonpointslist，并提出了一些更改它的想法。我还将所有非全局必需的标识符设为本地标识符，正如 Aditya 在评论中所建议的那样（这也迫使更改了 lua 文件中声明函数的顺序）。我将新代码粘贴在最后。

列表顺序

返回的坐标列表\poissonpoinstslist按照算法生成点的顺序排列。它从区域中的随机点开始，然后尝试找到一些不会与其他已设置的点“碰撞”的邻居。点网格的增长模式是随机的，但总是围绕着一个核心，就像溶解的结晶一样。

如果我们在处理列表时改变绘制每个点的颜色，就可以使模式变得可见，如下例所示（它还打印每个节点内的索引）：

\documentclass{article}

% This makes always the same "random" list, for comparison purposes
\directlua{ math.randomseed(1); }  
\edef\mylist{\poissonpointslist{5}{5}{0.4}{20}}

\tikzset{
    disc/.style={
        circle, draw, fill=#1, font=\tiny,
        inner sep=0pt, minimum size=5mm,
    },
    disc/.default=white,
}

\begin{tikzpicture}
    \fill[black!20] (0,0) rectangle (5,5);
    \foreach [count=\i] \x/\y in \mylist {
        \pgfmathsetmacro{\tint}{100-\i/2}
        \node[disc=orange!50!white!\tint!black] at (\x,\y) {\i};
     }
\end{tikzpicture}

结果如下：

算法生成的第一个坐标标记为“1”，填充颜色较亮。第二个坐标标记为“2”，填充颜色稍暗，依此类推。不断增长的图案可以看作是黑暗的渐变。

在某些情况下，列表的顺序可能不取决于算法生成点的顺序，而是采用其他顺序。例如，如果我们想从左到右、从上到下绘制点，则最好将标记为“85”的点确实是第一个，“26”是第二个，依此类推。

在最后粘贴的代码中，我提供了一个\poissonpointslistordered尝试执行此操作的新函数（尽管排序并不完美，因为由于坐标的随机性，没有清晰的“行”）。使用此顺序以及与上面相同的代码（仅更改\poissonpointslist为\poissonpointslistordered），结果现在是：

这个有序列表可以用于创建如下的一些效果：

\begin{tikzpicture}
    \fill[black!20] (0,0) rectangle (5,5);
    \foreach [count=\i] \x/\y in \mylist {
        \pgfmathsetmacro{\radius}{3+int(\i/5)/4}
        \fill[black!60] (\x,\y) circle (\radius pt);
     }
\end{tikzpicture}

新代码

泊松

\directlua{dofile("poisson.lua")}
\newcommand{\poissonpointslist}[4]{
    \directlua{poisson_points_list(#1,#2,#3,#4)}
}
\newcommand{\poissonpointslistordered}[4]{
    \directlua{poisson_points_list_ordered(#1,#2,#3,#4)}
}

泊松.lua

-- This is a lua implementation of the algorithm described in
-- http://devmag.org.za/2009/05/03/poisson-disk-sampling/
--
-- The structure of the algorithm is exactly the same than in 
-- the mentioned article. Its pseudo-code snippets were translated
-- to Lua.
--
-- One detail worths an explanation, though. The article uses a 2D matrix
-- called grid to store coordinates of points. In the article, it is
-- assumed that grid elements can be accesed via grid[point], being point
-- some structure with a pair of x and y integers, so grid[point] should
-- be equivalent to grid[x,y] or grid[x][y]. This grid is assumed to be
-- initially dimensioned and filled by nils.
--
-- In my implementation the grid is dynamic, and it is an associative array
-- indexed by string keys in the form grid["(x,y)"]. The function gridToString()
-- can be used to convert a Point to its string form, so the grid is indeed
-- accesed like this: grid[gridToString(p)] being p a Point with integer
-- coordinates (which in fact is found via imageToGrid, like in the article)

-- UTILITY FUNCTIONS (used in the article, without giving implementation)
-- =====================================================================

-- RandomQueue stores values and gives them in random order
local RandomQueue = {}
function RandomQueue.new ()
    return {last=-1}
end

function RandomQueue.push(q, item) 
    local last = q.last + 1
    q.last = last
    q[last] = item
end

function RandomQueue.pop(q)
    if (RandomQueue.empty(q)) then 
        return nil
    end
    local index = math.random(0,q.last) 
    -- A random index is generated. The last element
    -- is swaped with this random item, and the new
    -- last item is popped.
    local last = q.last
    item = q[index]
    q[index] = q[last]
    q[last] = nil
    q.last = last -1
    return item
end

function RandomQueue.empty(q)
    return q.last==-1
end

function RandomQueue.print(q)
    -- For debugging. Not used
    local t = {}
    for i=0, q.last do
        table.insert(t, string.format("(%f,%f)", q[i].x, q[i].y))
    end
    print (string.format("RandomQueue %d elem: %s", q.last+1, table.concat(t, " ")))
end

-- Point stores a coordinate pair
local Point = {}

function Point.new(x,y)
    return {x=x, y=y}
end

-- Determines if a point is inside the rendered rectangle
local function inRectangle(point, width, height)
  return (point.x>0 and point.y>0 and point.x<width and point.y<height)
end

-- Converts a point to a string representation, to be used as index in the grid
local function gridToString(gridPoint)
    return string.format("(%d,%d)", gridPoint.x, gridPoint.y)
end

-- Computes the distance between two points
local function distance(p1, p2)
    return math.sqrt(math.pow(p2.x-p1.x,2) + math.pow(p2.y-p1.y,2))
end

-- Prints the grid. For debugging. Not used
local function printGrid(grid)
    print "==========="
    for k,v in pairs(grid) do
        print (string.format("%s:  %f, %f", k, v.x, v.y))
    end
end

-- THE FUNCTIONS GIVEN IN THE ARTICLE
local function imageToGrid(point, cellSize)
    local gridX = math.floor(point.x/cellSize)
    local gridY = math.floor(point.y/cellSize)
    return Point.new(gridX, gridY)
end

local function generateRandomPointAround(point, mindist)
    local r1 = math.random()
    local r2 = math.random()
    local radius  = mindist * (r1+1)
    local angle   = 2 * math.pi * r2
    newX = point.x + radius * math.cos(angle)
    newY = point.y + radius * math.sin(angle)
    return Point.new(newX, newY)
end

-- This one is not given in the article. It returns the
-- values of several cells around the give gridPoint
-- We are using string indexes for the grid, but if we
-- try to access to a key which is not stored, lua gives
-- nil instead of an exception, so it works as expected
-- because we get nils for cells which have no dot inside
local function squareAroundPoint(grid, gridPoint, n)
    local extreme = math.floor(n/2)
    local result = {}
    for i=-extreme,extreme do
        for j=-extreme,extreme do
            ii = i + gridPoint.x
            jj = j + gridPoint.y
            data = grid[gridToString(Point.new(ii,jj))]
            if data == nil then
                repr = "nil"
            else
                repr = string.format("(%f,%f)", data.x, data.y)
            end
            table.insert(result, data)
        end
    end
    return result
end

local function inNeighbourhood(grid, point, mindist, cellSize)
    local gridPoint = imageToGrid(point, cellSize)
    cellsAroundPoint = squareAroundPoint(grid, gridPoint, 5)
    for k,cell in pairs(cellsAroundPoint) do
        if not (cell==nil) then
            local d = distance(cell, point)
            if distance(cell, point) < mindist then
                return true
            end
        end
    end
    return false
end

-- This is the lua implementation of the pseudocode in the article
function generate_poisson(width, height, min_dist, new_points_count)
    local cellSize = min_dist/math.sqrt(2)
    local grid = {} -- Point.new(math.ceil(width/cellSize), math.ceil(height/cellSize))}
    local processList = RandomQueue.new()
    local samplePoints = {};  -- Empty list

    -- Generate the first point
    local firstPoint = Point.new(math.random()*width, math.random()*height)
    -- print (string.format("newPoint: [%f, %f]", firstPoint.x, firstPoint.y))
    RandomQueue.push(processList, firstPoint)
    table.insert(samplePoints, firstPoint)
    grid[gridToString(imageToGrid(firstPoint, cellSize))] = firstPoint

    -- Generate other points from points in queue
    while (not RandomQueue.empty(processList)) do
        -- RandomQueue.print(processList)
        -- printGrid(grid)
        local point = RandomQueue.pop(processList)
        for i=0,new_points_count do
            local newPoint = generateRandomPointAround(point, min_dist)
            -- print (string.format("newPoint: [%f, %f]", newPoint.x, newPoint.y))
            -- Check the point is in the region and not too close
            -- to other points
            if inRectangle(newPoint, width, height) and 
                not inNeighbourhood(grid, newPoint, min_dist, cellSize) then
                -- In this case, the point is accepted
                RandomQueue.push(processList, newPoint)
                table.insert(samplePoints, newPoint)
                grid[gridToString(imageToGrid(newPoint, cellSize))] = newPoint;
            end
        end
    end
    return samplePoints
end


-- Initialize random seed
math.randomseed(os.time())


-- Function to generate the list of dots in a tikz's foreach compatible syntax
function poisson_points_list(width, height, mindist, add_points)
    local data = generate_poisson(width, height, mindist, add_points)
    local str = {}
    for k,v in ipairs(data) do
        table.insert(str, string.format("%f/%f", v.x, v.y))
    end
    tex.print(table.concat(str, ", "))
end

-- Function similar to the above, but the returned list is "ordered"
-- so that the points are more or less in the left-to-right, 
-- top-to-down order
function poisson_points_list_ordered(width, height, mindist, add_points)
    local cellSize = mindist/math.sqrt(2)
    local function compare_coords(a,b)
        aa = imageToGrid(a, cellSize);
        bb = imageToGrid(b, cellSize);
        if (aa.y == bb.y) then  -- If they are around the same row
            return a.x<b.x;     -- the x coord orders them
        else                    -- if not
            return a.y>b.y;     -- the y coord orders them
        end
    end

    local data = generate_poisson(width, height, mindist, add_points)
    table.sort(data, compare_coords);
    local str = {}
    for k,v in ipairs(data) do
        table.insert(str, string.format("%f/%f", v.x, v.y))
    end
    tex.print(table.concat(str, ", "))
end