HTML5 Canvas：分割/计算线

Question

我已经在键盘上敲击了大约一周了，但我无法找到解决问题的正确方法。我认为它比 HTML Canvas 更多地与数学相关......希望有人能指出我正确的方向。

我有一个 HTML Canvas，用户可以使用鼠标和非常简单的 moveTo() 和 lineTo() 函数来绘制线条。当用户完成后，我将坐标保存在 MongoDB 中。当用户稍后再次点击该页面时，我想显示他的绘图，但我不想立即加载包含所有存储坐标的整个图片，我想以图块形式返回它（通过缓存每个图块来获得更好的性能）。

这些图块为 200x200 像素（固定偏移量和宽度，从 0 -> 200-> 400 ->...开始）。 现在，当用户从 50,50(x/y) 到 250,250(x/y) 绘制一条线时，每个边界框（图块）中只有一个点。我需要分割线并计算每个边界框（图块）中每条线的起点和终点。否则我无法部分绘制图像（以图块形式）。当一条线穿过多个边界框（图块）时，情况会变得更加复杂。例如：100,100(x/y)->100,100(x/y)-> -1234，-300（x/y）。 这些线可以从任意点 (+/-) 向任意方向延伸任意距离。

当然，我查看了布雷森纳姆的旧算法，它部分有效，但对我来说，它似乎是最长且最耗资源的解决方案。

所以，我来这里的原因是我希望有人能够用（也许）另一种方法来计算每个边界框的线的起点/终点，为我指明正确的方向。

JavaScript 或 PHP 中的代码示例非常受欢迎。

感谢您的阅读和思考：）

Answer 1

tl;dr：使用平面，数学解释如下。底部有一个画布示例。

鉴于所有单元格都是轴对齐的边界框，您可以使用平面方程来找到直线与边缘的交点。

平面

您可以将您的盒子视为一组四个几何平面。每个平面都有一个法线或长度为 1 的向量，指示哪个方向是平面的“前”。构成细胞侧面的平面的法线为：

   top = {x:  0, y: -1};
bottom = {x:  0, y:  1};
  left = {x: -1, y:  0};
 right = {x:  1, y:  0};

给定平面上的一点，该平面具有方程：

distance = (normal.x * point.x) + (normal.y * point.y)

您可以使用此方程来计算平面的距离。在这种情况下，您知道框的左上角（假设 x 为 10，y 为 100）位于顶平面上，因此您可以执行以下操作：

distance = (0 * 10) + (-1 * 100)
distance = -100

根据平面检查点

一旦获得距离，您可以重用该方程来检查任何点相对于平面的位置。对于随机点 p（其中 x 为 -50，y 为 90），您可以执行以下操作：

result = (normal.x * p.x) + (normal.y * p.y) - distance
result = (0 * -50) + (-1 * 90) - (-100)
result = 0 + (-90) - (-100)
result = -90 + 100
result = 10

有两种可能的结果：

if (result >= 0) {
    // point is in front of the plane, or coplanar.
    // zero means it is coplanar, but we don't need to distinguish.
} else {
    // point is behind the plane
}

根据平面检查直线

您可以从 < code>a 到 b 这样：

result1 = (normal.x * a.x) + (normal.y * a.y) - distance
result2 = (normal.x * b.x) + (normal.y * b.y) - distance

有四种可能的结果：

if (result1 >= 0 && result2 >= 0) {
  // the line is completely in front of the plane
} else if (result1 < 0 && result2 < 0) {
  // the line is completely behind the plane
} else if (result1 >= 0 && result2 < 0) {
  // a is in front, but b is behind, line is entering the plane
} else if (result1 < 0 && result2 >= 0) {
  // a is behind, but b is in front, line is exiting the plane
}

当直线与平面相交时，要找到交点。它有助于思考矢量术语中的线：

a + t * (b - a)

如果 < code>t == 0 表示您位于该行的开头，而 t == 1 表示该行的结尾。在这种情况下，您可以计算交点为：

time = result1 / (result1 - result2)

交点计算为：

hit.x = a.x + (b.x - a.x) * time
hit.y = a.y + (b.y - a.y) * time

根据框检查一条线

通过该数学运算，您可以计算出与框的交线。您只需要针对每个平面测试直线的端点，并找到时间的最小值和最大值。

因为你的盒子是一个凸多边形，所以在这个检查中有一个早期的结果：如果线是完全位于盒子中任何一个平面的前面，它不能与你的盒子相交。您可以跳过检查其余飞机。

在 JavaScript 中，您的结果可能如下所示：

/**
 * Find the points where a line intersects a box.
 *
 * @param a Start point for the line.
 * @param b End point for the line.
 * @param tl Top left of the box.
 * @param br Bottom right of the box.
 * @return Object {nearTime, farTime, nearHit, farHit}, or false.
 */
function intersectLineBox(a, b, tl, br) {
  var nearestTime = -Infinity;
  var furthestTime = Infinity;
  var planes = [
    {nx:  0, ny: -1, dist: -tl.y},  // top
    {nx:  0, ny:  1, dist:  br.y},  // bottom
    {nx: -1, ny:  0, dist: -tl.x},  // left
    {nx:  1, ny:  0, dist:  br.x}   // right
  ];
  for (var i = 0; i < 4; ++i) {
    var plane = planes[i];
    var nearDist = (plane.nx * a.x + plane.ny * a.y) - plane.dist;
    var farDist = (plane.nx * b.x + plane.ny * b.y) - plane.dist;
    if (nearDist >= 0 && farDist >= 0) {
      // both are in front of the plane, line doesn't hit box
      return false;
    } else if (nearDist < 0 && farDist < 0) {
      // both are behind the plane
      continue;
    } else {
      var time = nearDist / (nearDist - farDist);
      if (nearDist >= farDist) {
        // entering the plane
        if (time > nearestTime) {
          nearestTime = time;
        }
      } else {
        // exiting the plane
        if (time < furthestTime) {
          furthestTime = time;
        }
      }
    }
  }
  if (furthestTime < nearestTime) {
    return false;
  }
  return {
    nearTime: nearestTime,
    farTime: furthestTime,
    nearHit: {
      x: a.x + (b.x - a.x) * nearestTime,
      y: a.y + (b.y - a.y) * nearestTime
    },
    farHit: {
      x: a.x + (b.x - a.x) * furthestTime,
      y: a.y + (b.y - a.y) * furthestTime
    }
  };
}

如果这仍然太慢，您还可以执行 broadphase 通过将世界划分为大矩形，并将线分配给这些矩形来进行剔除。如果您的线路和单元格不在同一矩形中，它们不会发生冲突。

我上传了一个画布示例。

Answer 2

看起来您必须弄清楚每条线与每个图块的边界相交的点。

查看此问题的答案：是否有一个简单的方法检测线段相交的方法？

答案不提供代码，但将方程转换为 PHP 或 Javascript 应该不会太难...

---

编辑：

为什么，确切地说，你想分割线吗？我知道您不想一次加载所有行，因为这可能需要一段时间。但是，只加载并绘制前几行，然后再绘制其余部分有什么问题吗？

我认为这比必须切割每行以适合特定的图块要简单得多。平铺是优化位图加载的好方法；我认为它不太适合基于矢量的绘图。

您还可以考虑发送 Ajax 请求，并在请求到来时开始绘制整个内容；这不会干扰页面的加载。