线绕画生成背后的数学原理

是什么将一张照片转化为数千条精确放置的线条？每一个线绕画图案背后都蕴含着优雅的数学——从经典几何学到现代优化算法。让我们探索驱动数字线绕画生成的迷人技术。

核心问题

线绕画生成解决了一个有趣的数学挑战：

已知： 目标图像、圆形排列的N个钉子和黑线

目标： 找到最能再现图像的线条连接序列

这本质上是一个优化问题——在数十亿种可能性中找到最佳解决方案。

贪婪算法方法

大多数线绕画生成器，包括我们的，都使用贪婪算法。工作原理如下：

步骤1：设置

1. 在圆周上均匀放置N个钉子
2. 将目标图像转换为灰度图
3. 创建"误差缓冲区" = 反转的灰度（暗 = 高误差）
4. 从钉子0开始

步骤2：迭代循环

重复直到达到最大连接数：
    1. 从当前钉子评估所有可能的下一个钉子
    2. 对于每条候选线：
       - 计算沿线路径的"误差和"
       - 穿过较暗区域的线 = 更高分数
    3. 选择误差分数最高的钉子
    4. 画线（从误差缓冲区减去暗度）
    5. 移动到选定的钉子
    6. 记录连接

步骤3：输出

最终输出：
- 可视预览
- 序列文件：0 → 87 → 134 → 23 → ...

为什么叫"贪婪"？

该算法被称为"贪婪"是因为在每一步，它都做出局部最优选择（最佳单线）而不考虑未来后果。

这种方法：

✅ 快速（多项式时间）
✅ 产生良好结果
❌ 不保证找到绝对最优解

找到真正的最优解需要评估所有可能的序列——对于数千条连接来说在计算上是不可能的。

钉子和线条的几何学

圆形钉子排列

钉子使用基本三角函数放置：

for (let i = 0; i < numPins; i++) {
    const angle = (2 * Math.PI * i) / numPins;
    const x = centerX + radius * Math.cos(angle);
    const y = centerY + radius * Math.sin(angle);
    pins[i] = { x, y };
}

这创建了均匀的角度间距——每个钉子间隔 360° / numPins 度。

线条像素计算

要评估潜在的线条，我们需要它覆盖的所有像素。这使用Bresenham线算法或线性插值：

function getLinePixels(x0, y0, x1, y1) {
    const distance = Math.sqrt((x1-x0)² + (y1-y0)²);
    const steps = Math.floor(distance);
    const pixels = [];
    
    for (let i = 0; i <= steps; i++) {
        const t = i / steps;
        const x = Math.round(x0 + t * (x1 - x0));
        const y = Math.round(y0 + t * (y1 - y0));
        pixels.push({ x, y });
    }
    return pixels;
}

误差缓冲区机制

初始状态

误差缓冲区从反转的灰度图像开始：

原始像素 → 灰度 → 误差值
暗像素   →  50  →   205 (255-50)
亮像素   → 230  →    25 (255-230)

高误差值 = 需要更多线条的暗区域。

误差减法

当"绘制"一条线时，我们沿其路径减去暗度：

function subtractLine(pin1, pin2, weight) {
    for (const pixel of getLinePixels(pin1, pin2)) {
        errorBuffer[pixel.y][pixel.x] -= weight;
        // 限制以防止负值
        if (errorBuffer[pixel.y][pixel.x] < 0) {
            errorBuffer[pixel.y][pixel.x] = 0;
        }
    }
}

weight 参数控制每条线添加多少暗度——调整这个会影响最终密度。

线条评分

每条候选线通过沿其路径求和误差值来评分：

function scoreLineError(pin1, pin2) {
    let score = 0;
    for (const pixel of getLinePixels(pin1, pin2)) {
        score += errorBuffer[pixel.y][pixel.x];
    }
    return score;
}

穿过高误差（暗）区域的线得分更高并被选中。

优化技术

距离约束

为防止难看的短线，我们强制连接钉子之间的最小距离：

const MIN_DISTANCE = 20; // 钉子数

// 选择下一个钉子时：
if (Math.abs(candidatePin - currentPin) < MIN_DISTANCE) {
    skip(); // 太近了
}

避免最近钉子

为防止重复的来回模式，我们追踪最近使用的钉子：

const recentPins = []; // 最近20个钉子

if (recentPins.includes(candidatePin)) {
    skip(); // 避免重复
}

// 选择后：
recentPins.push(selectedPin);
if (recentPins.length > 20) {
    recentPins.shift(); // 移除最旧的
}