一种基于交点排序的高效多边形裁剪算法  

An efficient algorithm for polygon clipping based on intersection points sorting

作　　者：彭杰[1,2] 刘南[1] 唐远彬[1,2] 杜震洪[1,2] 刘仁义[2] 

机构地区：[1]浙江大学浙江省资源与环境重点实验室,浙江杭州310028 [2]浙江大学地理信息科学研究所,浙江杭州310028

出　　处：《浙江大学学报（理学版）》2012年第1期107-111,122,共6页Journal of Zhejiang University（Science Edition）

基　　金：国家863项目(2009AA12Z222;2007AA12Z182);浙江省攻关项目(2009C33011);教育部博士点基金项目(200803350017);浙江省自然科学基金资助项目(Y5090130)

摘　　要：提出了一种适合任意多边形裁剪的算法,该算法将构成结果多边形的裁剪多边形和实体多边形顶点插入到两者的交点链表中,通过交点位置的排序,形成一个单线性、单指针结构的结果多边形顶点链表.简化了交点的数据结构,减少了裁剪多边形与实体多边形边界的循环求交次数.最后,通过与其他同类算法进行比较,验证了算法运行的效率优势.An efficient algorithm for polygon clipping is proposed.The algorithm inserts the vertexes of clipping and clips polygon which are made up of the result polygon into the intersection points list.By sorting the intersection points,we will get a directional linked and single-pointer vertexes list of result polygons.This algorithm optimizes the data structure of intersection points and reduces the calculation times.Finally,by compared with other congener algorithms,the new algorithm is verified to be more efficient.

关 键 词：多边形裁剪 交点计算 交点排序 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]