平面简单多边形的布尔运算.pdf

计算几何大实验 平面简单多边形的布尔运算 计研12 董未名（014894 ）、张松海（014888 ） 【问题背景】 平面多边形的布尔运算是几何和实体造型中的几个基本问题之一。当前有许多方法可以 计算多边形的交，但是大部分算法都没有一个正规的数学模型，以至于绝大多数只能对凸多 边形进行操作，而很少有比较好的方法可以对凹多边形进行计算。然而，在实际的应用中， 特别是在计算机图形学领域，任意多边形的交、并、差的运算是很重要的。例如，在进行平 面消隐的操作时，它的基础就是二维平面多边形的布尔运算。因此，设计一个稳定而有效的 多边形布尔运算的算法是必要的。在本次实验中，我们采用一种比较新颖的方法来对任意平 面多边形（有洞和无洞）进行布尔运算的操作，算法以一种对几何模型进行数学形式化的算 法为基础，可以避免去考虑布尔运算中各种各样繁琐的特殊情况，从而使系统有着较高的效 率和较强的鲁棒性。 【算法及原理】 这里只对二维的情况进行说明，对于三维或者更高维的情况是一样的。 (1) 多边形表示 设P 为一简单多边形，它的n 条边e1，e2…en 逆序排列，P 可以用如下的三角形链 n 表示： ，其中 ， 为原点与边ei 组成的三角形。 P P , where   S  {1,1} S  i i i i i 0 这里要说明一点：多边形所有定点必须落在第一象限。我们定义： f  : R d Z ,f  (Q) QSi i 。对于P 内部任意一点Q，有f  (Q) 1，对于多边 形外部一点 ，有f (Q ) 0 。 Q  (2) 多边形求交 共7 页 第1 页 计算几何大实验 n m 设 P1 ，P2 为简单多边形，  S ， b S 为对应的三角形链，则 1 i i 2 j j i 0 j 0 n m P P 对应的三角形链为  b Tri(S U ) ，其中Tri(S U ) 为 1 2 P P i j i j i j 1 2