文档介绍：图形的集合运算
赵立强
图形的集合运算
二维图形的集合运算是两个实面积多边形经过“交”、“并”、“差”运算之后,生成新的实面积多边形,且新图形仍能保持与原图形相同的维数(具有这一特点的集合运算又称布尔运算)。
一般集合运算公式不能保证这一要求得到满足,它可能会使新图形不能封闭或产生悬边等情况,见图。只有正则多边形在正则集合运算条件下,生成的新多边形才能保证上述要求得到满足。
正则多边形要求多边形是封闭的且无悬边、悬点等非法状况。下面分别介绍正则集合运算的基本原理与实现方法。
一、正则集合运算公式
若用bA,iA分别表示A图形的边界子集(多边形的各有向边线)与内部子集(实面积范围),则A,B两图形经“交”、“并”、“差”运算生成新图形C的结果可用正则集合运算公式表述如下。
=A∩B
则 iC=(iA in iB)
bC=(bA in iB) ∪(bB in iA) ∪ share(bA on bB) (3—11)
A图形的内部区域位于B图形的内部区域之内时,为新图形C的有效内部区域;
A图形的边界位于B图形的内部区域之内,或B图形的边界位于A图形的内部区域之内,或A图形的边界与月图形的边界重叠且方向相同,这三种边界为新图形C的有效边界。
=A∪B
=A∪B
则 iC=(iA out iB)∪(iB out iA)∪(iA in iB)
bC=(bA out iB)∪(bB out iA) ∪ share(bA on bB) (3—12)
A图形的内部区域位于B图形的内部区域之外,或B图形的内部区域位于A图形的内部区域之外,或A图形的内部区域位于B图形的内部区域之内,这三种区域为新图形C的有效内部区域;
A图形的边界位于B图形的内部区域之外,或B图形的边界位于A图形的内部区域之外,或A图形的边界与B图形的边界重叠且方向相同,这三种边界为新图形C的有效边界。
=A-B
=A-B=A∩B (二维图形的集合运算常用此表达式)
则 iC =(iA in iB)=(iA out iB)
bC = ( bA in iB ) ∪( bB in iA ) ∪ share( bA on bB )
= ( bA out iB ) ∪( bB in iA ) ∪ antishare( bA on bB )
A图形的内部区域位于B图形的内部区域之外为新图形C的有效内部区域;
A图形的边界位于B图形的内部区域之外,或B图形的边界位于A图形的内部区域之内(这里B要求把B图形的各边界反向),或与B图形的边界重叠且方向相反的A图形的边界,这三种边界为新图形C的有效边界。
正则集合运算示例
下面举例说明这组公式的应用,见图,原A,B多边形的边界经过求交分段之后,分别为:
(bA in iB)={18}
(bB in iA)={13,15}
(bA out iB)={10,1,2,3,5,6,7}
(bB out iA)={16,11}
share(bA on bB)={4}={14}
antishare(bA on bB)={9}={12}
(bB in iA)={13,15}
对于C=A ∩ B
bC = ( bA in iB ) ∪( bB in iA ) ∪ share( bA on bB ) = {8,13,15,4}
利用边线的顶点相邻性,不难组成新多边形的环。
bA = {1,2,3,4,5,6,7,8,9,10}
bB= {11,12,13,14,15,I6}
对于:C=A ∪B
bC=( bA out iB)∪(bB out iA)∪share(bA on bB)
= {10,1,2,3,5,6,7,16,11,4}
同理利用边线的顶点相邻性,可构成新多边形的环。
对于:C=A-B
bC=(bA out iB)U(bB in iA) ∪ antishare(bA On bB)
={10,1,2,3,5,6,7,9,13,15}
同理上述数据可构成两个并列的环。
这组公式说明,对边界表示法(即多边形)所描述的实面积图形(或用有界表面描述的物体),只要收集满足以上条件的各边界就可构成所求的、包围新图形C的封闭边界。因“差”运算可转换成“交”运算来实现,故对于二维图形的集合运算以下只讨论“交”、“并”运算的实现方法。
二、集合元素关系分类
这里A,B两图形的环、边线、点等图形元素是参加集合运算的基本单位——集合元素,它们之间的分离、相交、包含、重叠、相切等相互关系与图形C的新环有何联系,是集合元素关系分类要讨论的基本问题。

判断一个点P是否位于另一个多边形之内,通常用过该点的射线与此多边形相交的奇偶次数来确