首页 > 代码库 > 掩码内判断线段与哪些掩码相交
掩码内判断线段与哪些掩码相交
改进的Bresenham算法。
采用Bresenham算法进行直线计算,并且改进该算法中的乘法运算,使得整个直线段的计算都是通过加法运算进行,可以大大降低CPU的消耗,实验结果表明该算法对比DDA算法在频繁运算时能有者非常显著的效果。以下是改进过的Bresenham算法。
算法实现步骤:
过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点,然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列的所求象素。
如图a 所示,设直线方程为yi+1=yi+k(xi+1-xi)+k。假设列坐标象素已经确定为xi,其行坐标为yi。那么下一个象素的列坐标为xi+1,而行坐标要么为yi,要么递增1为yi+1。是否增1取决于误差项d的值。误差项d的初值d0=0,x坐标每增加1,d的值相应递增直线的斜率值k,即d=d+k。一旦 d≥1,就把它减去1,这样保证d在0、1之间。当d≥0.5时,直线与垂线x=xi+1交点最接近于当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当d<0.5时,更接近于右方象素(xi+1,yi)。为方便计算,令e=d-0.5,e的初值为-0.5,增量为k。当e≥0时,取当前象素(xi,yi)的右上方象素(xi+1,yi+1);而当e<0时,取(xi,yi)右方象素(xi+1,yi)。
然后再通过斜率>0.5还是<0.5进行以x方向还是y方向递加
掩码内判断线段与哪些掩码相交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。