我如何为凸包算法设置动画中间步骤？ [英] How can I animate intermediate steps for a convex hull algorithm?

问题描述

我正在尝试制作某种动画，以便用户可以了解或查看为点集找到凸包所采取的步骤。例如，假设我在下面的代码中使用了Graham Scan的代码，有什么方法可以对添加和删除行添加动画？即使有很多要点，处理它们也需要时间，然后几乎立即绘制它们，我不确定如何帮助用户体验正在发生的事情。

< pre $ {$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ ]。
var stack2 = [];

stack1.push（points [0]）
stack1.push（points [1]）$ ​​b
$ b（i = 2; 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]）$ ​​b $ b stack2.push（points [points.length-2]）

（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（）;

$ b函数reDraw（points，stack1，stack2）{
ctx.clearRect（0，0，w，h）;
document.getElementById（canvasimg）。style.display =none;
for（j = 0; j ctx.beginPath（）;
ctx.fillStyle = x;
ctx.fillRect（points [j] .x-1，points [j] .y-1,3,3）;
ctx.closePath（）; （k = 1; 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（）;
}
（l = 1; 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（）;



函数RTT（a，b，c）{
return Math.sign（（bx-ax）*（cy-ay） - （通过-AY）*（CX-AX））;
}

解决方案

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

最简单的方法是使用生成器函数创建可以停止执行算法的位置，并允许动画循环显示和控制执行速度。它不会干扰算法的功能。请参阅生成器函数声明MDN

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

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

当算法完成时，生成器将返回undefined作为值，并且您知道它已完成。

A快速示例

我已将您的 grahamScan 函数转换为生成器函数。然后用 vis = grahamScan（points）创建一个生成器，然后我每4帧渲染一次，这样就是〜15fps。我不确定你想要视觉休息的地方，而且我还添加了一些额外的渲染，因为发现的线条闪烁开启和关闭（内部while循环外部线条未被绘制）。

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

主动画循环在底部，I添加了一些代码来创建随机点并将其渲染为背景画布。唯一的限制是如果非常高，船体的顶点数量会减慢。这些点是预先渲染的，所以不会影响帧速率，你可以有成千上万到上百万（尽管预渲染时间会花费一点时间，我测试了500,000点，渲染背景需要大约4秒，但可视化运行以全帧速率。

use strictvar 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 ; //呈现之间有多少帧（正常更新每1/60秒呈现，所以1的val是每秒60次）var frameC ount = 0; var restartIn = 120; // frameCount befor restartvar 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

I'm trying to make some kind of animation so that a user can understand or see the steps taken in finding the convex hull for a point set. For example, let's say I'm using this code below for Graham Scan, what are some ways to animate the line additions and removals? Even for a lot of points, it takes time to process and then plots them all almost immediately, and I'm unsure how to help the user experience what's going on...

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

解决方案

Animating algorithms using generator functions.

The easiest way is to use a generator function to create place where you can stop execution of the algorithm and allow a animation loop to display and control the speed of execution. It does not interfere with the algorithm's function. See Generator function declaration MDN

Normal generator functions are used to generate data, but in this case we are not interested in the data but rather the visualization process built into the algorithm.

To animate just create a standard animation loop. Create a background canvas to hold any graphics that you don't want to draw each time you update / step the algorithm. Set a frame rate for the visualization, then every frame clear the canvas, draw the background, call for the next value from the generator function (which will render the next part of the algorithm) then wait for the next frame.

When the algorithm is complete the generator will return undefined as the value and you know it is complete.

A quick example

I have converted your grahamScan function into a generator function. Then create a generator with vis = grahamScan(points) then I render the steps every 4 frames so that is ~15fps. I was not sure where you wanted the visual breaks and I also added some extra rendering as the found lines were flashing on and off ( inside the inner while loops the outer lines were not being drawn).

I generate the points array randomly and restart the animation about 2 seconds after it is done.

The main animation loop is at the bottom, and I added some code to create random points and render them to a background canvas. The only limitation is the hull vert count if very high will slow it down. The points are pre rendered so will not affect the frame rate, you can have 100 of thousands to millions ( though pre render time will take a little time. I tested 500,000 points and it took about 4 seconds to render the background but the visualization ran at full frame rate.

"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);
 

这篇关于我如何为凸包算法设置动画中间步骤？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！