所有的点用一条线相交
本文关键字:一条 | 更新日期: 2023-09-27 17:54:34
我需要找到一条线上的所有点。我尝试了Bresenham的算法,但它不适用于以下情况:
(0, 0)
.-----------+-----------+-----------.
|...........| | |
|...........| | |
|.....XXXX..| | |
|........XXXX | |
|...........XXXXX | |
+-----------+---XXXX----+-----------+
| |......XXXXX|...........|
| |..........XXXX.........|
| |...........|.XXXXX.....|
| |...........|...........|
| |...........|...........|
`-----------+-----------+-----------´
(2, 1)
X
是实际的线,.
是Bresenham算法返回的,注意这条线穿过(1, 0)
,但没有标记。
我怎样才能有效地找到一条直线经过的所有像素点呢?我不需要这种反混叠,所以我认为吴的算法有点小题大做。线端点位于像素的中间。
引用我的算法是:
int dx = System.Math.Abs(x0 - x1);
int dy = System.Math.Abs(y0 - y1);
int sx = x0 < x1 ? 1 : -1;
int sy = y0 < y1 ? 1 : -1;
int err = dx - dy;
int lx = x0;
int ly = y0;
for(int i = 0; true; i++)
{
Mark(x0, y0);
if(x0 == x1 && y0 == y1)
break;
int e2 = err * 2;
if(e2 > -dy)
{
err -= dy;
x0 += sx;
}
if(e2 < dx)
{
err += dx;
y0 += sy;
}
}
那么,只需实现显而易见的简单算法:从线的一端开始,找到它穿过起始正方形的哪一边,跳到相应的相邻正方形……等等......一直走到终点广场。
在整数中实现它的最简单方法是切换到超像素精度:只需将所有内容乘以常数因子。当你发现你没有足够的整数范围来充分乘以它时,困难就开始了……我不知道你的情况是否如此。