以快速的方式找到直线和网格的交点

Question

有没有办法可以找到一条直线和一个网格之间的所有交点呢？（交点圆圈的大小比例不一定准确，我知道）

一种暴力算法是对于 x-y 网格中的每个点都计算其与该直线的交点，但这种算法非常低效（O(m*n)，其中 m 为 x 网格数，n 为 y 网格数）。

我正在寻找更好的算法。

- Graviton

---

网格应该是规则的吗？ - Ignacio Vazquez-Abrams

@Ignacio，是的，这个网格是规则的。 - Graviton

Answer 1

听起来你需要一个 数字微分分析器 或者 Bresenham直线算法。Bresenham是在位图上绘制线条的相同算法；在这种情况下，着色像素等同于检查该方格中是否发生碰撞。

- celion

---

我认为这应该是被接受的答案。使用像Bresenham算法这样的算法将给出要检查的网格点，然后从那里可以更轻松地计算出各个交点 - 水平和垂直分量都是已知的。 - Bryan Rayner

Answer 2

我不确定我是否真正理解这个问题。这是你正在寻找的吗？

- dtb

---

我想要红线和网格线之间的每个交点。因此，这些点是(0,b)、((h-b)/m, h)、(w, mw+b)、(2w, 2wm+b)、((2h-b)/m,2h)、(3w, 3wm+b)等等。 - Graviton

@dtb，没有遗漏。但我想要一个高效的算法。 - Graviton

这对我来说看起来像是每个交叉点一个计算。我想不出比这更有效率的方法了。 - dtb

@dtb，如果是这样的话，那将非常低效。考虑一下你有一个100100的网格，那么你就需要进行100100次操作。 - Graviton

@dtb，啊，好的，你是对的。但是没有其他方法进一步优化这件事吗？ - Graviton

Answer 3

如果网格是轴对齐的：

1. 找出线性方程
2. 直接使用网格线的x或y作为固定变量计算交点

如果网格是规则的，则每个水平线与其相交的距离相同。垂直线也是如此。在这种情况下，您可以使用dx和dy进行简单的迭代算法。

- jackrabbit

Answer 4

算法：

网格由墙壁组成。

墙壁具有特定的尺寸：（垂直、水平、深度）

墙壁尺寸相交形成单元格（在最终尺寸中）

线主要在它们自己的维度上与墙壁相交。

解决方案是将问题视为：如何在其自身维度中与墙壁相交的线。

解决方案是沿着线从墙壁滑动到墙壁，必要时切换维度。

沿着线滑动的过程是这样的，以便始终选择最近的墙壁作为下一个目的地。

在自己的维度中从墙壁滑动到墙壁是恒定/始终相同的。

线和墙壁的交点在不同的维度上是不同的。

这最终决定了墙壁相交的顺序。

因此，解决方案是：

第1阶段：初始化

计算Dimension.IntersectT

计算Dimension.SlideT

第2阶段：从起点开始向目标滑动，选择最近的墙壁：

Dimension.T：= Dimension.IntersectT

while ? end condition ?

选择最小的Dimension.T

更新所选的Dimension.T + = Dimension.SlideT

end

难点在于计算 Ts。

再见， Skybuck。

- oOo