【译】圆形填充—Circle Packing

[JChehe]

原文：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; // 创建一个圆时，所需尝试的最大次数

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

function createAndDrawCircle() {

  // 从 0 开始遍历至 createCircleAttempts
  // 尝试创建一个圆

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

  // 绘制圆形
}

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

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

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

创建带有 x、y 和 radius 属性的圆形对象。

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 被圆圈填满，但还剩一个小步骤要做，那就是增加圆形与边界的碰撞检测。我们将该工作拆分为两个判断语句，一个是检查上下边界，另一个是检查左右边界。

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

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