【摘要】 为了尽量降低任意多边形裁剪复杂度,提出了一种基于多边形顶点遍历的简单多边形裁剪算法。该算法将多边形交点插入到裁剪多边形和被裁减多边形顶点矢量数组中,通过记录交点及其前驱、后继信息,可快速生成结果多边形。其中,时间复杂度为O((m+k)×k),m是两多边形中顶点数较大者,k是两多边形的交点数。该算法简化了交点的数据结构,节省了存储空间,降低了算法的时间复杂度,具有简单、易于编程实现、运行效率高的特点。更多还原

【Abstract】 To decrease the difficulty for polygon clipping,an algorithm for simple polygon clipping based on traversing polygon’s vertices is proposed.The algorithm inserts intersection points into the vertexes’ vector of clipping and clips polygon.By recording intersection points and its predecessor and successor,it may generate results polygon quickly.The algorithm optimizes the data structure of intersection point,saves storage space,and reduces the time complexity that is O((m+k)×k)where m is the larger vertex number of two polygons,and k is the number of intersection points.The algorithm is simple,easy to implement and high efficiency.更多还原