首页 / JAVASCRIPT / javascript – 如何为凸包算法设置中间步骤的动画？

javascript – 如何为凸包算法设置中间步骤的动画？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了javascript – 如何为凸包算法设置中间步骤的动画？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9063字，纯文字阅读大概需要13分钟。

内容图文

我正在尝试制作某种动画,以便用户可以理解或查看为点集找到凸包的步骤.例如,假设我在下面使用此代码进行Graham Scan,有哪些方法可以为线条添加和删除设置动画？即使有很多要点,也需要时间来处理,然后几乎立即绘制它们,我不确定如何帮助用户体验正在发生的事情……

function GrahamScan(points) {
  points.sort(function(a, b){return a.x - b.x})

  var stack1 = [];
  var stack2 = [];

  stack1.push(points[0])
  stack1.push(points[1])

  for (i=2; i < points.length; i++) {
     len = stack1.length > 1;
     turn = RTT(stack1[stack1.length-2], stack1[stack1.length-1], points[i]) === 1;
     ctx.beginPath();
     ctx.moveTo(stack1[stack1.length-2].x,stack1[stack1.length-2].y);
     ctx.lineTo(stack1[stack1.length-1].x,stack1[stack1.length-1].y);
     ctx.stroke();
     while (len && !turn) {
           stack1.pop();
           reDraw(points, stack1, stack2);
           len = stack1.length > 1;
           if (!len) {
              break
           }
           turn = RTT(stack1[stack1.length-2], stack1[stack1.length-1], points[i]) === 1;
     }
     stack1.push(points[i]);

  }
  ctx.beginPath();
  ctx.moveTo(stack1[stack1.length-2].x,stack1[stack1.length-2].y);
  ctx.lineTo(stack1[stack1.length-1].x,stack1[stack1.length-1].y);
  ctx.stroke();

  stack2 = [];
  stack2.push(points[points.length-1])
  stack2.push(points[points.length-2])

  for (i=2; i < points.length; i++) {
     len = stack2.length > 1;
     turn = RTT(stack2[stack2.length-2], stack2[stack2.length-1], points[points.length-i-1]) === 1;
     ctx.beginPath();
     ctx.moveTo(stack2[stack2.length-2].x,stack2[stack2.length-2].y);
     ctx.lineTo(stack2[stack2.length-1].x,stack2[stack2.length-1].y);
     ctx.stroke();
     while (len && !turn) {
           stack2.pop();
           reDraw(points, stack1, stack2);
           len = stack2.length > 1;
           if (!len) {
              break
           }
           turn = RTT(stack2[stack2.length-2], stack2[stack2.length-1], points[points.length-i-1]) === 1;
     }
     stack2.push(points[points.length-i-1]);

  }
  ctx.beginPath();
  ctx.moveTo(stack2[stack2.length-2].x,stack2[stack2.length-2].y);
  ctx.lineTo(stack2[stack2.length-1].x,stack2[stack2.length-1].y);
  ctx.stroke();

}
   function reDraw(points,stack1,stack2) {
      ctx.clearRect(0, 0, w, h);
      document.getElementById("canvasimg").style.display = "none";
      for (j = 0; j < points.length; j++) {
         ctx.beginPath();
         ctx.fillStyle = x;
         ctx.fillRect(points[j].x-1, points[j].y-1, 3, 3);
         ctx.closePath();
      }
      for (k = 1; k < stack1.length; k++) {
         ctx.beginPath();
         ctx.moveTo(stack1[k-1].x-1,stack1[k-1].y-1);
         ctx.lineTo(stack1[k].x-1,stack1[k].y-1);
         ctx.stroke();
      }
      for (l = 1; l < stack2.length; l++) {
         ctx.beginPath();
         ctx.moveTo(stack2[l-1].x-1,stack2[l-1].y-1);
         ctx.lineTo(stack2[l].x-1,stack2[l].y-1);
         ctx.stroke();
      }
   }

   function RTT(a, b, c) {
      return Math.sign((b.x - a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x));
   }

解决方法:

使用生成器函数的动画算法.

最简单的方法是使用生成器函数创建可以停止执行算法的位置,并允许动画循环显示和控制执行速度.它不会干扰算法的功能.见Generator function declaration MDN

正常的生成器函数用于生成数据,但在这种情况下,我们对数据不感兴趣,而是对算法中内置的可视化过程感兴趣.

动画只是创建一个标准的动画循环.创建背景画布以保存每次更新/步进算法时不想绘制的任何图形.设置可视化的帧速率,然后每个帧清除画布,绘制背景,从生成器函数调用下一个值(将呈现算法的下一部分)然后等待下一帧.

算法完成后,生成器将返回undefined作为值,并且您知道它已完成.

一个简单的例子

我已将您的grahamScan函数转换为生成函数.然后使用vis = grahamScan(points)创建一个生成器,然后每4帧渲染一次这样的步骤,即?15fps.我不确定你想要视觉中断的位置,并且我还添加了一些额外的渲染,因为找到的线条是闪烁的(在内部while循环内部,外部线条没有被绘制).

我随机生成点数组,并在完成后约2秒重新启动动画.

主动画循环位于底部,我添加了一些代码来创建随机点并将它们渲染到背景画布.唯一的限制是船体垂直计数,如果非常高将减慢它.这些点是预先渲染的,因此不会影响帧速率,你可以拥有数十万到数百万(虽然预渲染时间需要一点时间.我测试了500,000点,渲染背景花了大约4秒但是可视化运行了以全帧速率.

"use strict"
var canvas = document.createElement("canvas");
canvas.width = innerWidth - 20;
canvas.height = innerHeight - 20;
var ctx = canvas.getContext("2d");
document.body.appendChild(canvas)
var w = canvas.width;
var h = canvas.height;
var points;
var background = document.createElement("canvas");
background.width = w;
background.height = h;
background.ctx = background.getContext("2d");
const frameRate = 4; // How many frames between renders (normal update renders every 1/60 second so val of 1 is 60 times a second)
var frameCount = 0;
var restartIn = 120; // frameCount befor restart
var restartCount = 120;
var restart = true;
var globalTime;
var vis;


function *grahamScan(points) {
    points.sort(function (a, b) {
        return a.x - b.x
    })

    var stack1 = [];
    var stack2 = [];

    stack1.push(points[0])
    stack1.push(points[1])

    for (var i = 2; i < points.length; i++) {
        var len = stack1.length > 1;
        var turn = RTT(stack1[stack1.length - 2], stack1[stack1.length - 1], points[i]) === 1;
        reDraw(points, stack1, stack2);
        ctx.strokeStyle = "red";
        ctx.beginPath();
        ctx.moveTo(stack1[stack1.length - 2].x, stack1[stack1.length - 2].y);
        ctx.lineTo(stack1[stack1.length - 1].x, stack1[stack1.length - 1].y);
        ctx.stroke();
        yield null; // not interested in what is returned just want to code to stop here
        while (len && !turn) {
            stack1.pop();
            reDraw(points, stack1, stack2);
            yield null; // not interested in what is returned just want to code to stop here
            len = stack1.length > 1;
            if (!len) {
                break
            }
            turn = RTT(stack1[stack1.length - 2], stack1[stack1.length - 1], points[i]) === 1;
        }
        stack1.push(points[i]);

    }
    reDraw(points, stack1, stack2);
    ctx.strokeStyle = "red";
    ctx.beginPath();
    ctx.moveTo(stack1[stack1.length - 2].x, stack1[stack1.length - 2].y);
    ctx.lineTo(stack1[stack1.length - 1].x, stack1[stack1.length - 1].y);
    ctx.stroke();
    yield null; // not interested in what is returned just want to code to stop here

    stack2 = [];
    stack2.push(points[points.length - 1])
    stack2.push(points[points.length - 2])

    for (i = 2; i < points.length; i++) {
        len = stack2.length > 1;
        turn = RTT(stack2[stack2.length - 2], stack2[stack2.length - 1], points[points.length - i - 1]) === 1;
        reDraw(points, stack1, stack2);
        ctx.strokeStyle = "red";
        ctx.beginPath();
        ctx.moveTo(stack2[stack2.length - 2].x, stack2[stack2.length - 2].y);
        ctx.lineTo(stack2[stack2.length - 1].x, stack2[stack2.length - 1].y);
        ctx.stroke();
        yield null; // not interested in what is returned just want to code to stop here
        while (len && !turn) {
            stack2.pop();
            reDraw(points, stack1, stack2);
            yield null; // not interested in what is returned just want to code to stop here
            len = stack2.length > 1;
            if (!len) {
                break
            }
            turn = RTT(stack2[stack2.length - 2], stack2[stack2.length - 1], points[points.length - i - 1]) === 1;
        }
        stack2.push(points[points.length - i - 1]);

    }
    ctx.beginPath();
    ctx.moveTo(stack2[stack2.length - 2].x, stack2[stack2.length - 2].y);
    ctx.lineTo(stack2[stack2.length - 1].x, stack2[stack2.length - 1].y);
    ctx.stroke();
    reDraw(points, stack1, stack2);
    yield "allDone";

}
function reDraw(points, stack1, stack2) {
    ctx.strokeStyle = "blue";
    ctx.lineWidth = 3;
    for (var k = 1; k < stack1.length; k++) {
        ctx.beginPath();
        ctx.moveTo(stack1[k - 1].x , stack1[k - 1].y );
        ctx.lineTo(stack1[k].x , stack1[k].y );
        ctx.stroke();
    }
    ctx.strokeStyle = "green";
    ctx.lineWidth = 2;
    for (var l = 1; l < stack2.length; l++) {
        ctx.beginPath();
        ctx.moveTo(stack2[l - 1].x , stack2[l - 1].y );
        ctx.lineTo(stack2[l].x , stack2[l].y );
        ctx.stroke();
    }
    ctx.lineWidth = 1;
}

function RTT(a, b, c) {
    return Math.sign((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}

function randomBell(min,max){  // over kill but smooth distrabution
    var r = 0;
    for(var i = 0; i < 4; i++){
        r += Math.random()+Math.random()+Math.random()+Math.random()+Math.random()+Math.random();
    }
    r /= (4*6);
    return (max-min)*r + min;
}
function createRandomPoints(count){
    var p = []; // points;
    for(var i = 0; i < count; i ++){
        p.push({x : randomBell(10,canvas.width-20), y : randomBell(10,canvas.height-20)});
    }
    return p;
}
function renderPoints(points,ctx){
    ctx.clearRect(0,0,ctx.canvas.width,ctx.canvas.height);
    ctx.strokeStyle = "red";
    ctx.lineWidth = "1";
    ctx.lineJoin = "round";
    points.forEach(function(p){
        ctx.strokeRect(p.x-1.5,p.y-1.5,3,3);
    });
}

function rescalePointsToFit(points,w,h){
    points.sort(function(a,b){return a.x - b.x});
    var minx = points[0].x;
    var maxx = points[points.length-1].x;
    points.sort(function(a,b){return a.y - b.y});
    var miny = points[0].y;
    var maxy = points[points.length-1].y;
    var scale = Math.min((w-20)/(maxx-minx),(h-20)/(maxy-miny));
    var midx = (maxx-minx) * 0.5 + minx;
    var midy = (maxy-miny) * 0.5 + miny;
    points.forEach(function(p){
        p.x = (p.x - midx) * scale + midx;
        p.y = (p.y - midy) * scale + midy;
    });
    return points;
}
// main update function
function update(timer){
    globalTime = timer;
    frameCount += 1;
    if(restart){
        restartCount += 1;
        if(restartCount >= restartIn){  // restart visulisation
            points = rescalePointsToFit(createRandomPoints(Math.floor(randomBell(10,500))),w-30,h-30);
            renderPoints(points,background.ctx);            
            vis = grahamScan(points); // create new generator 
            restart = false;
            frameCount = 0;
            
        }
    }
    if(!restart && (frameCount % frameRate === 0)){
        ctx.setTransform(1,0,0,1,0,0); // reset transform
        ctx.globalAlpha = 1;           // reset alpha
        ctx.clearRect(0,0,w,h);
        ctx.drawImage(background,0,0); // draw backround containing points;
        if(vis.next().value !== null){  // step the algorithum and check if done
            restart = true;
            restartCount = 0;
        }
    }
    requestAnimationFrame(update);

}
requestAnimationFrame(update);

内容总结

以上是互联网集市为您收集整理的javascript – 如何为凸包算法设置中间步骤的动画？全部内容，希望文章能够帮你解决javascript – 如何为凸包算法设置中间步骤的动画？所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/698294.html

来源：【匿名】

【上一篇】javascript倒计时器暂停恢复【下一篇】javascript 怎么调用php方法

更多 ►

【javascript – 如何为凸包算法设置中间步骤的动画？】教程文章相关的互联网学习教程文章

原创JavaScript Jquery特效之----多重特效折叠菜单(附带详细注释和算法思路)【图】

<!DOCTYPE html> <html><head><meta charset="utf-8"><title>折叠菜单</title><script type="text/javascript" src="js/jquery-2.1.0.js"></script><script type="text/javascript" src="js/foldMenu.js" ></script><style type="text/css">* {padding: 0;margin: 0;}#FoldingMenuBar {margin: 200px;;}li {list-style: none;}.left {float: left;}.TotalMenu {float: left;}.TotalMenu li{height: auto;overflow:auto;}.menuBody{...

JavaScript Base64算法的实现【代码】

js 版base 64 算法 base64.jsvar keyStr = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="; //将Ansi编码的字符串进行Base64编码function encode64(input) { var output = ""; var chr1, chr2, chr3 = ""; var enc1, enc2, enc3, enc4 = ""; var i = 0; do { chr1 = input.charCodeAt(i++); chr2 = input.charCodeAt(i++); chr3 = input.charCodeAt(i++); enc1 = chr1 >> 2; enc2 = ((chr1 & 3) << 4) | (...

javascript数组去重算法-----3【代码】

1<!DOCTYPE html> 2<html lang="en"> 3<head> 4<meta charset="UTF-8"> 5<title>javascript数组去重算法-----3</title> 6</head> 7<body> 8<script> 9var arr = [1,1,2,2,3,2,2,3,3,1,1,4,4,5,6]; 10function unique(array){ 11var n = []; 12var a = {}; 13for (var i =0; i < array.length; i++) { 14if (!a[array[i]]) { 15 a[array[i]] =true; 16 n.push(array[i]) 17 }; 18 ...

JavaScript算法 ,Python算法,Go算法,java算法,系列之【归并排序】篇【代码】【图】

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： 650) this.width=650;" src="/upload/getfiles/default/2022/11/8/20221108060054389.jpg" title="1513609480-59142359dda6f_articlex.png" />归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法...

JavaScript版几种常见排序算法【代码】

今天发现一篇文章讲“JavaScript版几种常见排序算法”，看着不错，推荐一下原文：http://www.w3cfuns.com/blog-5456021-5404137.html算法描述：* 冒泡排序：最简单，也最慢，貌似长度小于7最优* 插入排序：比冒泡快，比快速排序和希尔排序慢，较小数据有优势* 快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合* 希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快* 系统方法：在forfox...

数据结构算法-JavaScript常用排序法（常用排序方法的总结）【代码】【图】

JavaScript常见排序以下两个函数是排序中会用到的通用函数，就不一一写了function checkArray(array) {if (!array || array.length <= 2) return } function swap(array, left, right) {let rightValue = array[right]array[right] = array[left]array[left] = rightValue }View Code冒泡排序冒泡排序的原理如下，从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一...

关于JavaScript算法的几个小练习--DonyZ

各位小伙伴们，以下的内容来自于我在freecodecamp上做的练习，这是一个很好的学习平台，在此分享给大家，下面的题目答案在文章的最后(答案都是我自己写的，虽然都写出来了，可并不一定是最好的写法，所以希望能和大家一起交流，嘿嘿)，并且会持续更新关于JavaScript算法的文章，希望小伙伴们能多多交流，互相学习1.翻转字符串先把字符串转化成数组，再借助数组的reverse方法翻转数组顺序，最后把数组转化成字符串。你的结果必须得是...

重读《学习JavaScript数据结构与算法-第三版》- 第6章链表（一）【代码】【图】

定场诗伤情最是晚凉天，憔悴厮人不堪言；邀酒摧肠三杯醉.寻香惊梦五更寒。钗头凤斜卿有泪，荼蘼花了我无缘；小楼寂寞新雨月.也难如钩也难圆。前言本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。链表链表，为什么要有这种数据结构呢？当然，事出必有因！数组-最常用、最方便的数据结构，But，当我们从数组的起点或中间插入或移动项的成本很高，因为我们需要移...

不会全排列算法(Javascript实现)，我教你呀！【图】

今天我很郁闷，在实验室凑合睡了一晚，准备白天大干一场，结果一整天就只做出了一道算法题。看来还是经验不足呀，同志仍需努力呀。算法题目要求是这样的：Return the number of total permutations of the provided string that don‘t have repeated consecutive letters. Assume that all characters in the provided string are each unique.For example, aab should return 2 because it has 6 total permutations (aab, aab, ...

动态规划之最大公共子串算法代码实现(使用JavaScript实现)【代码】【图】

问题描述最大公共子串问题:要求在两个字符串之间找出最大的公共字符串.并且输出其所在位置.通过递推可以分析得出递推公式(博主是跟着学的,没分析) : c[i,j] = c[i-1,j-1] + 1以下图示列出了过程.文中的代码使用的是动态规划求解.其中可能有点难以理解的是下标问题: arr[i] == 0 arr[j] == 0的情况是需要进行列出来的,并且都是为0.在进行字符对比的时候,按照下标从1开始进行对比.而不是从0开始进行对比.图析代码实现 let lis...

快速排序算法的 JavaScript 实现【代码】

快速排序是一种在大多数情况下比冒泡排序效率更高（详情参考有关算法复杂度的文章）的算法。注意：许多编程语言内置的排序 API 底层实现便是基于快速排序。ES5 与 ES6 语法在实现该算法时区别不大，以下仅提供 ES5 版本。function quickSort(arr) {var len = arr.length;if (len <= 1) {return arr.slice(0); // 注意用 slice 可防范 arr[0] 为 undefined }var left = [], right = [], mid = [];mid.push(arr[0]);for (var i = 1; ...

javascript算法--随机选取10个数，并降序排列【代码】

1function rd(n,m){2var c = m - n + 1;3return Math.floor(Math.random()*c+n);4 }5var n = 10;6var m = 100;7var i = 10;8var j = 0;9var arr = []; 10while (i>0){ 11var a = rd(n,m); 12var b = 10 - i; 13var k; 14for(k = 0;k < b;k++){ 15if (a == arr[k]) { 16break; 17 } 18 }; 19if (k == b) { 20 arr[j++] = a; 21 i--; 22 } 23 ...

常见的排序算法总结（JavaScript）【代码】【图】

引言　　排序算法是数据结构和算法之中的基本功，无论是在笔试还是面试，还是实际运用中都有着很基础的地位。这不正直七月，每年校招的备战期，所以想把常见的排序算法记录下来。在本篇文章中的排序算法使用 JavaScript 实现。一、冒泡排序　　冒泡排序是排序算法中最简单的一个算法，其优点是易理解，易实现。在一些对性能要求不高且数据量不大的需求中，冒泡排序是一个很好的选择。　　原理：假设排序顺序为增序，数组长度为 N...

javascript算法挑战【代码】

1、翻转字符串算法挑战: 先把字符串转化成数组，再借助数组的reverse方法翻转数组顺序，最后把数组转化成字符串。你的结果必须得是一个字符串function reverseString(str) {arr = str.split(‘‘);str = arr.reverse().join(‘‘);return str; } reverseString("hello");2、阶乘算法挑战: 如果用字母n来代表一个整数，阶乘代表着所有小于或等于n的整数的乘积。阶乘通常简写成 n!例如: 5! = 1 * 2 * 3 * 4 * 5 = 120function factor...

一道javascript算法面试题

实现一个数组内所有元素的和。代码如下:function add(runningTotal, currentValue) {return runningTotal + currentValue; } var nums = [1,2,3,4,5,6,7,8,9,10]; var sum = nums.reduce(add); console.log(sum); // 显示55请写出reduce的实现功能。答案如下：Array.prototype.reduce=function(callback){ var total=0; this.forEach(function(e){ total=callback(total,parseInt(e));}); return total; };原文：http:/...

首页 / JAVASCRIPT / javascript – 如何为凸包算法设置中间步骤的动画？

javascript – 如何为凸包算法设置中间步骤的动画？

内容导读

内容图文

内容总结

内容备注

内容手机端

【javascript – 如何为凸包算法设置中间步骤的动画？】教程文章相关的互联网学习教程文章

JAVASCRIPT - 相关标签

算法 - 相关标签

设置 - 相关标签

JAVASCRIPT - 技术教程分类

JAVASCRIPT - 最新教程

JAVASCRIPT - 最热教程