用于绘制4连线的算法 [英] Algorithm for drawing a 4-connected line
问题描述
感谢您的帮助任何人都可以提供。
在以下是一种类似Bresenham的算法，可以绘制4条连线。代码是用Python编写的，但即使不知道语言，我也可以很容易理解。
$ C> DEF线（X0，Y0，X1，Y1，颜色）：DX = ABS（X1 - X0）＃距离在X
行进DY = ABS（Y1 - Y0）＃距离如果x0
， x1：
ix = 1＃x将在每一步增加
else：
ix = -1＃x将在每一步减少
如果y0 < y1：
iy = 1＃y会在每一步增加
else：
iy = -1＃y在每一步会减少
e = 0＃当前错误
在范围内（dx + dy）：
draw_pixel（x0，y0，color）
e1 = e + dy
e2 = e - dx
如果abs（e1）< ABS（E2）：
＃错误会较小上移动X
X0 + = IX $ B $是= E1
，否则：
＃错误会较小上移动Y
y0 + = iy
e = e2
这个想法是画一条线您应该用与理论线的DX / DY相匹配的比率来增加X和Y.为此，我从错误变量 e 初始化为0（我们在线）开始，并在每一步检查错误如果我只增加X或如果我只增加Y（Bresenham检查是选择只更改X还是X和Y两者），那么这个数字就会更低。
这个检查会添加 1 / dy 或 1 / dx ，但将所有增量乘以 dx * dy 允许仅使用整数值，这既提高了速度又提高了准确性，并且还避免了对 dx == 0 或 dy == 0 从而简化逻辑。
当然，因为我们正在寻找比例误差，所以使用比例增量不会影响结果。
无论线段是什么，两种可能性因为增量总会对错误产生不同的符号效应......所以我的任意选择是为X步增加错误并为Y步递减错误。
ix 和 iy 变量是该行所需的实际方向（+1或-1）取决于初始坐标是低于还是高于最终坐标。 在连接4条线中绘制的像素数显然 dx + dy ，所以我只是做了很多次循环来画线，而不是检查是否到达终点。请注意，此算法绘制除最后一个像素之外的所有像素;如果你还想要最后一个像素，那么应该在循环结束后添加额外的 draw_pixel 调用。
上述实施方式的示例结果可以在下面的图中可见
I'm looking for an algorithm (coded in Java would be nice, but anything clear enough to translate to Java is fine) to draw a 4-connected line. It seems that Bresenham's algorithm is the most widely used, but all the understandable implementations I've found are 8-connected. OpenCV's cvline function apparently has a 4-connected version, but the source code is, to me, as a mediocre and nearly C-illiterate programmer, impenetrable. Various other searches have turned up nothing.
Thanks for any help anyone can provide.
The following is a Bresenham-like algorithm that draws 4-connected lines. The code is in Python but I suppose can be understood easily even if you don't know the language.
def line(x0, y0, x1, y1, color):
dx = abs(x1 - x0) # distance to travel in X
dy = abs(y1 - y0) # distance to travel in Y
if x0 < x1:
ix = 1 # x will increase at each step
else:
ix = -1 # x will decrease at each step
if y0 < y1:
iy = 1 # y will increase at each step
else:
iy = -1 # y will decrease at each step
e = 0 # Current error
for i in range(dx + dy):
draw_pixel(x0, y0, color)
e1 = e + dy
e2 = e - dx
if abs(e1) < abs(e2):
# Error will be smaller moving on X
x0 += ix
e = e1
else:
# Error will be smaller moving on Y
y0 += iy
e = e2
The idea is that to draw a line you should increment X and Y with a ratio that matches DX/DY of the theoretic line. To do this I start with an error variable e initialized to 0 (we're on the line) and at each step I check if the error is lower if I only increment X or if I only increment Y (Bresenham check is to choose between changing only X or both X and Y).
The naive version for doing this check would be adding 1/dy or 1/dx, but multiplying all increments by dx*dy allows using only integer values and that improves both speed and accuracy and also avoids the need of special cases for dx==0 or dy==0 thus simplifying the logic.
Of course since we're looking for a proportion error, using a scaled increment doesn't affect the result.
Whatever is the line quadrant the two possibilities for the increment will always have a different sign effect on the error... so my arbitrary choice was to increment the error for an X step and decrement the error for an Y step.
The ix and iy variables are the real directions needed for the line (either +1 or -1) depending on whether the initial coordinates are lower or higher than the final coordinates.
The number of pixels to draw in a 4-connected line is obviously dx+dy, so I just do a loop for that many times to draw the line instead of checking if I got to the end point. Note that this algorithm draws all pixels except the last one; if you want also that final pixel then an extra draw_pixel call should be added after the end of the loop.
An example result of the above implementation can be seen in the following picture
这篇关于用于绘制4连线的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
