复杂多边形窗口的多边形裁剪的改进算法  

An Improved Algorithm for Polygon Clipping in Complex Polygon Window

作　　者：刘雪娜[1] 侯宝明[1] 

机构地区：[1]渤海大学信息科学与工程学院,辽宁锦州121000

出　　处：《计算机与现代化》2009年第11期36-38,42,共4页Computer and Modernization

摘　　要：多边形裁剪是计算机图形学中较为热点研究的问题,针对复杂多边形窗口的复杂多边形裁剪提出一个可靠有效算法。算法通过添加虚边来消去孔洞,并且为恢复裁剪结果的原貌改进了遍历方法。新的遍历算法只需遍历多边形一次就可巧妙地求得所有裁剪结果,并恢复带孔洞的裁剪结果的内外边界的拓扑结构,无需解环、并环,也不用对裁剪边界重新组合。Polygon clipping is a very hot research issue in computer graphics. An efficient and reliable algorithm for complex poly- gon clipping in a complex polygon window is proposed. Virtual edges are added to eliminate holes, and traversal method is improved to restore the original appearance of the clipping results. In the new traversal algorithm, after the two polygons are trav- ersed only one time, it is very clever to get all the clipping results and restore the topology between the outside border and the holes of the every clipping result with holes. Neither untie and unite ring, nor recombination of clipping borders is used.

关 键 词：裁剪 多边形 孔洞 计算机图形学 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]