一种求含孔洞多边形交、并、差集的新方法

提出了一种基于最小回路确定含孔洞多边形P 和Q 的交、并、差集的新方法。首先,初始化P 和Q 外环为逆时针方向,内环为顺时针方向,并通过连接内环极右顶点与其在外环上一可见点v,构造一条双向“桥边”,将内外多环转换为单环。其次,求出P 和Q 被转换为单环的边序列的交点,并对交点处的关联边进行排序。然后,沿着各个交点处正向边,依照最小转角原则搜索最小回路,并根据其中所含P 和Q 边所呈现的顺、逆时针方向进行分类。最后,P 和Q 的交、并、差集即对应不同类别的最小回路。算法简洁且几何意义明显,具有较好的适应性。

A New Method for Determining the Intersection,Union and Difference ofTwo Polygons with Holes

A new algorithm is presented for Boolean operation of two polygons with holes based onminimum circle. Firstly, outer rings of Polygon P and Q are initialized to counter-clockwise direction,and inner rings are initialized to clockwise direction. "Bridge edges" connect the outer and inner rings,so the polygon with multiple rings is converted to single ring. Then the edges connecting to eachintersection point of P and Q are arranged in sequential order. Next, all minimum circles are found bythe minimum turning angle rule. These minimum circles are classified according to edges direction in Pand Q. Intersection, union, and difference of the two polygons correspond to different kinds ofminimum circles. The algorithm has explicit geometric significance, and well resolves the problems inspecial cases.