【译】圆形填充—Circle Packing

@JChehe 2018-08-12 09:24:26发表于 JChehe/blog

原文:Circle Packing

圆形填充是一个非常神奇的效果。蕴含数学魅力的它,看似非常复杂。在本教程中,我们将创建一个有趣的圆形填充效果。尽管它实现起来并不特别高效,但仍然很快。

老规矩,初始化 canvas。

var canvas = document.querySelector('canvas');
var context = canvas.getContext('2d');

var size = window.innerWidth;
canvas.width = size;
canvas.height = size;

context.lineWidth = 2;

现在,我将阐述一下实现流程,并因此而确定需要哪些变量。该实现流程并不是最高效的,但能完成工作。

流程如下:

  1. 创建一个圆。
  2. 判断该圆是否与其他已存在的圆发生碰撞。
  3. 若未发生碰撞,则增大半径,并再次检查是否发生碰撞。
  4. 重复上一步,直至发生碰撞。此刻得到“最大尺寸”。
  5. 创建另一个圆,并重复 N 次。

因此,需要一个 circles 数组、totalCircles、最小与最大半径和 createCircleAttempts 变量。

var circles = []; // 存放合格的圆形
var minRadius = 2; // 最小半径
var maxRadius = 100; // 最大半径
var totalCircles = 500; // 调用创建圆形函数的次数
var createCircleAttempts = 500; // 创建一个圆时,所需尝试的最大次数

现在,我们将通过代码描绘整体实现流程。创建函数 createCircledoesCircleHaveACollision 函数,然后根据要求逐步填充实现细节。其中,包括调用 createAndDrawCircle 函数 totalCircles 次。

function createAndDrawCircle() {
  
  // 从 0 开始遍历至 createCircleAttempts
  // 尝试创建一个圆

  // 创建单位圆后,将其尺寸不断增大,直至碰到另一个圆。此时达到最大值

  // 绘制圆形
}

function doesCircleHaveACollision(circle) {
  // 根据当前圆形是否与另一个圆形发生碰撞,返回 true 或 false

  // 但现在一直返回 false
  return false;
}

for( var i = 0; i < totalCircles; i++ ) {  
  createAndDrawCircle();
}

创建带有 xyradius 属性的圆形对象。

var newCircle = {
  x: Math.floor(Math.random() * size),
  y: Math.floor(Math.random() * size),
  radius: minRadius
}

并将圆形对象填充到 circles 数组中,并进行绘制。尽管实际并不需要执行这一步,但这有助于了解代码流程。

circles.push(newCircle);
context.beginPath();
context.arc(newCircle.x, newCircle.y, newCircle.radius, 0, 2*Math.PI);
context.stroke(); 

小圆圈

现在 canvas 上充满了小圆圈。接着,让圆形每次增长 1 单位大小,直至发生碰撞。当发生碰撞时,半径大小减少 1,并退出循环。

for(var radiusSize = minRadius; radiusSize < maxRadius; radiusSize++) {
  newCircle.radius = radiusSize;
  if(doesCircleHaveACollision(newCircle)){
    newCircle.radius--
    break;
  } 
}

超级乱

哇,超级乱!原因是 doesCircleHaveACollision 一直返回 false

判断圆形之间是否发生碰撞,需要涉及一些三角学。我们需要遍历所有已绘制在 canvas 上的圆形,并将当前圆形与它们进行比较。若两者半径之和大于两者圆心距离,则发生碰撞。

通过勾股定理可计算出两圆心距离(哇,高中数学派上用场!)。

译者注:在国内,初中就已经学习勾股定理了。

for(var i = 0; i < circles.length; i++) {
  var otherCircle = circles[i];
  var a = circle.radius + otherCircle.radius;
  var x = circle.x - otherCircle.x;
  var y = circle.y - otherCircle.y;

  if (a >= Math.sqrt((x*x) + (y*y))) {
    return true;
  }
}

存在重叠

还有另一个小难题。当我们创建圆时,有可能出现在已有圆形内。

这就需要在创建圆形的循环内增加碰撞检测,尽管随机生成的位置会导致不那么高效。其实,除非要创建百万以上的圆形,否则不会看到任何迟缓的现象。

如果圆形找不到安全区域,那就放弃当次尝试。

var newCircle;
var circleSafeToDraw = false;
for( var tries = 0; tries < createCircleAttempts; tries++) {
  newCircle = {
    x: Math.floor(Math.random() * size),
    y: Math.floor(Math.random() * size),
    radius: minRadius
  }
    
  if(doesCircleHaveACollision(newCircle)) {
    continue;
  } else {
    circleSafeToDraw = true;
    break;
  }
}

if(!circleSafeToDraw) {
  return;
}

填满整个 canvas

哇,现在拥有了漂亮圆形的效果。尽管整个 canvas 被圆圈填满,但还剩一个小步骤要做,那就是增加圆形与边界的碰撞检测。我们将该工作拆分为两个判断语句,一个是检查上下边界,另一个是检查左右边界。

if ( circle.x + circle.radius >= size ||
  circle.x - circle.radius <= 0 ) {
  return true;
}
    
if (circle.y + circle.radius >= size ||
  circle.y-circle.radius <= 0 ) {
  return true;
}

最终效果——圆形填充

我们终于实现了!尽管这不是最完美的代码,但它是一个说明如何通过相对简单的数学来推理、思考并逐步完成较为复杂工作的好案例。