概念播报编辑实体造型系统中的正则与非正则形体集合运算算法详解

概念播报

编辑

集合运算在实体造型系统中是很重要的模块，并且是构造形体的一种有效方法。从一维的几何元素到三维的几何元素，人们依据不同的情况和应用需求，提出了许多集合运算算法。

早期的造型系统处理的对象为正则形体，所以定义了正则形体集合运算，以确保正则形体在集合运算下是封闭的。在非正则形体造型中，参与集合运算的形体可以是体、面、边、点，运算结果也是这些形体。这就需要集合运算算法能够统一处理这些不同维数的形体，故而需要引入非正则形体运算。

1、正则集与正则集合运算算子

Tilove依据点集拓扑学的原理，给出了正则集的定义。其认为正则的几何形体是由内部点的闭包所构成，也就是由内部点以及边界这两部分共同组成。对于几何造型里的形体，规定正则形体是三维欧氏空间中的正则集合，所以能够将正则几何形体描述为：

主要类型播报

编辑

三维欧氏空间 R3 中存在一个有界区域 G，G 由两部分组成，即 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 中的正则形体，那么就将其称为正则集合算子。其中，正则并记为∪*，正则交记为∩*，正则差记为-* [1]。

分类播报

编辑

几何造型中的集合运算本质上是关于对集合中的成员进行分类的事情。Tilove给出了集合成员分类问题的定义以及判定的方法。

Tilove 对分类问题的定义是这样的：存在一个集合 S，它是由待分类的元素所组成的；还有一个集合 G，它是一个正则集合。那么，S 相对于 G 的成员分类函数就是：

C(S,G)包含三种情况，一是 S 在 G 中，即 S in G；二是 S 不在 G 中，即 S out G；三是 S 在 G 上，即 S on G。

其中，

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 共享的（bG）等于这样的 P 的集合，即 P 属于 S 且 P 属于 bG 并且 S 的 NP 等于 bG 的 NP 。

S 共享的集合(-bG)等于这样的 P 的集合，P 属于 S 且 P 属于 bG 且 S 的否定范式(NP)等于 bG 的否定范式的否定(-NP(bG))。

于是，S相对于G的分类函数C(S,G)可写为：

C(S,G)包含以下几种情况：S 在 G 中；S 不在 G 中；S 与 bG 共享；S 与 -bG 共享。

由此，正则集合运算定义的形体边界可表达为：

b 与 A 并 B 的结果为{bA 除去 B，bB 除去 A，bA 与(bB)的交集}

b 与 A 和 B 的交集等于{bA 属于 B，bB 属于 A，bA 与 bB 有共享部分}

b(A - B)包含 bA 不属于 B，bB 属于 A 的否定，以及 bA 与 -bB 的共享部分。

3．集合运算算法

正则集合运算与非正则形体运算存在区别，区别在于增加了正则化处理步骤。接下来，我们给出一个关于非正则形体的集合运算算法。

假定参与集合运算的形体分别是 A 和 B，运算后得到的结果形体是 C，且 C 等于 A 与 B 的某种运算结果，这里的集合运算符是通常的集合运算并（È ）、交（Ç ）、差（- ）。

一个非正则形体 L 可以这样分解，即 L 等于 L3 并上 L2 并上 L1 并上 L0。其中，L3 是 R3 中的正则闭集的并集，并且有面表、边表、点表等拓扑元素。L2 是悬面集，有边表和点表。L1 是悬边集，仅包含端点。L0 是孤立点集。

集合运算整个算法包括了以下几部分：

参与运算的一个形体的各拓扑元素进行求交，求交顺序是低维元素向高维元素进行。通过求交结果产生新元素（维数低于参与求交的元素），用这些新元素对求交元素进行划分，从而形成一些子元素。在经过求交步骤之后，每一形体所产生的子拓扑元素的整体，与另一形体之间存在外部、内部、边界上的分类关系。

成环过程如下：通过求交得到的交线会把原形体的面进行分割，从而形成一些新的面环。同时，原形体的悬边以及悬点经过求交之后所得到的各个子拓扑元素，也会一起构成一个拓扑元素生成集。

分类：对于形成的拓扑元素生成集中的每一个拓扑元素，选取其上的一个代表点。依据点/体分类的原则，确定该点相对于另一形体的位置关系。同时，考虑该点所代表的拓扑元素的类型，也就是其维数，以此来决定该拓扑元素相对于另一形体的分类关系。

取舍：依据拓扑元素的类型以及它相对于另一形体的分类关系，按照集合运算的运算符的要求，需决定拓扑元素是被保留还是被舍去；被保留的拓扑元素会构成一个保留集。

对保留集中同类型且可合并的拓扑元素进行合并操作，其中包括对面环的合并以及对边的合并。

拼接时，将拓扑元素的共享边界当作其连接标志，接着按照从高维到低维的顺序，把分类后保留的拓扑元素收集起来，从而形成结果形体的边界表示数据结构[2]。

集合的运算播报

编辑

并

主条目：并集

两个集合能够进行“相加”操作。A 的元素与 B 的元素组合在一起，就形成了 A 和 B 的并集，这个并集是一个新的集合。

定义

定义集合 A 和 B 后，定义运算∪的方式如下：A∪B 这个集合包含所有属于 A 或者属于 B 的元素 e。A∪B 被称作 A 和 B 的并集。

A 和 B 的并集

示例

基本性质

作为集合间的二元运算，∪运算具有以下性质。

交换律：A∪B = B∪A；

结合律：(A∪B)∪C = A∪(B∪C)；

幂等律：A∪A = A；

幺元：∀集合A，A∪

= A；（

是∪运算的幺元）。

交

主条目：交集

一个新的集合能够依据两个集合所“共同”拥有的元素进行构造。A 与 B 的交集，记作 A∩B，它是由既属于 A 又属于 B 的所有元素所构成的集合。

如果 A 与 B 的交集为{\displaystyle \varnothing }，那么就称 A 和 B 是不相交的。

A 和 B 的交集

定义

定义运算∩，对于给定的集合 A 和 B，A∩B 是这样一个集合：其中的元素 e 满足 e 既属于集合 A 又属于集合 B。也就是说，A∩B = {e|e∈A 且 e∈B}，A∩B 被称为 A 和 B 的交集。

基本性质

作为集合间的二元运算，∩运算具有以下性质。

空集合：∀集合A，A∩

；（

是∩运算的空集合）。

其它性质还有：

示例

{1, 2}∩{红色, 白色} =

{绿色}与{红色, 白色, 绿色}的交集为{绿色}；{1, 2, 绿色}与{红色, 白色, 绿色}的交集是{绿色}

{1, 2}∩{1, 2} = {1, 2}

差

主条目：差集

两个集合能够进行“相减”的操作。A 在 B 中的相对补集，用 B−A 来表示，它是由属于 B 且不属于 A 的所有元素所组成的集合。

在特定情形下，所谈及的所有集合是一个既定的全集 U 的部分。在此情况下，U 减去 A 被称作 A 的绝对补集，或者简称为补集（余集），其记作 A′或者 CUA。

补集可以看作两个集合相减，有时也称作差集。

定义

给定集合 A 以及集合 B，定义了这样一种运算 - ：A 减去 B 所得到的集合是{e|e 属于 A 并且 e 不属于 B}。

。A - B称为B对于A的差集，相对补集或相对余集。

当上下文明确了全集 U 之后，对于 U 的某一个子集 A 而言，通常把 U 减去 A 所得到的集合称作 A（相对于 U）的补集或者余集，一般记为 A′或者

，也有记为CUA的。

基本性质

作为集合间的二元运算，- 运算有如下基本性质：

A - A =

；

右幺元：∀集合A，A -

= A；（

是 - 运算的右幺元）。

左零元：∀集合A，

- A =

；（

是 - 运算的左零元）。

示例

{1, 2}−{红色, 白色} = {1, 2}

{1, 2, 绿色}这个集合减去{红色, 白色, 绿色}这个集合，结果等于{1, 2}。

{1, 2}−{1, 2} =

若U是整数集，则奇数的补集是偶数

对称差

主条目：对称差

定义

给定集合 A 和集合 B，对于对称差运算进行如下定义：A 与 B 的对称差 AB 等于 A 减去 B 的结果与 B 减去 A 的结果的并集。

基本性质

作为集合间的二元运算，运算具有如下基本性质：

交换律：AB = BA；

结合律：(AB)C = A(BC)；

幺元：∀集合A，A

= A；（

是运算的幺元）。

逆元：AA =

；