泊松分布Poisson-Disc采样点的生成

2018.12/D3.js

泊松分布采样生成的点尽量紧密堆积,并且各点之间的距离均不小于指定的最小距离,从而可以产生更自然的采样图案。下面使用Robert Bridson提出的一种高效算法,时间复杂度为O(n):

  1. 规定采样点之间的最小距离为r。

  2. 在画布尺寸范围内随机生成一个活跃采样点,在这个采样点周围的环形区域中再随机生成k个候选采样点,这个环形区域以该活跃采样点为圆心,半径从r延伸到2r。

  3. 在这k个随机候选采样点中,剔除掉与已选定的采样点距离小于r的点,剩下的作为新的活跃采样点。

  4. 如果这k个采样点都被剔除了,没有剩下任何可用的点,则将此环形区域圆心处的所选活跃采样点标记为非活跃,不再用于生成候选项。

  5. 当所有采样点均为非活跃状态时,算法迭代结束。

  6. 在对候选采样点剔除筛选时,使用了对角线长度为r的单元网格来加速距离检查。每个单元网格最多只能包含一个采样点,只需检查候选采样点周边固定数量的相邻单元网格即可。

const width = document.querySelector('svg#d3').parentNode.clientWidth
const height = Math.round(width * 0.4)
const radius = Math.round(width / 50)

const sample = poissonDiscSampler(width, height, radius)

const svg = d3.select('svg#d3')
.attr('width', width)
.attr('height', height)
.attr('viewBox', `0 0 ${width} ${height}`)
.attr('fill', '#83887c')

const timer = d3.timer(function() {
const s = sample()
if (!s) return timer.stop()
svg.append("circle")
.attr("cx", s[0])
.attr("cy", s[1])
.attr("r", 0)
.transition()
.attr("r", 2)
})

function poissonDiscSampler(width, height, radius) {
const k = 30,
cellSize = radius * Math.SQRT1_2,
gridWidthLength = Math.ceil(width / cellSize),
gridHeightLength = Math.ceil(height / cellSize),
grid = new Array(gridWidthLength * gridHeightLength),
queue = []
let queueLength = 0,
sampleLength = 0

return function() {
if (!sampleLength) return sample(Math.random() * width, Math.random() * height)

while (queueLength) {
const i = Math.random() * queueLength | 0,
s = queue[i]

for (let j = 0; j < k; ++j) {
const a = 2 * Math.PI * Math.random(),
r = radius * (Math.random() + 1),
x = s[0] + r * Math.cos(a),
y = s[1] + r * Math.sin(a)

if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) return sample(x, y)
}

queue[i] = queue[--queueLength]
queue.length = queueLength
}
}

function far(x, y) {
let i = x / cellSize | 0,
j = y / cellSize | 0
const i0 = Math.max(i - 2, 0),
j0 = Math.max(j - 2, 0),
i1 = Math.min(i + 3, gridWidthLength),
j1 = Math.min(j + 3, gridHeightLength)

for (j = j0; j < j1; ++j) {
for (i = i0; i < i1; ++i) {
const s = grid[j * gridWidthLength + i]
if (s) {
const dx = s[0] - x,
dy = s[1] - y
if (dx * dx + dy * dy < radius * radius) return false
}
}
}

return true
}

function sample(x, y) {
const s = [x, y]
queue.push(s)
grid[gridWidthLength * (y / cellSize | 0) + (x / cellSize | 0)] = s
++sampleLength
++queueLength
return s
}
}

参考:https://bl.ocks.org/mbostock/19168c663618b7f07158