图形算法

2018-07-11  本文已影响38人  sudhengshi

采样

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

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)

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;
}

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

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）,取三个元素先排序，将中间数作为基准，一般是取左端，右端和中间三个数，也可随机取。另一个就是当递归到数组元素比较少的时候采用插入排序而不是继续递归。

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

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++];
          }
     }
}

排序算法可视化参考资料

迷宫算法可视化参考资料

算法资料

可视化资源

光影效果

数学

上一篇 下一篇

猜你喜欢

热点阅读