精华内容
下载资源
问答
  • Weiler Atherton 任意多边形裁剪 Sutherland Hodgeman 算法解决了裁剪窗口为凸多边形窗口的...Weiler Atherton 任意多边形裁剪算法描述 在算法中裁剪窗口被裁剪多边形可以是任意多边形凸的凹的内角大于 180 o 甚至是带
  • Weiler-Atherton多边形裁剪算法

    千次阅读 2015-08-21 17:00:17
    这是一个通用的多边形裁剪算法,既可以裁剪凸多边形也可以裁剪凹多边。 通过下图来描述算法的执行过程 图中DCBA为裁剪窗口,dcba为要裁剪的多边形。在算法执行之前将多边形和裁剪窗口的交点分别加入他们的...

    来自:http://blog.csdn.net/liaojinyu282/article/details/6011177

    这是一个通用的多边形裁剪算法,既可以裁剪凸多边形也可以裁剪凹多边。

    通过下图来描述算法的执行过程

    img79

    图中DCBA为裁剪窗口,dcba为要裁剪的多边形。在算法执行之前将多边形和裁剪窗口的交点分别加入他们的顶点序列。即图中的123456。

    则多边形序列为:a,6,5,d,4,3,c,2,b,1

    裁剪窗口序列为:A,5,4,D,C,1,B,2,3,6

    从多边形顶点a开始按逆时针方向遍历多边形顶点。到达多边形与裁剪边界的交点6,此时线段是从裁剪区的外部进入裁剪区内部

    (即交点6一个entering intersection),则在多边形序列上继续遍历直到找到第一个从边界“出去”的点或者一个已经遍历过的点,图中所示为交点5(称交点5为一个exiting intersection);

    此时线段从裁剪区内出去,这时在裁剪窗口序列的当前顶点开始逆时针遍历(此时为交点5),到达交点4,线段d4指向多边形内部,交点4是一个entering intersection;

    转换到多边形序列继续遍历,到交点3,交点3是一个exiting intersection;

    转换到裁剪窗口序列逆时针遍历,到交点6,发现6已经访问过,得到顶点序列6543,即为一个要绘制的多边形;

    这时退回到最后一个exiting intersection,即顶点3,在多边形序列上遍历,找到一个   entering intersection,即点2,然后按照上述过程得到一个顶点序列2b1B,此时多边形所有的点均已访问,算法结束;

    整个算法就是先计算多边形和裁剪窗口的顶点序列,然后根据交点是一个entering intersection还是exiting intersection选择在不同的顶点序列上遍历,直到所有的点都访问完

    输入给出多边形序列和裁剪窗口的序列,首先要一个预处理将他们的交点按依序插入各自的序列,一个比较直接的办法,可以直接按逆时针遍历这两个序列,每次取2个点组成一个线段与另一个序列的每条边比较计算交点,得出一个要插入的点集,然后按照该点集中的每个点到线段起点的距离按序插入,离起点近的就先插入;

     

    参考 :

    《计算机图形学》 赫恩

    http://www.cs.fit.edu/~wds/classes/graphics/Clip/clip/clip.html

    http://en.wikipedia.org/wiki/Weiler–Atherton_clipping_algorithm


    展开全文
  • 多边形裁剪二:Weiler-Atherton算法

    万次阅读 2014-07-13 13:21:57
    Weiler-Atherton任意多边形裁剪  Sutherland-Hodgeman算法解决了裁剪窗口为凸多边形窗口的...一、Weiler-Atherton任意多边形裁剪算法描述:  在算法中,裁剪窗口、被裁剪多边形可以是任意多边形:凸的、凹的(内

    Weiler-Atherton任意多边形裁剪

      Sutherland-Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题,但一些应用需要涉及任意多边形窗口(含凹多边形窗口)的裁剪。Weiler-Atherton多边形裁剪算法正是满足这种要求的算法。

     

    WeilerAtherton任意多边形裁剪算法描述:

      在算法中,裁剪窗口、被裁剪多边形可以是任意多边形:凸的、凹的(内角大于180o)、甚至是带有内环的(子区),见下图。

      裁剪窗口和被裁剪多边形处于完全对等的地位,这里我们称:

      1、被裁剪多边形为主多边形,记为A;

      2、裁剪窗口为裁剪多边形,记为B。

      主多边形A和裁剪多边形B的边界将整个二维平面分成了四个区域:
      1、A∩B(交:属于A且属于B); 
      2、A-B(差:属于A不属于B);
      3、B-A(差:属于B不属于A);
      4、A∪B(并:属于A或属于B,取反;即:不属于A且不属于B)。

      内裁剪即通常意义上的裁剪,取图元位于窗口之内的部分,结果为A∩B。

      外裁剪取图元位于窗口之外的部分,结果为A-B。

      观察下图不难发现裁剪结果区域的边界由被裁剪多 边形的部分边界和裁剪窗口的部分边界两部分构成,并且在交点处边界发生交替,即由被裁剪多边形的边界转至裁剪窗口的边界,或者反之。由于多边形构成一个封闭的区域,所以,如果被裁剪多边形和裁剪窗口有交点,则交点成对出现。这些交点分成两类:

      一类称“入”点,即被裁剪多边形由此点进入裁剪窗口,如图中a、c、e;
      一类称“出”点,即被裁剪多边形由此点离开裁剪窗口,如图中b、d、f。

                     

     

    WeilerAtherton任意多边形裁剪算法思想:

      假设被裁剪多边形和裁剪窗口的顶点序列都按顺时针方向排列。当两个多边形相交时,交点必然成对出现,其中一个是从被裁剪多边形进入裁剪窗口的交点,称为“入点”,另一个是从被裁剪多边形离开裁剪窗口的交点,称为“出点”。

      算法从被裁剪多边形的一个入点开始,碰到入点,沿着被裁剪多边形按顺时针方向搜集顶点序列;

      而当遇到出点时,则沿着裁剪窗口按顺时针方向搜集顶点序列。

      按上述规则,如此交替地沿着两个多边形的边线行进,直到回到起始点。这时,收集到的全部顶点序列就是裁剪所得的一个多边形。

      由于可能存在分裂的多边形,因此算法要考虑:将搜集过的入点的入点记号删去,以免重复跟踪。将所有的入点搜集完毕后算法结束。

     

    三、WeilerAtherton任意多边形裁剪算法步骤:

      1、顺时针输入被裁剪多边形顶点序列Ⅰ放入数组1中。

      2、顺时针输入裁剪窗口顶点序列Ⅱ放入数组2中。

      3、求出被裁剪多边形和裁剪窗口相交的所有交点,并给每个交点打上“入”、“出”标记。

        然后将交点按顺序插入序列Ⅰ得到新的顶点序列Ⅲ,并放入数组3中;

        同样也将交点按顺序插入序列Ⅱ得到新的顶点序列Ⅳ,放入数组4中;

      4、初始化输出数组Q,令数组Q为空。接着从数组3中寻找“入”点。

        如果“入”点没找到,程序结束。

      5、如果找到“入”点,则将“入”点放入S中暂存。

      6、将“入”点录入到输出数组Q中。并从数组3中将该“入”点的“入”点标记删去。

      7、沿数组3顺序取顶点:

        如果顶点不是“出点”,则将顶点录入到输出数组Q中,流程转第7步。
        否则,流程转第8步。

      8、沿数组4顺序取顶点:

        如果顶点不是“入点”,则将顶点录入到输出数组Q中,流程转第8步。
        否则,流程转第9步。

      9、如果顶点不等于起始点S,流程转第6步,继续跟踪数组3。

        否则,将数组Q输出;

        流程转第4步,寻找可能存在的分裂多边形。

        算法在第4步:满足“入”点没找到的条件时,算法结束。算法的生成过程见下图所示。

     

     

    四、WeilerAtherton任意多边形裁剪算法特点:

      1、裁剪窗口可以是矩形、任意凸多边形、任意凹多边形。

      2、可实现被裁剪多边形相对裁剪窗口的内裁或外裁,即保留窗口内的图形或保留窗口外的图形,因此在三维消隐中可以用来处理物体表面间的相互遮挡关系。

      3、裁剪思想新颖,方法简洁,裁剪一次完成,与裁剪窗口的边数无关。

     

    五、WeilerAtherton任意多边形裁剪算法小结:

      前面介绍的是内裁算法,即保留裁剪窗口内的图形。而外裁算法(保留裁剪窗口外的图形)同内裁算法差不多。

      外裁算法与内裁算法不同的是:

      1、从被裁剪多边形的一个“出点”开始,碰到出点,沿着被裁剪多边形按顺时针方向搜集顶点序列;

      2、而当遇到“入点”时,则沿着裁剪窗口按逆时针方向搜集顶点序列。

      按上述规则,如此交替地沿着两个多边形的边线行进,直到回到起始点为止。这时,收集到的全部顶点序列就是裁剪所得的一个多边形。

      由于可能存在分裂的多边形,因此算法要考虑:将搜集过的“出点”的出点记号删去,以免重复跟踪。将所有的出点搜集完毕后算法结束。

      Weiler-Atherton算法的的设计思想很巧妙,裁剪是一次完成,不象Sutherland-Hodgman多边形裁剪算法,每次只对裁剪窗口的一条边界及其延长线进行裁剪,如裁剪窗口有n条边,则要调用n次S-H算法后才能最后得出裁剪结果。

      但Weiler-Atherton算法的编程实现比Sutherland-Hodgman算法稍难,主要难在入、出点的查寻以及跨数组搜索上。

     

    六、未测试的代码(正确代码见以后更新)

    1. typedef struct PWAPoint  
    2. {  
    3.     RtPoint point;  
    4.     int  flag;//0表示被剪裁多边形,1表示交点  
    5.     int  index;//属于被剪裁哪个线段的交点  
    6.     int index0;//属于剪裁哪个线段的交点  
    7.     int  flag0;//0表示入,1表示出,-1表示清除  
    8. }PWAPoint;  
    9.   
    10. typedef struct PWAArray  
    11. {  
    12.     double dist;//交点于启点的距离  
    13.     int index;//交点存储位置  
    14. }PWAArray;  
    15.   
    16. //多边形点必须是顺时针方向  
    17. int rtPrunePWA(RtPoint* src, int num, RtPoint* dest, int total)  
    18. {  
    19.     int i = 0, j = 0, k = 0,n = 0,m = 0, w = 0,u = 0;  
    20.     RtPoint sp, ep;//剪裁多边形  
    21.     RtPoint startP, endP;//被剪裁多边形  
    22.   
    23.     CRtPoint<double> point;  
    24.     CRtPoint<int> st, et;                   
    25.     CRtLine<int> v1,v2;  
    26.   
    27.     PWAPoint* injectP = (PWAPoint*)malloc(sizeof(PWAPoint) * num * total);  
    28.     PWAPoint* temp = (PWAPoint*)malloc(sizeof(PWAPoint) * num * (total));//剪裁加交点插入  
    29.     PWAPoint* temp0 = (PWAPoint*)malloc(sizeof(PWAPoint) * num * (total));//被剪裁加交点插入  
    30.     PWAArray* inP = (PWAArray*)malloc(sizeof(PWAArray) * num * (total));  
    31.     RtPoint* dst = (RtPoint*)malloc(sizeof(RtPoint) * num * total);//输出数组  
    32.   
    33.     //求交点  
    34.     startP = *(dest + total - 1);  
    35.     for (j = 0; j < total; j++)//被剪裁多边形  
    36.     {  
    37.         endP = *(dest + j);  
    38.         st.SetData(startP.x, startP.y);  
    39.         et.SetData(endP.x, endP.y);  
    40.         v2.SetData(st, et);  
    41.   
    42.         sp = *(src + num - 1);  
    43.         for (i = 0; i < num; i++)//剪裁多边形  
    44.         {  
    45.             ep = *(src + i);  
    46.             st.SetData(sp.x, sp.y);  
    47.             et.SetData(ep.x, ep.y);  
    48.             v1.SetData(st, et);   
    49.               
    50.             if(v2.Intersect(v1,point))//求交点   
    51.             {  
    52.                 injectP[k].point.x = point[0];  
    53.                 injectP[k].point.y = point[1];  
    54.                 injectP[k].flag = 1;  
    55.                 injectP[k].index = j;  
    56.                 injectP[k].index0 = i;  
    57.             }  
    58.             sp = ep;  
    59.         }  
    60.         startP = endP;  
    61.     }  
    62.   
    63.     //剪裁多边形插入交点  
    64.     w = 0;  
    65.     for (i = 0; i < num; i++)  
    66.     {  
    67.         temp[w].point = *(src + i);  
    68.         temp[w].flag = 0;  
    69.         w++;  
    70.   
    71.         n = 0;  
    72.         for (j = 0; j < k;j++)  
    73.         {  
    74.             if (injectP[j].index0 == j)//属于剪裁当前线段的交点  
    75.             {  
    76.                 inP[n].dist = sqrt(pow(injectP[j].point.x - temp[w].point.x , 2) + pow(injectP[j].point.y - temp[w].point.y , 2));  
    77.                 inP[n].index = j;  
    78.                 n++;  
    79.             }  
    80.         }  
    81.   
    82.         for (j = 0; j<n; j++)  
    83.         {  
    84.             for (m = j+1;m<n;m++)  
    85.             {  
    86.                 PWAArray tempp;  
    87.                 if (inP[j].dist > inP[m].dist)  
    88.                 {  
    89.                     tempp = inP[j];  
    90.                     inP[j] = inP[m];  
    91.                     inP[m] = tempp;  
    92.                 }  
    93.             }  
    94.         }  
    95.   
    96.         for (j = 0; j < n;j++)  
    97.         {  
    98.             temp[w] = injectP[inP[j].index];  
    99.             w++;  
    100.         }  
    101.   
    102.     }  
    103.   
    104.     //被剪裁多边形插入交点  
    105.     u = 0;  
    106.     for (i = 0; i < total; i++)  
    107.     {  
    108.         temp0[u].point = *((dest) + i);  
    109.         temp0[u].flag = 0;  
    110.         u++;  
    111.           
    112.         n = 0;  
    113.         for (j = 0; j < k;j++)  
    114.         {  
    115.             if (injectP[j].index0 == j)//属于剪裁当前线段的交点  
    116.             {  
    117.                 inP[n].dist = sqrt(pow(injectP[j].point.x - temp0[u].point.x , 2) + pow(injectP[j].point.y - temp0[u].point.y , 2));  
    118.                 inP[n].index = j;  
    119.                 n++;  
    120.             }  
    121.         }  
    122.           
    123.         for (j = 0; j<n; j++)  
    124.         {  
    125.             for (m = j+1;m<n;m++)  
    126.             {  
    127.                 PWAArray tempp;  
    128.                 if (inP[j].dist > inP[m].dist)  
    129.                 {  
    130.                     tempp = inP[j];  
    131.                     inP[j] = inP[m];  
    132.                     inP[m] = tempp;  
    133.                 }  
    134.             }  
    135.         }  
    136.           
    137.         for (j = 0; j < n;j++)  
    138.         {  
    139.             temp0[u] = injectP[inP[j].index];  
    140.             u++;  
    141.         }  
    142.           
    143.     }  
    144.   
    145.     //标记出入点  
    146.     for (i = 0; i < w; i++)  
    147.     {  
    148.         if (temp[i].flag == 1)  
    149.         {  
    150.             if (i == w - 1)  
    151.             {  
    152.                 if(temp[0].flag == 0)  
    153.                 {  
    154.                     temp[i].flag0 = 0;  
    155.                 }  
    156.                 if (temp[0].flag == 1)  
    157.                 {  
    158.                     temp[i].flag0 = 1;  
    159.                 }  
    160.             }  
    161.             else  
    162.             {  
    163.                 if (temp[i + 1].flag == 0)  
    164.                 {  
    165.                     temp[i].flag0 = 0;  
    166.                 }  
    167.                 else  
    168.                 {  
    169.                     temp[i].flag0 = 1;  
    170.                 }  
    171.             }             
    172.         }  
    173.     }  
    174.     for (i = 0; i < u; i++)  
    175.     {  
    176.         if (temp0[i].flag == 1)  
    177.         {  
    178.             if (i == u - 1)  
    179.             {  
    180.                 if(temp0[0].flag == 0)  
    181.                 {  
    182.                     temp0[i].flag0 = 0;  
    183.                 }  
    184.                 if (temp0[0].flag == 1)  
    185.                 {  
    186.                     temp0[i].flag0 = 1;  
    187.                 }  
    188.             }  
    189.             else  
    190.             {  
    191.                 if (temp0[i + 1].flag == 0)  
    192.                 {  
    193.                     temp0[i].flag0 = 0;  
    194.                 }  
    195.                 else  
    196.                 {  
    197.                     temp0[i].flag0 = 1;  
    198.                 }  
    199.             }             
    200.         }  
    201.     }  
    202.   
    203.     k = 0;  
    204.     //统计剪裁区域  
    205. loop3:  
    206.     for (i = 0; i < u; i++)//被剪裁区域  
    207.     {  
    208.         if (0 == temp0[i].flag0)//是入点  
    209.         {  
    210.             dst[k] = temp0[i].point;  
    211.             k++;  
    212.             temp0[i].flag0 = -1;  
    213.             goto loop0;  
    214.         }  
    215.     }  
    216.     return 1;  
    217.   
    218. loop0:  
    219.     for (j = i; j < u; j++)  
    220.     {  
    221.         if (temp0[i].flag0 != 1)//不是出点  
    222.         {  
    223.             dst[k] = temp0[i].point;  
    224.             temp0[i].flag0 = -1;  
    225.             k++;  
    226.         }  
    227.         else  
    228.         {  
    229.             goto loop1;  
    230.         }  
    231.     }  
    232.   
    233. loop1:  
    234.     for (m = 0; m < w; m++)  
    235.     {  
    236.         if (dst[k].x == temp[m].point.x && dst[k].y == temp[m].point.y)  
    237.         {  
    238.             goto loop2;  
    239.         }  
    240.     }  
    241.   
    242. loop2:  
    243.     for (n = m+1;n < w; n++)  
    244.     {  
    245.         if (temp[i].flag0 != 0)//不是入点  
    246.         {  
    247.             dst[k] = temp[i].point;  
    248.             temp[i].flag0 = -1;  
    249.             k++;  
    250.         }  
    251.         else  
    252.         {  
    253.             goto loop3;  
    254.         }  
    255.     }  
    256.   
    257.     free(injectP);  
    258.     free(temp);  
    259.     free(temp0);  
    260.     free(inP);  
    261.     return 0;  
    262. }  

     

    展开全文
  • 故贴在此处,希望对看到的人能有帮助,如果转载,请注明作者:shaoshaoh 出处:本页网址图形学课程设计报告——基于编码技术的直线和多边形的裁剪一、直线的多边形裁剪1、直线裁剪的算法描述课本中的算法5.3-1描述了...

    本文为本人原创,是图形学课程设计的报告,投入了很多的精力,尤其是对于任意多边形裁剪的算法的一些想法,觉得还是有一些价值,故贴在此处,希望对看到的人能有帮助,如果转载,请注明作者:shaoshaoh 出处:本页网址

    图形学课程设计报告

    ——基于编码技术的直线和多边形的裁剪

    一、直线的多边形裁剪

    1、直线裁剪的算法描述

    课本中的算法5.3-1描述了【求取一条线段与一个图形的公共部分的算法】,该算法通过求取直线段与多边形的所有交点,然后对交点进行排序,来确定交点的奇偶性,然后再根据交点的奇偶性,方便地求出直线段与多边形的公共部分。当然,其中包含了交点特征值,以及对于重交点的处理。

    该算法思路清晰,判断准确,是一个好的算法。但是,该算法在实际实行上却有不少的问题。首先,该算法要求多边形的方向是正向,既逆时针,只有这样才能够正确处理特征值的问题,然而,我们要做的工作是实现一个可交互式的图形裁剪试验程序,不可能要求用户只按照逆时针的顺序来输入多边形。其次,该算法的第一个步骤求交点,使用的是参数法,这个方法求出的点可能在直线段上,其延长线上,多边形的边上,边的延长线上。其中在多边形的边的延长线上交点是完全没有必要求取的。而对于一个普通的多边形来说,这样的点恰恰很多。所以,对于这个部分,该算法的效率也还有很大的提升空间。

    改进这两个问题就要做到:

    l         对多边形的方向没有要求;

    l         大幅提高求交点的效率,避免不必要的运算;

    参考了相关领域的研究成果,我决定实现陆国栋等[1]提出的算法。该算法使用了和Cohen-Sutherland算法相同的思路,都是通过编码,巧妙的排除无关的线段。大大减少了求交点的运算次数,也因此,很大程度上提高了效率。

    下面,我对该算法进行简要的一个描述。

    该算法第一个亮点在于,其编码对象为多边形的顶点,即,不是对裁剪对象进行编码,而是对裁剪窗口进行编码,这点与Cohen-Sutherland不同,但是却是异曲同工之妙。

    我们知道,平面上的直线都可以表示成 的形式。利用这个方程,我们将平面上的点集分成三个子集:

    (1)  对这个集合,我们称为负集,记为G-

    (2)  对这个集合,我们称为零集,记为G0

    (3)  对这个集合,我们称为正集,记为G+

    显然,对于直线 ,如果线段AB和直线有一个交点(非AB),当且仅当AB分别落在正集和负集。算法利用这个原理,对于多边形的每个顶点进行分类,也即编码。实现了完全避免求取那些落在多边形边的延长线上的交点。

    这个想法是不错,但是要对顶点进行分类,免不了要把多边形的顶点带入到直线方程中去计算,而且还是复杂的乘法运算,这样下来,也节省不了多少。

    本算法的第二个亮点就是,利用“简单直线”放大零集,简化运算,快速编码。

    为了进一步提高效率,该算法采用放大零集的做法。在平面上,坐标轴和|k|=1的四根直线,把平面分成了8个区域,将其中那个直线段所在的区域作为拟似的零集,可以对零集以外的点进行快速判断。如下图:

    A

    B

    G0

    G-

    G+

    直线段AB所在的直线的k满足 ,对于使得yi<xi成立的点(xi,yi)来说,肯定可以使yi<kxi+b成立,即在y=x直线右侧的点,肯定输入直线AB的负集;而对于使xi<0成立的(xi,yi)来说,则一定可以使yi>kxi+b成立,即点肯定属于正集。而其判断都仅需一次比较就可以完成,非常的高效。

    最后只有那些在y轴和y=x中间区域的多边形顶点,才需要带入到直线的方程中去判断,这些点到底真正落在那个集合。

    编码时候,可以令正集的点编码为f=1,负集的为f=-1,零集的为f=0。在求交点的时候,如果多边形的边的两个端点的fi*fi+1<0,则肯定有交点,开始求交点,如果fi*fi+1>0,则肯定没有交点,不用求,如果fi*fi+1=0,则说明是情况比较特殊,有至少一个顶点在直线上,这时候应该专门处理,但是实际情况中,进入这个分支的时候很少。

    不失一般性,在具体实现的时候,不会正好是坐标轴和y=xy=-x四条直线分割平面,我们会重新选择一个特定的“原点”,以确保最大程度的区分多边形的顶点,减少计算。在实际处理的时候,选用的是多边形的外接矩形的边界上的点。

    详细的描述,可以参考文献[1]

    算法流程图如下:

    2、直线裁剪的主要数据结构及算法实现

    struct poly_vertex

    {

        int x;

        int y;

        int f; //code

    };

    struct CodecPoly

    {

        CTypedPtrList<CPtrList,poly_vertex*> poly;

    };

    上述为算法实现时主要采用的数据结构,poly_vertex是多边形的顶点的一个结构,其中f用来表示其相对于直线的编码值,CodecPoly是一个编码了的多边形,poly是一个poly_vertex指针组成的类型安全的链表。

    算法的实现要对多边形窗口进行两次遍历,第一次对每个顶点进行编码,第二次,求出所有的交点。交点求取结束后,对交点进行排序,根据第一个有效的交点(即不在线段的延长线上)的序数的奇偶性,可以确定此点的出入性,交点的出入性是交替出现的,所以对后序的点不用作判断,遍历交点的链表,每遇到一个入点,就以此点为始点,其后紧接着的出点为终点创建一条线段,加入当前的线段集合。如果线段起点在多边形内,则以起点为第一个入点,如果最后一个交点是入点,则以被裁剪线段的终点为出点。最后删去原被裁剪线段,则完成了裁剪。

    这里值得补充的是对上文中提到的fi*fi+1=0时候的处理,也即对奇异情况的处理。对于此种情况,可以增加一个顶点Vi-1来帮助判断。如果fi-1*fi+1=1,说明Vi在直线上,而Vi-1Vi+1位于直线的同侧,此时的Vi不能改变直线的出入性,所以直接舍去;如果fi-1*fi+1=-1,说明Vi-1Vi+1位于直线的异侧,改变了直线的出入性,Vi直接加入交点链表;如果fi-1*fi+1=0,情况比较复杂,如果fi =0,说明,ViVi+1这条边与直线重合,则如果这条边时多边形的凸边,则应该保留Vi进入交点链表,如果是凹边,则应该舍去;如果fi0,说明Vi-1或者Vi+1在直线上,这两种情况可以不处理,为什么呢?因为Vi-1在上一个循环中是Vi,而Vi+1在下一个循环中处于Vi的地位,不用重复处理。

    3、结果分析

    该算法适应性良好,多余非常复杂的情况也有良好的适应性。如图:

            

    而且裁减的速度很快,对于直线非常多的情况也完全没有问题。如图:

    对于许多不同方向上的直线的同时裁剪的效果图。可见该算法对于各种方向的直线都有很好的适应性,正确性。

     

    二、多边形的矩形裁剪

    1、多边形的裁剪的算法描述

    多边行的矩形裁剪,课本上介绍了Sutherland-Hodgman的算法,我觉得对于矩形裁剪来说,这应该算得上最简单的算法了。但是,这个算法的性能并不差。这又验证了,简单的就是优美的,高效的那么一个道理。

    Suterland-Hodgman算法用矩形窗口的边界做刀,分别对多边形进行裁剪,每裁剪一次,进行一次封口操作,这样,一共四次,就可以完成对于多边形的裁剪。

    其裁剪过程如图所示:

    有感于直线的多边形线裁剪算法,我在Sutherland-Hodgman算法中加入了编码的成分。以提高对交点有无的判断,进而减少求交次数。

    具体编码方案,采用了Cohen-Sutherland的编码方案,这个编码方案在直线的矩形窗口裁剪中本来是有缺陷的,即它不能快速排除跨越三个区域的直线。然而,这个编码方案用在这里却是正正好好,恰到好处,因为这种裁剪方案,每次使用一条边裁剪,仅需对分布在两个区域的线段作判定,使这种编码方案显示了充分的威力。

    在具体实现的时候,我是这么做的:

    首先,基于矩形窗口对多边形进行编码;

    然后,依次裁剪,裁剪的时候,根据编码,可以快速排除,如果一条边位于窗口的一个边界的同侧,则不予处理。对于,分布在边界两侧的边,求出其交点,并且加入到多边形中。

    对于封口操作,我这里也想出了一个新的办法,可以在裁剪的同时,就完成封口操作。不用额外地使用一个函数。

    下面,我提一下我的设计思路:

    我在这里用编码值标记顶点的有效性。刚才不是提到了使用Cohen-Sutherland算法中的编码方案吗,根据这个编码,我可以对一些明显不在裁剪范围内的点进行舍去。这个判断的条件其实是相当简单的,取出该顶点关于某条边的编码的位,如果为0,有效,为1则无效。

    比如上面图中,白色和黄色三角形的顶点,对于上边界可以直接舍去,蓝色和黄色三角形标记的顶点对于右边界可以舍去。有了无效的判断方法,在进行边裁剪的时候,就可以轻易完成封口操作,在裁剪中,首先准备一个结果链表,用来存储一条边裁剪过后的结果多边形。

    然后从多边形首节点开始遍历,取出多边形首节点和次节点编码中针对这条边的码值,比如对于上图中,针对上边界,只要把每个顶点的编码值与8作位与,就可以取得了。这个取出的码值如果为零,说明这个顶点在结果链表中,如果两个连续顶点,一个码值为零,另一个不为零,所名跟当前切割边必有交点,求出交点,求出交点的编码,然后把交点加入到多边形链表中,指针后移一个,继续遍历多边形。真正巧妙的在于,由于刚才把无效的顶点直接舍去了,求出的结果多边形正好是已经正确封口的多边形,不需要额外的封口操作了。

    下面给出算法的流程图:

    对所有顶点编码

    是否全在内部

    进行四次线裁剪

    取出当前节点及其下一个节点

    取出两个顶点关于当前边的编码

    当前节点码值为零

    加入结果链表

    当前节点与下一个节点码值不等

    开始

    求交点,求交点的编码(其实是全零),将交点加入到结果链表,指针后移一个。

    结束

    N

    Y

    4

    Y

    N

    N

    Y

    2、多边形的裁剪的数据结构

    struct vertex{

        int x,y;

        int code1;

        bool valid;

        ……

        vertex(const vertex& v)

        {

            x = v.x;

            y = v.y;

            code1 = v.code1;

            code2 = v.code2;

            valid = v.valid;

        };

        vertex(int x, int y)

            :code1(0),code2(0),valid(false)

        {

            this->x = x;

            this->y = y;

        };

        vertex& operator=(const vertex& v)

        {

            if (this == &v) return *this;

            x = v.x;

            y = v.y;

            code1 = v.code1;

            code2 = v.code2;

            valid = v.valid;

        };

        bool operator<(const vertex& v)

        {

            if (x < v.x) return true;

            if (x == v.x && y < v.y) return true;

            return false;

        };

    };

    //多边形数据结构

    struct polygon{

        list<vertex> V;

    };

    顶点使用了自己定义的一个结构,code1用来存放编码的值,多边形使用了和STL结合的办法,用了一个标准的list,主要是看中它操作方便的特性。

    3、结果分析

    当然,正如大家所知道的。Sutherland-Hodgman算法有着很大的局限性,即其只能对凸多边形进行正确的裁剪,而对于凹多边形,在有些情况下会出现无法消去的退化边界,在课本里成为蜿蜒的现象。另一个局限就是不能分块输出。

    对于书上一个经典的例子,就变成下面这种局面:

                        

    其实,还有其它的情况,比如下面的样子:

                         

    这也是退化边,而且,这种类型的退化边根据裁剪顺序的不同,而有所不同。如上图,裁剪顺序为,左,上,右,下。如果换成左,右,上,下,又会有所不同了。

    虽然,Sutherland-Hodgman算法有很大的局限性,但是做为仅仅需要进行凸多边形裁剪的场景的应用,该算法,还是有相当的优势的。

    不过,如果非要实现去除退化边界,结果分块输出的效果,应该怎么做呢?那就只有使用二维布尔运算的办法了。下面,我也会介绍。

    三、任意多边形的裁剪

    1、任意多边形裁剪的算法描述

    任意多边形的裁剪,更加具有一般性,与矩形裁剪不同,对被裁剪的多边形形,和裁剪使用的窗口都没有明确的规定,可以是凹多边形,甚至是带有内环的多边形。

    对于这样的多边形,常常采用的就是二维布尔运算的方法。这种方法,主要优点是通过定义相互的出点和入点,然后可以方便地进行各种布尔运算。对于多边形的裁剪来说,也是其中的一个方面。

    在任意多边形的裁剪算法中,我就是使用二维布尔运算的原理。

    这个原理在书上有叙述,我就不再赘述了,简单说就是先求交点,然后确定交点是入点还是出点。接下去按照书上的描述,进行处理,就可以实现裁剪了。

    我这里主要是提几个关键性的问题。

    书上提到的二维布尔求交是基于几个假设的,首先多边形是有方向的,书上假设的是多边形都是逆时针方向的。在这种假设下,多边形的入点和出点才有意义。这也就意味着,如果想按照算法来解决问题,第一步就是要使两个多边形处于正方向。

    对于这一点,交互式地输入多边形,肯定是不能满足条件的,因为你不能规定用户按照哪个方向来输入多边形。

    我是这么解决的,我发现,对于两个多边形来说,如果两个多边形的方向是一致的,那么对于一方来说的入点对于另外一方来说就是出点,而且对于同一个多边形来说,沿着这个多边形的方向,入点和出点是交替分布的。这其实降低了要求,不要求两个多边形的方向一定是正方向,而是只要求,两个多边形的方向相同。

    那么如何判定两个输入多边形的方向是否相同呢?

    这个就是我这个算法里面比较有新意的地方。我们知道,如果一个多边形是有方向的,其实是说,多边形的边是顺次相连的有向线段。对于一个顶点来说,是一条有向线段的起点,是另一条有向线段的终点。对于这两条线段,我们可以求取它的叉积。这个叉积其实业是一个向量,我发现在于同一个多边形中,凸顶点的叉积都是相同方向的,而凹定点的叉积也是相同方向的,而且是凸顶点的反方向,如果将一个多边形的方向逆转,就会发现这两种方向都发生反转。有了这种特性,我就可以很方便的判定两个多边形的方向是否一致了,只要在两个多边形中各找到一个凸顶点,然后计算叉积,如果符号相同,就说明两个多边形的方向一致,否则,只要任意逆转其中一个多边形就可以了。

    下面,我再用一个图示来说明:

    +1

    +1

    +1

    +1

    -1

    -1

    -1

    -1

    -1

    +1

    对于上面这张图来说,两个多边形的方向如图所示,对于每个顶点,求<进入这个顶点的向量,离开这个顶点的向量>这个有序对的叉积,如果值大于0,则标注+1,小于0则标注-1,我们看到,方向不同的两个多边形的正负情况刚好相反。所以在实际中,我们可以利用这个特性,来判断两个多边形的方向。

    首先求出两个多边形的最左(右,上,下)边的点,这个点一定是凸顶点,对这个点求叉积,如果两个多边形的符号相同,就是同向,进入下一个阶段,如果两个多边形的符号不同,就是反向,这时候,只要逆转其中之一就可以了。

    下面,我还是给出整个算法的流程图:

     

    取得多边形

    取得实体多边形的最左点,求得叉积,负值给sign1

    取得裁剪多边形的最左点,求得叉积,负值给sign2

    sign1 * sign2 > 0

    逆转裁剪多边形

    求裁剪多边形与实体多边形的第一个交点,通过包容性测试判断其出入性,用P指针标记此点

    求出两个多边形的所有的交点,然后插入到两个多边形的链表中。

    P指向的交点是实体多边形相对于裁剪多边形的入点

    沿着实体多边形移动到下一个交点,F指向P

    新建一个结果多边形链表的节点

    F加入结果链表第一个多边形。进入到实体多边形,标记该点已处理

    遇到交点

    将点加入

    将点加入,进入裁剪多边形

    遇到交点

    将点加入

    是否是P

    移动F到下一个没有标记过的入点

    结束

    返回结果链表

    N

    N

    N

    N

    N

    2、任意多边形裁剪的数据结构

    struct vertex {

            int x,y;

            bool inters, used;

            struct vertex *next, *next1, *next2;   

    };

    struct out{

            vertex *polygon;

            struct out *next;

    };

    如上,就是这个算法中使用的数据结构,vertex是一个节点数据结构,我们可以看到,这里面有三个指针域,next是多边形单链表用的。next1表示如果是交点,被插入了实体多边形,使用这个指针,同时这个节点也会被插入到裁剪多边形,使用next2指针。所以实际中最多会用到两个。

    实体多边形和裁剪多边形都是用单链表的结构存储,vertex也可以表到交点,用inters这个bool型来说明是否是交点,used这个bool在输出的时候用来标记节点是否已经处理。

    out是使一个输出链表,它是一个顶点链表的链表,也即是一个多边形的链表,用来存储分块输出的多边形。

    对于数据结构的实际使用,我也用图示来说明:

    对于如下的两个多边形:

    输入后,并且求出所有的交点后是如下图的样子:

    这个数据结构的采用,是参考了刘勇奎等[2]的提法,也主要是因为这个结构比较简单,清晰,而且占用了较少的资源。

    3、结果分析

    使用了二维布尔求交后,可以对任意的多边形求取裁剪,稍作修改,也可以求并,补等运算。完全解决了矩形裁剪时候的蜿蜒,其实只要用多边形来表达矩形,就可以实现正确的矩形裁剪,但是为了比较,我还是保留了矩形裁剪。

    其最后效果如图:

     

    四、实验感想

    通过本次图形学的课程设计,我实践图形学中二维图形处理的很重要的一块,裁剪。裁剪的算法是三维图形处理中消隐的基本算法,也是大型图形处理中很重要的一块,对于算法的正确性,效率都有很高的要求。

    在这次课程设计中,能够选择这个题目我很高兴。学到了很多的知识。

    也曾为了一些技术问题头疼过,但当我真的想出了一个可行的解决方案时,那种欣喜,是无法用语言表达的。

    不管怎么说,我觉得做这个课程设计,我是用了十分的努力的,我也从中获得了极大的满足。这个图形学课程和课程设计,都带给了我很多知识,我在此感谢何老师,您是一位很好的老师,教学认真,讲究方法,授人以渔而非授人以鱼,您是一位不可多得的好老师!

    感谢辛苦评阅此次课程设计的所有人员,包括老师和助教。没有你们,我们也不能顺利完成课程的学习。

    感谢蔡舒同学,你和我选择一样的题目,并且毫不吝啬地和我分享你的经验,和我一起讨论技术问题,使我获得了许多的启发,你的努力认真也使我受到了激励!

    五、参考文献

    [1]   陆国栋,邢世海,彭群生 基于顶点编码的多边形线裁剪高效算法 计算机学报 2002.9

    [2]   刘勇奎,高  云,黄有群 一个有效的多边形裁剪算法 软件学报 2003

    本实验报告的原文及C++代码实现的源文件,请按这里下载!仅供参考!

     
    展开全文
  • 基于MFC的VC++程序,实现基于Weiler-Atherton算法,能使完成任意形状的多边形剪裁。详细功能描述见程序内标注说明。 This is a VC++ program, which implements the cutting function of ramdom polygons, based on...
  • 基本图形生成算法原理 (四) 第三章 本章内容 一点直线段生成 二曲线的生成 三区域填充算法 四线宽与线型的处理 五字符及汉字生成 六二维图形裁剪 六二维图形裁剪 图形坐标系统 点的裁剪 直线线段的裁剪 多边形裁剪...
  • 本实现主要参考了发表于2003年《软件学报》的《一个有效的多边形裁剪算法》(刘勇奎,高云,黄有群)这篇论文,所使用的理论与算法大都基于本文,对论文中部分阐述进行了详细解释,并提取了论文中一些重要的理论加以汇总...
    原文:任意多边形切割/裁剪(附C#代码实现)

    本实现主要参考了发表于2003年《软件学报》的《一个有效的多边形裁剪算法》(刘勇奎,高云,黄有群)这篇论文,所使用的理论与算法大都基于本文,对论文中部分阐述进行了详细解释,并提取了论文中一些重要的理论加以汇总。另外对于论文描述无法处理的一些情况也进行了试探性的分析。

     

    多边形裁剪用于裁剪掉被裁剪多边形(又称为实体多边形,后文用S表示)位于窗口(又称为裁剪多边形,后文用C表示)之外的部分。裁剪的结果多边形是由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界组成的。见下图

    图1

    后文将以这个图来描述裁剪过程,这个图形比原论文给出的图形更具代表性,最主要就在于C1这一点,论文中的图形,切割多边形没有在实体多边形中的点。所以,第一次看的人往往容易误以为切割多边形与交点组成的列表没有作用。

    如图中所示,切割多边形与实体多边形分别为C1C2C3C4和S1S2S3S4S5(由于两个多边形需要同向,需要逆置切割多边形为C1C4C3C2,这个逆置也是有条件的,需要第一个交点保持不变,具体可以见代码实现),我们要得到的结果是C1-I6->I3-I4->I5(-C1)和S4->I1-I2(->S4)这两个结果多边形(其中用"-"表示切割多边形在实体多边形中的边,用"->"表示实体多边形在切割多边形中的边)

     

    算法的实现分为三个阶段:

    阶段1:计算第一个交点,并由第一个交点两多边形相互的进出性判断两个多边形是否同向,如果不同向,将切割多边形反向来使两个多边形方向一致。

    阶段2:依次使用实体多边形每条边去切割裁剪多边形并将交点以正确的顺序分别插入到两个多边形的链表中。

    阶段3:遍历交点列表,获得最终的结果。

    后文将按照这3步来介绍相关的实现要点和代码中主要方法。最后在文章末尾还提到一些特殊情况的处理。

     

    阶段1

    阶段1要判断2个多边形是否同向(同向的重要性在后文有描述),其中很重要的一点就是求切割的交点,当然求交点在第二阶段也是很重要的,这里介绍了求交点第二阶段就不再介绍了。

    (注:判断多边形是顺时针还是逆时针的方法有很多,本文的C#代码将采用原论文中的方法)

    原论文中描述的方法基于一个定理:

    定理1:如果两个相交多边形的边的取向相同(均为顺时针或逆时针方向),则对一个多边形是进点的交点对另一个多边形必是出点。

    如果两个多边形的方向相同,对其中一个多边形求出一个进点或出点以后,另一个多边形的进出性也就确定了。这样,求出交点时只需标记其中一个多边形对另一个多边形的进出性即可。从另一个多边形角度看的进出性相反。

    判断两个多边形是否同向,需要判断交点的进出性。同一个交点对于两个多边形的进出性不同,则两个多边形是同向;否则,两个多边形方向相反。

     

    交点进出性的判定(排除切线与多边形在顶点处相交或与多边形一条边重合的情况。)

    当一条直线切割多边形时,与多边形相交的第一个点是必是进点,第二个点必是出点,如此进点与出点循环出现。

    当一个多边形的边切割另一个多边形时,多边形上所有交点的进出性也是交替出现。

     

    通过上面的分析可知,整个实现过程中一个十分关键的操作就是求线段(阶段1中是求直线与多边形交点)与多边形的交点(即用线切割多边形)。并在这个过程中判断交点对于被切割多边形的进出性。

     

    求交点

    这里介绍一下原论文中给出的名为错切变化法的求交点方法。这种方法基于两直线进行错切变换后交点的x值不变来实现,通过把切线变为斜率为0的直线来使求交点的过程简化。假设切割线段为(x1,y1)、(x2,y2),被切割多边形由v1, v2 … vn构成。求交点过程可以描述如下:

    1. 求斜率d,d是切线的斜率,将(x1,y1)、(x2,y2)按照这个斜率进行变化后可以得到一条水平直线,我们设这条水平直线为y=yc,则有如下方程组:

     

     

    带入可得,有

     

    说明,原论文说这里需要x1<x2(看代码实现可知x1=x2 x1>x2都是特殊处理的)。x1≠x2和y1≠y2也是需要满足的,当x1=x2时表示切线是垂直线,应在垂直方向进行切割,先求交点的坐标y。如果y1=y2则不用错切过程,直接用切线切割即可。保证x1<x2是为了保证交点插入实体多边形的顺序正确。

    下图是一个例子,黑色的线是错切前的线,绿色的线是错切后的线,实线是切线,虚线是多边形上一条被切割的线:

    图2

     

    2. 将多边形上每个点vi(xi, yi)的y坐标按公式进行错切变化得到yi':

     

    3. 对错切后多边形的每条边((xi,yi'),(xi+1,yi+1'))与切线求交点的x坐标Ixj

     

    如,对于前面图中的例子,带入xi, xi+1可得Ix=6.8。

    接着,通过反错切就可以得到Iy,公式:

     

    所以

     

    经计算,Iy=4.6。最终坐标系图像:

     图3

    在多边形切割处理中有一个需要特别注意的问题,就是一个多边形的顶点落在另一个多边形的边上的情况。这种情况会影响交点的进出性判断,从而可能会导致错误的结果。这种点与边重合的情况可以在上述使用线切割多边形的过程中处理。我们分几种情况讨论:

    1. 切线的点落在多边形的一条边上

    下图可以很好的说明这种情况:

    图4

    当通过计算,我们发现交点坐标的x值Ix与切线的坐标x的最大或最小值相等时就发生了这种情况。

    如下面的两组多边形都是这种情况:

    图5

    如果不考虑第二种情况,我们只需将这些坐标的x值Ix与切线的坐标x的最大或最小值相等的点不算在交点(实交点和虚交点都不统计这种情况)内即可忽略这种情况,即我们假设那个点不相交。但这种处理对第二种情况不适用,我们需要知道这个特殊的交点的进出性来决定遇到这个交点后是沿着实体多边形还是切割多边形继续前进。

    对于这种情况,只需将坐标的x值Ix与切线的坐标x的最大或最小值相等的交点作为实交点即可。

    2. 多边形边的一点落在切线上

    如下图所示:

    图6

    当经过错切计算后,错切后的多边形的点的坐标的y值等于yc的话,表示出现了这种情况。由于被切的多边形的边不用计算交点的进出性(当然判断两个多边形方向时是个例外,也就是说判断两个多边形方向时需要选择一个一般化的交点),只需忽略这种多边形的边,不拿它们与切线计算交点即可(简单说,这种交点可以被忽略)。

    如下图使用上述方法可以正确处理:

    图7

     

    3. 边重合的情况

    以上两种情况的处理,由于我们没有改变多边形结点的坐标,所以不会对最终的结果产生错误的影响,是可以接受的解决方案。对于两个多边形有边重合的情况(两多边形结点重合除外,这个问题后面说),如这样两个多边形(其中实体多边形为实线,虚线的为切割多边形,后文例子同),通过上面的方法可以正确处理,且不需要特意去判断重合,我们可以将其作为情况2的一个特例:

    图8

     

    4. 当前文提到的情况1和2同时发生时,就是多边形节点重合的情况,体现在坐标系中为如下这样:

    图9

    看2个这种情况的典型例子:

    图10

    对于这种情况的处理方法,当经过错切计算后,错切后的多边形的点的坐标的y值等于yc的话,且交点的坐标的x值正好等于切线端点的x坐标,即发生当前所述情况,则我们挑多边形边上的一个点认为其有交点,而另一个点认为没有交点。还是用上图的例子来解

    如果现使用I1I2依次切割多边形的边C1C2, C2C3, …我们假设如果多边形边上的第二点(对于C1C2,C2C3第二点分别为C2,C3,另外,使用第一点效果也是一样的)出现情况4时,我们认为其存在实交点。即使用I1I2切 C1C2,我们认为有一个交点,使用I1I2 切C2C3时根据上述规则它们没有交点。这样这种情况就得到正确的处理。

     

    结果上面的介绍,对于各种交点计算都已可以处理,然后按偶奇的顺序来标记进出性也很容易了。下面来看第二阶段。

     

    阶段2

    上面介绍的方法已经可以得到交点与交点的进出性。并根据进出性判断两个多边形的方向,对于不同的向的,需要将其中一个多边形反向。下面是整个算法的另一个重点,用实体多边形的边切割裁剪多边形并将交点插入两个多边形的的链表的过程。

    1. 先把切割多边形与实体多边形连成如下两个链表(前文已处理为方向一致)。

    图11

    2. 用实体多边形S的每条边依次切割切割多边形C,并把交点依次插入实体多边形S与切割多边形C的链表中,这个过程中同时标记该交点实体多边形对于切割多边形的进出性。

    开始执行时,先使用S1S5切割切割多边形C,会产生I6, I3两个交点,可以使用S1、I6、I3和S5这几个点x坐标的位置关系来作为顺序进行插入。这样依次用S中每条边切割C并插入链表,最终得到如下模型:

    图12

    下面的图可以更好的看出每个链表各自的情况(注意,交点相对不同的多边形进出性是相反的,这也是多边形同向的主要特征):

    图13

    这样完成切割以及交点插入后就可以进入阶段3了。

     

    阶段3

    在有了上面两个链表后,遍历实体多边形和裁剪多边形链表来来获得输出多边形链表。遍历过程由实体多边形对于裁剪多边形为进点的这样一个交点开始(需要used为0)。如上图第一个这样的交点为I6。

    从该进点到实体多边形链表中的下一个交点(一定为出点,对于图中这个点为I3)之间的所有实体多边形上的点全部作为结果多边形(下面的图中以红色箭头表示这样一个生成结果的过程,即沿着I6的NextS方向,对应图中实心三角箭头所指方向前进)。另外每遍历一个结点或交点就将其used置为1,下同。

    由于I3是实体多边形对于裁剪多边行的出点,所以下面的过程不能继续沿着实体多边形的边继续,需要转向裁剪多边形的方向(即沿着I3的Next2方向,对应图中三角箭头方向)继续找点,直到遇到下一个交点(这个交点必然是实体多边形对于裁剪多边形的进点)。(此处论文中提到由于I3的NextC方向是裁剪多边形相对于实体多边形的进点,所以沿着NextC方向继续,正是因为两个多边形同向,由于定理1,必然可以保证I3的NextC方向是裁剪多边形相对于实体多边形的进点,所以这就是两个多边形同向的重要性。)把这些点顺序加入输出多边形。

    重复这个过程(即遇到进点就沿NextS走,遇到出点就沿NextC走,另外注意,主要这个过程中遇到Vertex(不管是实体多边形的,还是裁剪多边形的),一定是沿着其Next走)直到遇到当前结果多边形起始的那个交点(对于这个例子即I6)。这样就输出了一个结果多边形。

    在上面处理结束后,如果实体多边形的链表中还有used为0的交点,说明还有其它的结果多边形。找到第一个used为0的进点,然后继续上文所述的过程,得到剩余的结果多边形。直到所有used为1结束。

    下图展示了连接点的过程:

    图14

    另一个版本:

    图15

    这样就可以得到结果了。

     

    本文参考论文所实现的算法支持一般多边形,包括但不限于凹多边形等,而且经过简单修改还可以求多边形的并或差,有一定的应用范围。在输出多边形的过程中当遇到进点(实体多边形相对于切割多边形)时沿着切割多边形的方向(即交点的NextC方向),而遇到出点(实体多边形相对于切割多边形)时沿着实体多边形的方向(即交点的NextS方向),即可得到多边形的"并"。

    要得到多边形的"差",只需使两个多边形开始阶段2时方向相反即可(即求交集需要多边形方向相同,求差集需要方向相反)。

    对于有孔洞的多边形的切割,论文中给出了一种思路,但是具体实现太复杂,这里就没有实现。有兴趣的童鞋自己去研究下吧。基本的原理就是把有空多边形的外侧边方向和切割多边形保持一致,内侧边和外侧边方向相反,这样在内侧边与切割多边形切割时,交点的进出性可以保持正确。

     

    由于本文使用的算法需要由交点起遍历多边形链表,所以要求切割多边形与实体多边形必须有实际交点(区别于虚焦点,即一个多边形边的延长线与另一个多边形的交点)。

    下面补充讨论下两个没有实际相交的多边形。

    首先看几组例子:

    图16

    在这种情况的处理下,仍可以处理凹多边形,将不被如下方案支持。上面几种情况,(a)切割后,结果多边形即为切割多边形。而(b)情况切割后结果即为实体多边形。对于(c),结果为空。

    经过前文使用实体多边形的边切切割多边行的过程后,如果交点个数为0,则说明出现了上图的情况。对于这三种情况的区分可以使用如下方法:

    取切割多边形中的一个点,如果位于实体多边形内则属于情况(a)

    取实体多边形中的一个点,如果位于切割多边形内则属于情况(b)

    如果以上两种情况都不成立则是情况(c)

    这种判断对如下这种嵌套,但同时存在边重合的情况也适用(需要在判断时,如果点在多边形的边上也算作在多边形内部。同时这也依赖于如果两个多边形边重合就认为它们没有交点这个假设):

    图17

    这里涉及到一个问题是,如果一个多边形嵌套另一个多边形,如何来判断嵌套。由于当一个多边形嵌套在另一个多边形中时,这个多边形其中的任一顶点也就在另一个多边形内部。所以可以把一个多边形是否包含另一个多边形的问题转为一个多边形是否包含一个点的问题。

    对于点是否在多边形中的问题,有一个经典方法可用于判断,由这个点向任意方向做一条射线(代码实现中是向右做水平射线,实现起来最简单),如果射线与多边形有奇数个交点,说明点在多边形内部,反之(包括没有交点)则说明点在多边形外部。具体可见代码实现部分。

     

     

    代码实现:

    采用原论文中描述的方法判断两个多变形是否同向和获取第一个交点应该同时完成,不过我实现写不出在通过一次切割即构成链表又能判断出进出性/多边形方向的代码,所以下面的实现中判断方向的切割与构成链表的切割相分离(即阶段1和阶段2把第一个交点计算了2次,第一次只是用于方向的判断)。 

     

    算法使用的数据结构

    这个算法中使用2个链表来分别表示切割多边形与实体多边形。

    其中结点/交点的数据结构:

    public abstract class VertexBase
    {
        public double X { get; set; }
        public double Y { get; set; }
    
        public string Name { get; set; }
    
        public void SetXY(double x, double y)
        {
            X = x;
            Y = y;
        }
    
        public Point ToPoint()
        {
            return new Point(X,Y);
        }
    }
    
    public class Vertex : VertexBase
    {
        [DebuggerNonUserCode]
        public Vertex(double x, double y)
        {
            X = x;
            Y = y;
        }
    
        public VertexBase Next { get; set; }
    }
    
    public class Intersection : VertexBase
    {
        [DebuggerNonUserCode]
        public Intersection(double x, double y)
        {
            X = x;
            Y = y;
        }
    
        public CrossInOut CrossDi { get; set; }
        public bool Used { get; set; }
        public VertexBase NextS { get; set; }
        public VertexBase NextC { get; set; }
    }

    Vertex中的Next用于表示下一个节点或交点的引用(可能是Vertex也可能是Intersection),Intersection中的NextS和NextC分别存储交点在S链表中和C链表中的下一个节点或交点的引用。Intersection中的Used记录输出结果的过程中该交点是否被输出,CrossDi表示该交点处S多边形相对于C多边形的进出性。

    解决方案中ArbitraryPolygonCut.cs文件包含了算法核心的代码(篇幅原因不列出代码了,后面有Github链接,自行下载查看吧),其中

    List<List<VertexBase>> Cut(List<VertexBase> listS, List<VertexBase> listC)

    是算法的主入口函数,里面的注释包含了几个阶段的标识,阶段一最主要的切割并判断方向的函数为:

    Tuple<CrossInOut, int, bool> CutByLineForCrossDi(VertexBase v1, VertexBase v2, List<VertexBase> list, bool withIdx, int line2Idx = 0)

    阶段二切割并链接节点的函数为:

    List<Intersection> CutByLine(Vertex s1, Vertex s2, LinkedList<VertexBase> linkC)

    上面2个切割函数还有2个Vertical结尾的函数,用于处理切线是垂直的情况。

     

    对于完全不相交的情况,使用

    List<VertexBase> ProcessNoCross(List<VertexBase> listS, List<VertexBase> listC)

    函数来处理,其中调用

    bool IsVertexInPolygon(VertexBase v, List<VertexBase> list)

    来进行点是否在多边形内的判断。

     

    代码附带一个测试程序,里面附带了部分保存好的测试图形(.cut结尾的文件),其包含了文档中涵盖的几种情况。也可以通过程序创建自己的图形来测试。

    最后放上一个图:

     

    代码下载:

    Github

     

    代码可以用于任意项目中,但本实现的测试不完善,用于生产场景请再次测试。如果用于出版的文档请标明来源。

    转载本文请保留链接

    展开全文
  • Cyrus-Beck图像裁剪算法归纳

    千次阅读 2010-10-11 00:38:00
    算法能使用任意多边形对一条直线段进行裁剪。 类GLdoublePoint: 公有—GLdouble x ,y;类line: 公有—GLdoublePoint first,second;linelist: line型数据组成的链表,用于描述多边形; 伪代码:int ...
  • 【寒江雪】凸多边形矩形裁切算法

    千次阅读 2016-11-17 00:14:33
    这次要干的事情是给定一个凸多边形的点描述和矩形的点描述,按着矩形来对多边形区域进行裁切。 大概如下图所示: 蓝色矩形是裁剪框,相当于Photoshop里的选区,红色多边形是图像,裁剪后在红色以外的部分...
  • 多边形的剪切

    2015-12-18 19:12:48
    绍的多边形剪裁算法是Sutherland和Hodgman提出的,本程序用c++描述多边形裁剪问题。运行是没有问题的。
  • 新版本增加了图形用户界面、椭圆、图像压缩和线条反走样算法等,还增加了Liang-Barsky裁剪算法和Nicholl-Lee- Nicholl裁剪算法。新版本大大扩充了可见面光线跟踪算法。在绘制这一章中新增了基于物理的光照明模型,...
  • 任务描述 设计方案 源程序 平面截图 心得体会 ............. 多边形的区域填充算法的...首先将多边形对于巨型窗口的裁剪分解为对窗口四边形所在直线的裁剪,其次,将多边形对一条直线的裁剪分解为各条边对直线的裁剪
  • 9.7多边形区域排序算法 9.8OpenGL中的消隐处理 第10章真实感图形绘制 10.1简单光照模型 10.1.1环境光 10.1.2漫反射光 10.1.3镜面反射光 10.1.4光强衰减 10.1.5颜色 10.2基于简单光照模型的...
  • 4.8.3 Cyrus-Beck裁剪算法 4.8.4 更高级的裁剪问题 本章小结 案例分析 进一步阅读 第5章 物体变换 5.1 概述 5.2 几何变换初步 52.1 点和物体变换 5.2.2 仿射变换 5.2.3 二维基本仿射变换的几何效果 5.2.4 仿射变换的...
  • 4.8.3 Cyrus-Beck裁剪算法 4.8.4 更高级的裁剪问题 本章小结 案例分析 进一步阅读 第5章 物体变换 5.1 概述 5.2 几何变换初步 52.1 点和物体变换 5.2.2 仿射变换 5.2.3 二维基本仿射变换的几何效果 5.2.4 仿射变换...
  • MAPGIS地质制图工具

    2013-05-06 16:15:30
    裁剪工具:裁剪指定范围的(工程)文件,且可以勾选裁剪完毕自动生成图框。 剪断相交线:选择线剪断相交线或者直接拉一条线剪断相交线,自相交及节点断线。 等分线:定距离或定段数等分一条线。还可以随机按偏移量自动...

空空如也

空空如也

1 2
收藏数 21
精华内容 8
关键字:

多边形裁剪算法描述