该算法的功能明显不同于其他两个——它充分利用现有采样点逐步生成新的采样点,而不是在整个采样区域随机生成新的采样点。这使其进展具有准生物学外观,如在培养皿中分裂的细胞。注意,也没有采样点彼此太接近;这是定义由算法实施的泊松盘分布的最小距离约束。 这就是它的工作原理: 红点表示“活跃”采样点。在每次迭代中,从所有活跃采样点的集合中随机选择一个。然后,在围绕所选采样点的环内随机生成一些数量的候选采样点(用空心黑点表示)。环从半径r延伸到2r,其中r是样本之间的最小允许距离。 来自现有采样点的距离r内的候选采样点被拒绝;这个“禁止区”以灰色显示,用黑线连接将被拒绝的候选采样点和附近的现有采样点。网格加速每个候选采样点的距离检查。网格尺寸r /√2确保每个单元可以包含至多一个采样点,并且仅需要检查固定数量的相邻单元。 如果候选采样点是可以接受的,它被添加作为一个新的采样点,然后随机选择一个新的活跃采样点。如果没有一个候选采样点是可以接受的,所选择的活跃采样点被标记为无效(颜色从红色变为黑色)。当没有采样点保持活跃时,该算法终止。 面积用着色表示的Voronoi图显示了泊松盘采样算法相对于最佳候选算法的改进,没有深蓝色或浅黄色细胞: 泊松盘采样下的《星夜》最大地保留了细节和引入了最少的噪音。它让人想起美丽的罗马马赛克: 现在,你已经看到了一些例子,让我们简要地思考一下为什么要把算法可视化。 ▼娱乐 我发现可视化的算法有无穷的魅力,甚至令人着迷。特别是在涉及随机性时。虽然这看似是一个牵强的理由,但不要低估了快乐的价值!此外,尽管这些可视化甚至在不理解基础算法的情况下也可以参与,但是掌握算法的重要性可以给出更深的理解。 ▼教学 你发现代码或动画更有帮助吗?伪代码( 不能编译的代码的委婉语)怎么样? 虽然形式描述在明确的文档中有它的位置,可视化可以使直观的理解更容易。 ▼调试 你有没有实现基于形式描述的算法? 可能很难! 能够看到你的代码在做什么可以提高生产力。 可视化不能取代测试需求,但测试主要用于检测故障而不是解释它。即使输出看起来正确,可视化还可以在实现过程中发现意外的表现(参看Bret Victor的《可学习的编程》和为了优秀的相关工作的《发明原理》)。 ▼学习 即使你只是想为自己学习,可视化会是一个很好的方式来得到深刻的理解。教学是最有效的学习方法之一,实现可视化就像教自己。我发现看到它,而不是熟记小而容易忘记细节的代码,更容易直观地记住一个算法。 洗牌 洗牌是随机重新排列一组元素的过程。例如,你可以在打牌之前洗牌。一个好的洗牌算法是无偏的,其中每个排序都有相同的可能性。 Fisher-Yates shuffle是一个最佳的洗牌算法。 它不仅是无偏的,而且在线性时间内运行,使用恒定的空间,并且易于实现。 ▼代码如下—— function shuffle(array) { varn = array.length, t, i; while (n) { i= Math.random() * n-- | 0; // 0 ≤ i < n t= array[n]; array[n] = array[i]; array[i] = t; } return array; } 以上是代码,下面是一个可视化的解释: (责任编辑:本港台直播) |