所有点都被一条线穿过

Question

我需要找到一条线上的所有点。我尝试了 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;
    }
}

Answer 1

好吧，只需实现明显简单的算法：从线的一端开始，找到它穿过起始方块的哪一侧，跳到相应的相邻方块......等等。步行直到到达终点广场。

以整数实现它的最简单方法是切换到超像素精度：只需将所有值乘以常数因子即可。当您发现没有足够的整数范围来充分乘以它时，困难的部分就开始了......我不知道您的情况是否属于这种情况。