一条线穿过的所有点 [英] All points crossed by a line

问题描述

我需要找到一条线上的所有点.我尝试了 Bresenham 的算法，但在以下情况下不起作用:

I need to find all points that are on a line. I tried Bresenham's algorithm but it doesn't work on the following case:

 (0, 0)
.-----------+-----------+-----------.
|...........|           |           |
|...........|           |           |
|.....XXXX..|           |           |
|........XXXX           |           |
|...........XXXXX       |           |
+-----------+---XXXX----+-----------+
|           |......XXXXX|...........|
|           |..........XXXX.........|
|           |...........|.XXXXX.....|
|           |...........|...........|
|           |...........|...........|
`-----------+-----------+-----------´
                              (2, 1)

X 是实际的行，. 是 Bresenham 算法返回的内容，注意该行与 (1, 0) 交叉，但不是标记.
如何有效地找到一条线穿过的所有像素?我不需要这个抗锯齿，所以我认为吴的算法是一种矫枉过正.线端点位于像素的中间.

X is the actual line, . is what Bresenham's algorithm returns, notice the line crosses (1, 0) but it is not marked.
How can I find all the pixels a line goes through efficiently? I don't need this anti-aliased so I think Wu's algorithm is an overkill. The line endpoints are in middle of the pixels.

引用我的算法是:

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;
    }
}

推荐答案

好吧，就实现一个显而易见的简单算法:从线的一端开始，找到它穿过起始方块的哪一侧，跳转到对应的相邻方块... 等等.步行直到到达终点广场.

Well, just implement the obvious straightforward algorithm: start from one end of the line, find which side of the starting square it crosses, jump to the corresponding adjacent square... and so on. Walk until you reach the finish square.

以整数实现它的最简单方法是切换到超像素精度:只需将所有内容乘以一个常数因子.当您发现没有足够的整数范围来充分乘以它时，困难的部分就开始了……我不知道您的情况是否如此.

The simplest way to implement it in integers would be to switch to superpixel precision: just multiply everything by a constant factor. The difficult part begins when you discover that you don't have enough integer range to multiply it sufficiently... I don't know whether this is the case in your case.

这篇关于一条线穿过的所有点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！