查找由线段相交的所有瓷砖

Question

我需要找到所有与线段相交的瓷砖，但是Bresenham算法不符合我的要求。我需要找到所有单元格。我不需要知道交点，只需要知道是否相交。谢谢帮助。

我考虑找到线的方向向量，并逐步按瓷砖大小进行分割以找到单元格。但我不知道如何选择正确的步长。我认为1像素步长不好。

- Denis Ermolin

---

你说的“不符合我的要求”是什么意思？它在哪些方面不符合要求？ - Ivaylo Strandjev

它只会找到符合 delta 参数的单元格，而不是所有单元格。请查看维基百科的示例图片。 - Denis Ermolin

Answer 1

这里是Amanatides和Woo的文章，标题为“用于光线追踪的快速体素遍历算法”，适用于2D和3D情况。 实际应用。

- MBo

Answer 2

你可以使用以下其中一个线性方程式：http://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml 或 http://mathworld.wolfram.com/Line.html

假设你在坐标系中有两个点，你可以推导出 y=mx+n 方程式，并将其与你的瓷砖匹配，查看它们是否相交，同时在你的坐标系中沿着任何方向移动 x，从你的瓷砖最小的 x 到最大的 x。如果你的坐标系是屏幕，那么 1 像素就足够了。

这是我现在能够提供的最接近的提示，但我不知道你所面临的问题的确切性质。

- Ferenc Deak

---

什么是“与你的瓷砖匹配”？我需要一个针对这个操作的算法。 - Denis Ermolin

你的瓦片是什么几何形状？ - Ferenc Deak

Answer 3

修改 Bresenham 算法以跟踪所需内容是很容易的。以下是算法的相关片段：

plot(x,y);
error = error + deltaerr;
if (error >= 0.5)
{
    y = y + ystep;
    error = error - 1.0;
}

为了跟踪所有的单元格，我们需要另一个变量。请注意，我还没有严格检查过这个。

plot(x,y);
olderror = error.
error = error + deltaerr;
if (error >= 0.5)
{
    y = y + ystep;
    error = error - 1.0;
    extra = error+olderror;

    if (extra > 0)
    {
      plot (x,y); /* not plot (x-1,y); */
    }
    else if (extra < 0)
    {
      plot (x+1,y-1); /* not plot (x+1,y); */
    }
    else
    {
      // the line goes right through the cell corner
      // either do nothing, or do both plot (x-1,y) and plot (x+1,y)
      // depending on your definition of intersection           
    }
}

- n. m.

---

我稍后会尝试，然后会汇报结果。 - Denis Ermolin

plot (x-1,y) 和 plot (x+1,y) 中有错误，坐标不正确。应该是 plot (x,y) 和 plot (x+1,y-1)。我已经更新了代码。 - n. m.

此外，如果处理陡峭的线条，则 plot(x,y) 变为 if (steep) plot(y,x); else plot(x,y);，其他 plot 调用也会类似地改变（就像维基百科文章中的第二个列表中一样）。 - n. m.