4.1 初次尝试——点和直线（下）.pdf

初次尝试——点和直线（下） 提纲 1 中点的Bresenham算法回顾 2 更直观的想法 3 改进的Bresenham算法 1 中点Bresenham算法回顾 基本原理 ： 假定0≤k≤1 ，x是最大位移方向 候选点 p （x +1 ，y +1 ） u i i Q M(x +1 ，y +0.5) i i 当前点 p （x +1 ，y ） d i i p （x ，y ） i i i 1 中点Bresenham算法回顾 基本原理 ： 通过中点不直线的位置关系引入误差项d ，判断误差项的符号来选择候选点 p （x +1 ，y +1 ） p （x +1 ，y +1 ） u i i u i i pi+1取pu Q M(x +1 ，y +0.5) Q M(x +1 ，y +0.5) i i i i pi+1取pu p （x ，y ） p （x +1 ，y ） p （x ，y ） p （x +1 ，y ） i i i d i i i i i d i i M在Q的下方 M在Q的上方 d=F(M)（0 d=F(M)≥0 取Pu 取P d 2 更直观的想法 基本原理 ： 假定0≤k≤1 ，x是最大位移方向 pu d）0.5 d=0.5 d（0.5 pi pd d d 每次x =x +1 i+1 i d d）0.5 y =y +1 d i+1 i d=0.5 yi+1=yi d（0.5 yi+1=yi 引入简洁的误差项d 2 更直观的想法 寻找d的变换规律 k d每次 k d 增加k k d k d k d 一旦向上走了一步 则让d减去1 d的初值 为0 2 更直观的想法 k k k d d 如果向上走了一步 k d d丌减去1 d k d 后果会如何？ 3 改进的Bresenham算法 完备的算法 d的初值： d =0 0 k k d d d的变换及如何取点： k d=d+k k 浮点运算 d d x =x +1 k i+1 i d）0.5 y =y +1 此时d=d-1 i+1 i d≤0.5 yi+1 =yi 让人烦恼 的比较 3 改进的Bresenham算法 改进一 d的初值： e的初值： d =0 令e=d-0.5 e =-0.5 0 0 仍然有 浮点数！ d的变换及如何取点： e的变换及如何取点： d=d+k e=e+k x =x +1 x =x +1 i+1 i i+1 i d）0.5 y =y +1 此时d=d-1 e）0 y =y +1 此时e=e-1 i+1 i i+1 i d≤0.5 yi+1 =yi e≤0 yi+1 =yi 3 改进的Bresenham算法 改进二 e的初值： e的初值： e =-0.5 e=e ×2△x e =-△x 0 0 消除了 浮点数！ e的变换及如何取点： e的变换及如何取点： e=e+k e=e+2△y x =x +1 x =x +1 i+1 i i+1 i e）0 y =y +1 此时e=e-1 e）0 y =y +1 此时e=e-2△x i+1 i i+1 i e≤0 yi+1 =yi e≤0 yi+1 =yi 3 改进的Bresenham算法 在0≤k≤1情况下改进的B