我必须找到与线段相交的所有图块,但 Bresenham 的线算法不符合我的要求。我需要找到所有单元格。我不需要知道交点,只需要知道交点的事实。感谢帮助。
我想找到线的方向向量,并通过平铺大小的划分逐步找到单元格。但我不知道如何选择正确的步长。我认为 1 px 步骤很糟糕。
我必须找到与线段相交的所有图块,但 Bresenham 的线算法不符合我的要求。我需要找到所有单元格。我不需要知道交点,只需要知道交点的事实。感谢帮助。
我想找到线的方向向量,并通过平铺大小的划分逐步找到单元格。但我不知道如何选择正确的步长。我认为 1 px 步骤很糟糕。
您可以使用以下网址中的众多线方程之一:http ://www.cut-the-knot.org/Curriculum/Calculus/StraightLine.shtml或http://mathworld.wolfram.com/Line.html
假设您的坐标系中的线穿过两个点,您可以推导出y=mx+n
方程并与您的瓷砖相匹配,看看它们是否相交,同时以您的坐标系为单位从瓷砖的最小 x 向您喜欢的任何方向移动 x直到最大。如果你的坐标系是屏幕,1个像素就足够了。
这是我可以提示正确知道的关闭,而无需更多地了解您所面临问题的确切性质。
修改 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
}
}