用最小回路求两个简单多边形的交、并、差集

Resolving intersection,union and difference of two simple polygons based on minimum circle

针对求两个简单多边形交、并、差集问题,提出一种基于最小回路的新算法。首先,将初始多边形P和Q初始化为逆时针方向,并将两个多边形交点处的关联边排序。然后,从各个交点出发利用最小转角法搜索最小回路,并根据这些最小回路中包含P和Q边的方向性对它们进行分类。最终,不同类别的最小回路将对应P和Q的交、并、差集。算法的时间复杂度为O((n+m+k)logd),其中n、m分别是P和Q的顶点数,k是两多边形的交点数,d为将多边形分割的单调链数。算法几何意义明显,对于多边形布尔运算中的重合顶点、重合边等奇异情形,具有较好的适应性。

A new algorithm for Boolean operation of two simple polygons based on minimum circle was presented.Polygon P and Q were initialized to counter-clockwise direction,and the edges connecting to each intersection point of P and Q were arranged in sequential order.Then,all minimum circles were found using the minimum turning angle rule.These minimum circles were classified according to edges direction in P and Q.Intersection,union,and difference of the two polygons are corresponding to different kinds of minimum circles.The algorithm run in time O（（n＋m＋k）log d） in a worst presented case,where n and m were the vertex numbers of the two polygons respectively,k was the numbers of intersection points,and d was the number of polygon＇s monotonic chain.The algorithm has explicit geometric significance,and well resolves the problems in special cases,such as overlapped edges,and operation edges intersection at the vertex of edges.