有没有办法可以找到一条直线和一个网格之间的所有交点呢?(交点圆圈的大小比例不一定准确,我知道)
一种暴力算法是对于 x-y
网格中的每个点都计算其与该直线的交点,但这种算法非常低效(O(m*n)
,其中 m
为 x
网格数,n
为 y
网格数)。
我正在寻找更好的算法。
(0,b)
、((h-b)/m, h)
、(w, mw+b)
、(2w, 2wm+b)
、((2h-b)/m,2h)
、(3w, 3wm+b)
等等。 - Graviton如果网格是轴对齐的:
如果网格是规则的,则每个水平线与其相交的距离相同。垂直线也是如此。在这种情况下,您可以使用dx和dy进行简单的迭代算法。
算法:
网格由墙壁组成。
墙壁具有特定的尺寸:(垂直、水平、深度)
墙壁尺寸相交形成单元格(在最终尺寸中)
线主要在它们自己的维度上与墙壁相交。
解决方案是将问题视为:如何在其自身维度中与墙壁相交的线。
解决方案是沿着线从墙壁滑动到墙壁,必要时切换维度。
沿着线滑动的过程是这样的,以便始终选择最近的墙壁作为下一个目的地。
在自己的维度中从墙壁滑动到墙壁是恒定/始终相同的。
线和墙壁的交点在不同的维度上是不同的。
这最终决定了墙壁相交的顺序。
因此,解决方案是:
第1阶段:初始化
计算Dimension.IntersectT
计算Dimension.SlideT
第2阶段:从起点开始向目标滑动,选择最近的墙壁:
Dimension.T:= Dimension.IntersectT
while ? end condition ?
选择最小的Dimension.T
更新所选的Dimension.T + = Dimension.SlideT
end
难点在于计算 Ts。
再见, Skybuck。