在直线Bresenham生成算法中,确定y的值取yi+1,还是yi的依据是

发布网友发布时间：2022-05-24 21:00

共1个回答

热心网友时间：2023-11-01 23:10

假设我们需要由 (x0, y0) 这一点,绘画一直线至右下角的另一点(x1, y1), x,y分别代表其水平(horizontal)及垂直(vertical)座标.(这是一般电脑常用之设定.)

因此x及y之值分别向下及向右增加.而两点之水平距离分别为x1 − x0及y1-y0.由此得之,该线的斜率(slope)必定介附于 - 1至0之间.而此算法之目的,就是找出在x0与x1之间,第x行相对应的第y列,从而得出一映像点(pixel),而此点必须是最接近原本的线.

对于由(x0, y0)及(x1, y1)两点所组成之直线,公式如下:

y-y0 = [(y1-y0)/(x1-x0)](x-x0)

因此,对于每一点的x,其y的值是

[(y1-y0)/(x1-x0)](x-x0)+y0

因为x及y皆为整数,但并非每一点x所对应的y皆为整数,故此没有必要去计算每一点x所对应之y值.反之由于此线之斜率介附于 - 1至0之间,故此我们只需要找出当x到达那一个数值时,会使y上升1,若x尚未到此值,则y不变.至于如何找出相关的x值,则需依靠斜率.斜率之计算方法为m = (y1 − y0) / (x1 − x0).由于此值不变,故可于运算前预先计算,减少运算次数.

要实行此算法,我们需计算每一映像点与该线之间的误差(error).于上述例子中,误差应为每一点x中,其相对的映像点之y值与该线实际之y值的差距.每当x的值增加1,误差的值就会增加m.每当误差的值超出某一限额(如0.5),线就会比较靠近下一个映像点,因此y的值便会加1.反之若误差少于 0.5,y则减1.

The procere looks like this, assuming plot(x,y) plots a point and abs returns absolute value:

Expressed in pseudo code, the naive implementation below uses comparatively expensive floating point arithmetic, but it can be easily tweaked (see optimization section) to use integer math:

function line(x0, x1, y0, y1)
int deltax := abs(x1 - x0)
int deltay := abs(y1 - y0)
real error := 0
real deltaerr := deltay / deltax // 假设 deltax != 0（非垂直线）
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if error ≥ 0.5 then
y := y + 1
error := error - 1.0

参考资料：http://zh.wikipedia.org/wiki/Bresenham%E7%9B%B4%E7%B7%9A%E6%BC%94%E7%AE%97%E6%B3%95