文章插图
集合运算【集合运算】集合运算是数学科学中常用的词语 ， 是一种非常有效的构造形体的方法 ， 可以直观的减少运算难度 。
基本介绍中文名：集合运算
套用领域：数学科学
释义：一种非常有效的构造形体的方法
适用：正则集与正则集合运算运算元
概念集合运算是实体造型系统中非常重要的模组 ， 也是一种非常有效的构造形体的方法 。从一维几何元素到三维几何元素 ， 人们针对不同的情况和套用要求 ， 提出了不少集合运算算法 。在早期的造型系统中 ， 处理的对象是正则形体 ， 因此定义了正则形体集合运算 ， 来保证正则形体在集合运算下是封闭的 。在非正则形体造型中 ， 参与集合运算的形体可以是体、面、边、点 ， 运算的结果也是这些形体 ， 这就要求集合运算算法中能统一处理这些不同维数的形体 ， 因此需要引入非正则形体运算 。1、正则集与正则集合运算运算元Tilove根据点集拓扑学的原理 ， 给出了正则集的定义 。认为正则的几何形体是由其内部点的闭包构成 ， 即由内部点和边界两部分组成 。对于几何造型中的形体 ， 规定正则形体是三维欧氏空间中的正则集合 ， 因此可以将正则几何形体描述如下：主要类型设G是三维欧氏空间R3中的一个有界区域 ， 且G=bG∪iG ， 其中bG是G的n－1维边界 ， iG是G的内部 。G的补空间cG称为G的外部 ， 此时正则形体G需满足：1)bG将iG和cG分为两个互不连通的子空间；2)bG中的任意一点可以使iG和bG连通；3)bG中任一点存在切平面 ， 其法矢指向cG子空间4)bG是二维流形 。对于正则形体集合 ， 可以定义正则集合运算元 。设是集合运算运算元（交、并或差） ， 如果R3中任意两个正则形体A、B作集合运算：R=AB运算结果R仍是R3中的正则形体 ， 则称为正则集合运算元 ， 正则并、正则交、正则差分别记为∪* ， ∩*、-* 。分类几何造型中的集合运算实质上是对集合中的成员进行分类的问题 ， Tilove给出了集合成员分类问题的定义及判定方法 。Tilove对分类问题的定义为：设S为待分类元素组成的集合 ， G为一正则集合 ， 则S相对于G的成员分类函式为：C(S,G)={S in G ， S out G ， S on G} ， （3-2-1）其中 ， S in G=S∩iG ， S out G=S∩cG ， S on G=S∩bG ， 如果S是形体的表面 ， G是一正则形体 ， 则定义S相对于G的分类函式时 ， 需考虑S的法向量 。记-S为S的反向面 。形体表面S上一点P相对于外侧的法向量为NP(S) ， 相反方向的法向量为- NP(S) ， 则（3-2-1）式中S on G可分为两种情况：S on G ={S shared(bG) ， S shared(-bG)} ， 其中 ， S shared(bG)={P|P∈S ， P∈bG ， NP(S)=NP(bG)},S shared(-bG)={P|P∈S ， P∈bG ， NP(S)=-NP(bG)} 。于是 ， S相对于G的分类函式C(S,G)可写为：C(S,G)={S in G ， S out G ， S shared(bG) ， S shared(-bG)} 。由此 ， 正则集合运算定义的形体边界可表达为：b(A∪B)={bA out B ， bB out A ， bA shared(bB)} ， b(A∩B)={bA in B ， bB in A ， bA shared(bB)} ， b(A-B)={bA out B ， -(bB in A) ， bA shared(-bB)} 。3．集合运算算法正则集合运算与非正则形体运算的区别在于增加了正则化处理步骤 。下面 ， 我们给出一个非正则形体的集合运算算法 。假定参与集合运算的形体为A和B ， 运算的结果形体C=AB ， 其中集合运算符为通常的集合运算并、交、差（è 、? 、- ） 。对于一个非正则形体L ， 可以将其分解为L=L3èL2èL1èL0 ， 其中L3为R3中的正则闭集之并 ， 存在面表、边表、点表等拓扑元素 。L2是悬面集 ， 存在边表和点表 。L1是悬边集 ， 只有端点 。L0是孤立点集 。集合运算整个算法包括了以下几部分：(1)求交：参与运算的一个形体的各拓扑元素求交 ， 求交的顺序採用低维元素向高维元素进行 。用求交结果产生的新元素（维数低于参与求交的元素）对求交元素进行划分 ， 形成一些子元素 。这种经过求交步骤之后 ， 每一形体产生的子拓扑元素的整体相对于另一形体有外部、内部、边界上的分类关係 。2)成环：由求交得到的交线将原形体的面进行分割 ， 形成一些新的面环 。再加上原形体的悬边、悬点经求交后得到的各子拓扑元素 ， 形成一拓扑元素生成集 。(3)分类：对形成的拓扑元素生成集中的每一拓扑元素 ， 取其上的一个代表点 ， 根据点/体分类的原则 ， 决定该点相对于另一形体的位置关係 ， 同时考虑该点代表的拓扑元素的类型（即其维数） ， 来决定该拓扑元素相对于另一形体的分类关係 。(4)取捨：根据拓扑元素的类型及其相对另一形体的分类关係 ， 按照集合运算的运算符要求 ， 要决定拓扑元素是保留还是捨去；保留的拓扑元素形成一个保留集 。(5)合併：对保留集中同类型可合併的拓扑元素进行合併 ， 包括面环的合併和边的合併 。(6)拼接：以拓扑元素的共享边界作为其连线标誌 ， 按照从高维到低维的顺序 ， 收集分类后保留的拓扑元素 ， 形成结果形体的边界表示数据结构 。集合的运算并主条目：并集两个集合可以相"加" 。A和B的并集是将A和B的元素放到一起构成的新集合 。定义给定集合A ， B ， 定义运算∪如下：A∪B = {e|e∈A 或 e∈B} 。A∪B称为A和B的并集 。A 和 B 的并集示例