BYR Achieve · 镜像论坛

背景：在把WindML接口封装为Xwindow接口形式的过程中，发现WindML无法实现虚线的亦或方式绘图操作(3.0版本；其他版本未知)，但实线的亦或可以实现。故考虑使用隔断的短实线段如“-- -- -- -- --”来替代实现虚线的亦或。这就需要一个高效且准确的画线算法。在此实验使用bresenham算法，最终运行结果十分理想，360°无死角绘制且因为仅使用整数的加减运算避免了繁复的浮点运算，效率相当高。 -------------------------------------------------------- 关于bresenham算法，在此简要介绍如下（推荐参考dut_wenc的文章Bresenham画线算法）：考虑从起点到终点画线是有方向的，故划分坐标系360°=45°x8个区域，先考虑第一区域(0,45°]，其他区域以此类推。在第一区域(0<k<=1)，先画起点(x1,y1)，再画紧邻的下一点，取右点(x1++,y1)或者右上点(x1++,y1++)。以此类推。可以发现，x值一直是加1，而y值要么不加，要么加1。故我们只考虑下一点的y取值。至于下一点取右点还是右上点，就需要使用判决公式来判断。 --------------------------------------------------------- 设线段方程式：a*x+b*y+c=0 得到关键量斜率k=-a/b=dy/dx, dy=y2-y1, dx=x2-x1,代入起点坐标(x1,y1)得a*x1+b*y1+c=0 则下一点的y坐标是代入x1+1得到yN={-c-a(x1+1) }/b; 又下一点可能取的两个值的中点y坐标是yT={ (y1)+(y1+1) }/2=y1+0.5。故判决公式：yN<yT时，即下一点在中点之下，则取右点y1; yN>yT时，即下一点在中点之上，则取右上点y1++; (在此考虑yN=yT的情况：即k=1/2时，右点和右上点交替取得) 代入dy、dx、y1值得：△1=yN-yT=-a/b-0.5=dy/dx-0.5 为了避免浮点运算，在此左右同乘2*dx得到新的△1=2*dy-dx 取右点(x1++,y1)时候：△1<0；取右上点(x1++,y1++)时候：△1>0。 ---------------------------------------------------------- 以上讨论了第二点的取值，类推可得第三点的取值，当第三点取右点时，△2=4*dy-dx，可得D△=△2-△1=2*dy; 当第三点取右上点时，△2=4*dy-3*dx，可得D△=△2-△1=2*dy-2*dx ----------------------------------------------------------- 由此可知第一点的判决公式△1=2*dy-dx，以及后一点与前一点的判决差值D△=2*dy（后一点取右点）或者2*dy-2*dx（后一点取右上点），可以知道第二点、第三点......任一点的判决公式△n（不停递加）。 ------------------------------------------------------------ 以上仅写出了第一区域(0,45°]的算法。至于其他7个区域，考虑如下：对于第2区域(45,90)，交换x和y即可仿照第1区域得到。对于第3区域(90,135°]，交换x和y即可仿照第8区域得到。对于第4区域(135,180)，交换起点和终点掉头即可仿照第8区域得到。对于第5区域(180,225]，交换起点和终点掉头即可仿照第1区域得到。对于第6区域(225,270)，交换起点和终点掉头即可仿照第2区域得到。对于第7区域(270,315]，交换起点和终点掉头即可仿照第3区域得到。而对于第8区域(315,360)，我们在此考虑如下： yN={-c-a(x1+1) }/b; yT=y1-0.5; △1=yN-yT=2*dy+dx; 第二点取右点(x1++,y1)时候：△1>0；第二点取右下点(x1++,y1--)时候：△1<0。当第三点取右点时，△2=4*dy+dx，可得D△=△2-△1=2*dy; 当第三点取右下点时，△2=4*dy+3*dx，可得D△=△2-△1=2*dy+2*dx 又对于0°线考虑如下：y不变，x++。对于90°线：x不变，y++。对于180°线：交换起点和终点掉头即可仿照0°线得到。对于270°线：交换起点和终点掉头即可仿照90°线得到。 ---------------------------------------------------------------------------- 至此，360°无死角全部分析完毕，code如下（包含8个区域）： void Bresenhamline(GC gc,int x1,int y1,int x2,int y2) { int dx = 0,dy = 0,p = 0; int x3 = 0,y3 = 0; int flag = 0; int tempx = 0,tempy = 0; int width0,width1; width0 = 2;/*虚线中的每个空格长度*/ width1 = 2;/*虚线中的每个线段长度*/ dx = (x2-x1); dy = (y2-y1); flag = 1; if( ((dx>=dy)&&(dy>0)) || ((dx<=dy)&&(dy<0)) )/*0:45 180:225*/ { if((dx<=dy)&&(dy<0) ) { tempx = x1; x1 = x2; x2 = tempx; tempy = y1; y1 = y2; y2 = tempy; } dx = (x2-x1); dy = (y2-y1); x3 = x1; y3 = y1; p = 2*dy-dx; while(x1<x2) { x1++; if(p>=0) /*斜率大于0.5 取右上点，等于0.5则在右上-右-右上-右之间切换*/ { y1++; p=p+2*dy-2*dx; } else if(p<0)/* 取右点*/ { p=p+2*dy; } if( ((x1-x3)>width1)&&flag) { uglLine(gc,x3,y3,x1,y1); x3=x1; y3=y1; flag=0; } else if( ((x1-x3)>width0)&&!flag) { x3=x1; y3=y1; flag=1; } } } else if( ((dy>dx)&&(dx>0) ) || ((dy<dx)&&(dx<0)) )/*45:90 225:270*/ { if( (dy<dx)&&(dx<0) ) { tempx = x1; x1 = x2; x2 = tempx; tempy = y1; y1 = y2; y2 = tempy; } dy = (y2-y1); dx = (x2-x1); y3 = y1; x3 = x1; p = 2*dx-dy; while(y1<y2) { y1++; if(p>=0) { x1++; p=p+2*dx-2*dy; } else if(p<0) { p=p+2*dx; } if( ((y1-y3)>width1)&&flag) { uglLine(gc,x3,y3,x1,y1); y3=y1; x3=x1; flag=0; } else if( ((y1-y3)>width0)&&!flag) { y3=y1; x3=x1; flag=1; } } } else if( ( (dx>0)&&(dy<0)&&(dx>=abs(dy)) ) || ( (dx<0)&&(dy>0)&&(abs(dx)>=dy) ) )/*315:360 135:180*/ { if( (dx<0)&&(dy>0)&&(abs(dx)>=dy) ) { tempx = x1; x1 = x2; x2 = tempx; tempy = y1; y1 = y2; y2 = tempy; } dx = (x2-x1); dy = (y2-y1); x3 = x1; y3 = y1; p = 2*dy+dx; while(x1<x2) { x1++; if(p>=0) /* 取右点*/ { p=p+2*dy; } else if(p<0)/*取右下点*/ { y1--; p=p+2*dy+2*dx; } if( ((x1-x3)>width1)&&flag) { uglLine(gc,x3,y3,x1,y1); x3=x1; y3=y1; flag=0; } else if( ((x1-x3)>width0)&&!flag) { x3=x1; y3=y1; flag=1; } } } else if( ((dx<0)&&(dy>0)&&(abs(dx)<dy)) || ((dx>0)&&(dy<0)&&(dx<abs(dy))) )/*90:135 270:315*/ { if( (dx>0)&&(dy<0)&&(dx<abs(dy)) ) { tempx = x1; x1 = x2; x2 = tempx; tempy = y1; y1 = y2; y2 = tempy; } dy = (y2-y1); dx = (x2-x1); y3 = y1; x3 = x1; p = 2*dx+dy; while(y1<y2) { y1++; if(p>=0) { p=p+2*dx; } else if(p<0) { x1--; p=p+2*dx+2*dy; } if( ((y1-y3)>width1)&&flag) { uglLine(gc,x3,y3,x1,y1); y3=y1; x3=x1; flag=0; } else if( ((y1-y3)>width0)&&!flag) { y3=y1; x3=x1; flag=1; } } } else if(dx==0)/*90 270*/ { if(y1>y2) { tempy = y1; y1 = y2; y2 = tempy; } y3 = y1; while(y1<y2) { y1++; if( ((y1-y3)>width1)&&flag ) { uglLine(gc,x1,y3,x1,y1); y3=y1; flag=0; } else if( ((y1-y3)>width0)&&!flag ) { y3=y1; flag=1; } } } else if(dy==0)/*0 180*/ { if(x1>x2) { tempx = x1; x1 = x2; x2 = tempx; } x3=x1; while(x1<x2) { x1++; if( (x1-x3>width1)&&flag ) { uglLine(gc,x3,y1,x1,y1); x3=x1; flag=0; } else if( ((x1-x3)>width0)&&!flag ) { x3=x1; flag=1; } } } }

新手来报到一：bresenham算法实现虚线（VxWorks5.5 WindML3.0