suwang Tech Blog

Tech Blog

0%

图形算法

发表于 更新于

#采样
米切尔最佳候选算法（Mitchell’s best-candidate algorithm）
从候选的采样点中选择出最佳采样点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function sample() {
     var bestCandidate, bestDistance = 0;
     //numCandidates为固定数量候选采样点，这个越少算法运行速度越快，越大速度慢质量高
     for (var i = 0; i < numCandidates; ++i) {
          var c = [Math.random() * width, Math.random() * height],
          d = distance(findClosest(samples, c), c);
          //最佳采样点就是距离固定点最远的那个点
          if (d > bestDistance) {
               bestDistance = d;
               bestCandidate = c;
          }
     }
     return bestCandidate;
}
function distance(a, b) {
     var dx = a[0] - b[0],
     dy = a[1] - b[1];
     return Math.sqrt(dx * dx + dy * dy);
}

泊松圆盘采样算法（Poisson-disc）
比米切尔最佳候选算法（Mitchell’s best-candidate algorithm）效果更好些，方法是利用现有采样点一点点生成新的采样点，best-candidate是在整个采样区里生成新采样点。算法执行过程是使用红色表示活跃点，黑色标识固定采样点，等所有红色采样点都变成黑色算法结束。

每一轮循环会从所有活跃点中随机取一个，以此点为圆心分别以r和2r为半径作两个同心圆，将r定为两个采样点之间最小距离。

在r和2r之间环形区随机生成一些候选点，从里面筛出满足和其它活跃点或者固定点之间距离大于r的点将其设置为活跃点，如果都小于r那么将圆心那个点设置为固定点。当所有点都为固定点时算法结束。

洗牌
对一组元素随机重排列
Fisher–Yates洗牌算法
最优洗牌算法，时间复杂度O(n)，O(1)

1
2
3
4
5
6
7
8
9
10
function shuffle(array) {
     var n = 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;
}

排序
快速排序
在当前待排序元素中取个基准，然后将比这个基准小的元素放到左侧，大的放到右侧，不断递归下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quicksort(array, left, right) {
     if (left < right - 1) {
          var pivot = left + right >> 1;
          pivot = partition(array, left, right, pivot);
          quicksort(array, left, pivot);
          quicksort(array, pivot + 1, right);
     }
}
function partition(array, left, right, pivot) {
     var pivotValue = array[pivot];
     swap(array, pivot, --right);
     for (var i = left; i < right; ++i) {
          if (array[i] < pivotValue) {
               swap(array, i, left++);
          }
     }
     swap(array, left, right);
     return left;
}

快速排序还有些优化的方法，比如三数取中（median-of-three）,取三个元素先排序，将中间数作为基准，一般是取左端，右端和中间三个数，也可随机取。另一个就是当递归到数组元素比较少的时候采用插入排序而不是继续递归。

归并排序
将两个相邻的有序表归并为一个新的有序表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function mergesort(array) {
     var n = array.length, a0 = array, a1 = new Array(n);
     for (var m = 1; m < n; m <<= 1) {
          for (var i = 0; i < n; i += m << 1) {
               var left = i,
               right = Math.min(i + m, n),
               end = Math.min(i + (m << 1), n);
               merge(a0, a1, left, right, end);
          }
          array = a0, a0 = a1, a1 = array;
     }
}
function merge(a0, a1, left, right, end) {
     for (var i0 = left, i1 = right; left < end; ++left) {
          if (i0 < right && (i1 >= end || a0[i0] <= a0[i1])) {
               a1[left] = a0[i0++];
          } else {
               a1[left] = a0[i1++];
          }
     }
}

排序算法可视化参考资料

迷宫

主要就是用到了生成树的算法，需要先了解广度优先遍历，深度优先遍历，Kruskal算法，Prim算法。
随机遍历

算法从左下角开始，每步从所有可以扩展点随机选择一个进行扩展。
深度优先遍历

从当前最长的路径的末端随机选择一个可扩展点开始扩展，如果出现回路或到达边界就回溯到最近的一个可扩展分支。这种算法生成迷路分支较少，路径也更长更曲折。
Prim算法

用于构造一棵最小生成树，其边的权重在所有可能的生成树中是最小的。在迷宫生成中，我们可以通过随机指定边的权重。Prim算法每一步都从当前最小权重的边中挑一条添加当前迷宫上，形成回路就丢弃，再选一条权重最小的边。
Wilson算法

利用擦圈随机游动（loop-erased random walks）的方法生成一个均匀的随机迷宫，就是一棵均匀支撑树（uniform spanning tree）。Wilson算法每轮随机指定一个起点，开始随机游走直到其与当前迷宫相交，将红变白，然后开始下一轮的随机游走。如果随机游走过程形成回路，就擦除回路继续随机游走。

迷宫算法可视化参考资料

算法资料

可视化资源

光影效果

数学