太惊艳了，原来算法可视化后可以这么艺术（多gif图)

前言

最近读到一篇老外的文章《Visualizing Algorithms》，表示被里面各种算法炫酷的展示亮瞎了眼，一时冲动决定要将这篇文章翻译成中文，但是由于原文较长而且很文艺（我会告诉你们是我的英语太渣了么-_-），我打算以解读的形式来展示原文而并非翻译，如果感兴趣可以直接看原版。最后我会整合其他一些算法可视化的素材。好了，闲话不多说，Let’s begin~

“

我们需要向你道歉，由于本文图片太多，而且都是gif图，为了帮您节省流量，我们只放出部分内容。请你在Wifi环境下，点击左下角“阅读原文”到36大数据官网阅读。你也可以百度“36大数据”，查看更多我们的文章。

采样

首先我们来欣赏一下梵高同学的名画《星空》的一部分

关于光是怎样在人的视网膜上成像涉及到物理和生物的一些知识，这里我们不作讨论。但是其中有很重要的一个过程就是人眼把连续的光信号变成了离散的信号，并将其反馈给大脑。这个过程就称为采样。

采样在计算机图形学中扮演着非常重要的角色。即使是简单的调整图像大小也要用到采样。因此如何进行采样就显得十分重要，一方面要保证采样点要均匀分布，另一方面要避免采样点重复或产生规律（否则会产生混叠）。人的视网膜在采样上做的非常出色，看下面这张视网膜在显微镜下的图，图中的较大的视锥细胞探测颜色，较小的视杆细胞对弱光较为敏感。

这些细胞稠密且均匀的分布在视网膜上，而且它们之间的相对位置是无规律的。我们称之为泊松圆盘分布，因为任意细胞间的最小距离总是一定的。

但是构造一个泊松圆盘分布并不容易，我们先来看看米切尔最佳候选算法(Mitchell’s best-candidate algorithm)，它是泊松圆盘分布的一个近似，方便起见，我们就称之为best-candidate算法吧~

从图上来看best-candidate算法形成的采样点还算令人满意，至少随机性是不错。不过缺点也很明显，有的区域采样点非常多（过采样），而有的区域则较稀疏（欠采样）。当然即使这样也是相当不错的，因为这个算法易于实现。

我们来看看这个算法的原理

best-candidate算法，顾名思义，是从一堆候选采样点中选取一个最佳采样点。首先，生成固定数量（上图中为10）的候选采样点，用灰色表示，每一个候选采样点是在采样区域随机生成的。然后寻找最佳候选采样点，用红色表示。什么是最佳候选采样点呢？就是距离已固定的采样点（黑色表示）最远的那个点。这么说大家可能还是不太明白，其实就是把已固定的采样点整体看成一个集合，候选采样点与这个集合中每一个元素都有一个距离，我们把最小的那个距离定义为该候选采样点到已固定采样点的距离。

从图上来说就是对每一个灰点（候选采样点），寻找离它最近的黑点（已固定的采样点），在它们之间划一条线，线的长度就是它们的距离。红点（最佳候选采样点）就是在当前所有灰点中这个距离最大的那个点。当这一轮结束这后，把红点标为黑点（把最佳候选采样点作为已固定的采样点），然后进行下一轮的选取，如此循环下去。

点击下方“阅读原文”查看全文……

↓↓↓