我正在尝试制作某种动画,以便用户可以理解或查看为点集找到凸包的步骤.例如,假设我在下面使用此代码进行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);