HTML5 Canvas:拆分/计算线

Question

我现在已经在键盘上敲了大约一个星期了,我无法为我的问题找到合适的解决方案.我认为它比HTML Canvas更加数学相关...希望有人可以指出我正确的方向.

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

瓷砖是200x200像素(固定偏移和宽度,从0 - > 200-> 400 - > ...开始).现在,当用户从50,50(x/y)到250,250(x/y)绘制一条线时,每个边界框(平铺)中只有一个点.我需要分割线条并计算每个边界框(平铺)中每条线的起点和终点.否则我无法部分绘制图像(在图块中).当一条线穿过多个边界框(瓦片)时,它会变得更加复杂.例如:100,100(x/y) - > -1234,-300(x/y).这些线可以从任何点(+/-)到任何距离的ANY方向.

当然,我看了一下Bresenham的旧算法并且它有效 - 部分地,但它似乎是对我来说最长且最耗费资源的解决方案.

所以,我在这里的原因是我希望有人可以指出我正确的方向(可能)另一种计算每个边界框我的线的起点/终点的方法.

代码示例在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
}

检查飞机上的一条线

您可以从检查线的两个端点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)

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

如果这仍然太慢,你也可以通过将世界划分为大的行,并为这些行分配行来进行广义剔除.如果您的线和单元格不在同一个矩形中,它们不会发生碰撞.

我上传了一个画布示例.