关键词: 多边形, 孔洞, 最小回路, 布尔运算

Abstract: A new algorithm is presented for Boolean operation of two polygons with holes based on
minimum 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 each
intersection point of P and Q are arranged in sequential order. Next, all minimum circles are found by
the minimum turning angle rule. These minimum circles are classified according to edges direction in P
and Q. Intersection, union, and difference of the two polygons correspond to different kinds of
minimum circles. The algorithm has explicit geometric significance, and well resolves the problems in
special cases.

Key words: polygon, hole, minimum circle, Boolean