搜索
扫描转换扫描转换直线段DDA算法基本思想：直接求点中点算法基本思想：根据一个点的取值范围来确定下一个点的取值是NE还是E（利用取值范围的中点M在直线上方还是下方来确定取点）具体实现：以中点d的符号来确定取NE还是E，当d0，取E，反之取NE；F（x，y）=deltaX*y-deltaY*x-deltaX*B为了去除分母，d=2*F（x，y）然后d的符号是根据递推式来求取，直接用（x+2，yi+1+0.5）带入F，然后根据yi+1与yi的关系把F（x+1，yi+0.5）的那部分取出来，剩余一部分就是要加上去的那一部分。最后d0di+1=di-2*delataYd0di+1=di-2(deltaY-deltaX)扫描转换圆弧中点算法基本思想：与直线段的中点算法非常相似，同样根据一个点的取值范围来确定下一个点的取值是E还是SE（利用取值范围的中点M在圆的内部还是外部来确定取点）具体实现：以中点d的符号来确定取SE还是E，当d0，取SE，反之取E；F（x，y）=x^2+y^2-R^2d=F(M)然后d的符号是根据递推式来求取，直接用（x+2，yi+1-0.5）带入F，然后根据yi+1与yi的关系把F（x+1，yi-0.5）的那部分取出来，剩余一部分就是要加上去的那一部分。最后d0di+1=di+2(xi-yi)+5d0di+1=di+2xi+3注:改进算法中为了去除浮点，整体乘4去除d0中分母4以及进一步的可以用查分的方法求得d的递归式子正负法基本思想：利用F（x，y）的正负划分性，针对扫描转化第一象限那八分之一圆弧，我们先假设往右走一步到P1，然后往下或往右继续走，根据Pi与p1的乘积的符号决定，由于p1恒为正数，所以直接根据pi的符号即可判断。若pi为正数，则往前进deltaY，否则前进deltaX。具体实现：若前进deltaY，则用y-1带入F求取递归式，反正用x+1带入。最后pi0dpi+1=dpi-2yi+1pi0dpi+1=dpi+2xi+1扫描转换矩形基本思想：直接找到矩形的box，然后直接用一个for循环即可。扫描转换多边形逐点判断算法基本思想：找到多边形的box，然后依次判断里面的点是否属于多边形，可以用逐点判断算法，累计角度法或者是编码法来判断点是否在多边形内部。注：这里特别实现过，所以是重点射线法基本思想：为了方便，从一个点引出水平向右的射线，然后计数它与多边形边的交点个数来确定它是否在多边形内，若为奇数则在多边形内，否则在多边形外。但是要注意水平边取0个交点，还有顶点下取上不取这些奇异情况。编码法基本思想：它是累计角度法的离散化思想，以v为原点建立坐标系，然后对各边进行编码，然后相加的和若为0，则在外部，若为+-4，则在内部。在求和过程中特别要注意+-3的情况要进行加减周期4处理，还有+-2的情况，这是跨象限的情况，所以要额外判断，可以根据直线与y=0的交点的正负来进行判断。还有若顶点落在坐标系上，这种特殊处理，简化吧。扫描线算法基本思想：点的连续性和边的连续性来减少无效的判断，建立边的分类表ET和活化边表AEL。然后从最小的y开始依次往上走，依次组织成对交点进行填充即可。但是要注意取整必须往多边形内部方向取整，以及落在边上左取右不取，还有顶点下取上不取，水平边不计。边缘填充算法基本思想：有两种，第一种以扫描线为中心向右填充，第二种以边为中心向右填充。若填充了偶数次，则那些点就是外部点，奇数次则为内部点。填充图元区域填充递归填充算法基本思想：直接调用递归。扫描线算法基本思想：利用扫描线连续性，先以一个种子点填充其所在的区段，然后进行上下填充，这个算法相对比较复杂，涉及堆栈的一些基本操作，所以估计不会出大题。二维裁剪直线段裁剪直接求交算法基本思想：判断两个端点关于裁剪框的关系即可。Cohen-Sutherland算法基本思想：编码法的思想，先对各区域进行合理的编码，然后直接可以确定完全可见和完全不可见的线段，剩下的可以不断进行与矩形框某一条边的求交，然后舍去其外部部分。注：这个算法我认为也比较重要，也实现过，可能是写其中的片段算法。Nicholl-Lee-Nicholl算法基本思想：在Cohen-Sutherland算法的基础上，更加划分细的区域减少求交。中点分割算法基本思想：用递归的方法以一个精确度E来找p0和p1最近的可见点。梁友栋-Barsky算法基本思想：生成诱导窗口将二维的相加问题转到一维上来，可见部分VW=P0P1交LR交TB，LR和TB分别是P0P1所在直线与窗口左右上下所交的点连线。然后以参数式的形式求得相应的t0‘，t0’‘，t1‘，t1’‘，以及初始的（0,1）求交集。主要是定义r=d/q来求取交点这里，这是用相似的方法得出的，比如说（x0-xL）/deltax，可以看做是p0交点与p0p1在水平方向上的比例，这样得到t带入参数式就可以得到交点了。注：这个算法我认为也比较重要。多边形裁剪Sutherland-Hodgman算法基本思想：逐边裁剪法，利用窗口边的半空间特点，则考虑到4种不同情况。然后以点为着眼点，结果集中的点的集合为交点或者是原来的顶点的集合。Weiler-Atherton算法基本思想：主多边形和裁剪多边形的部分边的组合形成了结果集，所以定义了两类点，一类为进点，另一类为出点，然后分别建立主多边形的顶点表和裁剪多边形的顶点表，它们分别在交点处发生变化，只要用双向链表跟踪即可。