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

标签 javascript animation canvas geometry convex-hull

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

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

要制作动画，只需创建一个标准动画循环。创建一个背景 Canvas 来保存每次更新/步进算法时不想绘制的任何图形。设置可视化的帧速率，然后每一帧清除 Canvas ，绘制背景，从生成器函数调用下一个值(这将渲染算法的下一部分)，然后等待下一帧。

当算法完成时，生成器将返回未定义的值，您就知道它已完成。

一个简单的例子

我已将您的 grahamScan 函数转换为生成器函数。然后使用 vis = grahamScan(points) 创建一个生成器，然后每 4 帧渲染一次步骤，从而达到约 15fps。我不确定您想要在哪里进行视觉中断，并且我还添加了一些额外的渲染，因为找到的线条不断闪烁(在内部 while 循环内，未绘制外部线条)。

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

主要动画循环位于底部，我添加了一些代码来创建随机点并将它们渲染到背景 Canvas 上。唯一的限制是船体垂直计数如果非常高会减慢速度。这些点是预先渲染的，因此不会影响帧速率，您可以有 100 个数千到数百万个(尽管预渲染时间需要一点时间。我测试了 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 - 如何为凸包算法的中间步骤设置动画？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40734485/

上一篇：javascript - 根据 Ajax GET 请求将复选框设置为选中

下一篇：javascript - 为什么更改 Canvas 大小会重置其参数？

相关文章：

javascript - 为什么 onclick 事件不影响 CSS3 animation-duration 属性？

javascript - 需要知道如何根据我点击的按钮来选择变量(Javascript)

ios - 在 UIScrollView 中滚动时动画停止

css - 旋转svg动画的起点

jQuery:减少重绘

javascript - 按字母过滤数组

javascript - Amcharts - 当图表滚动条滚动时可排序的 div 移动

node.js - 在 pkg-config 搜索路径中找不到包 cairo。 Node j.s安装 Canvas 问题

javascript - 当用户使用 Javascript 在屏幕上拖动鼠标创建多个圆圈时如何删除特定圆圈

javascript - 对象 :removed Event Not Fired - Fabric JS

©2024 IT工具网  联系我们