集合運(yùn)算（數(shù)學(xué)科學(xué)中的專業(yè)詞匯）

概念

集合運(yùn)算是實(shí)體造型系統(tǒng)中非常重要的模塊，也是一種非常有效的構(gòu)造形體的方法。從一維幾何元素到三維幾何元素，人們針對(duì)不同的情況和應(yīng)用要求，提出了不少集合運(yùn)算算法。

在早期的造型系統(tǒng)中，處理的對(duì)象是正則形體，因此定義了正則形體集合運(yùn)算，來(lái)保證正則形體在集合運(yùn)算下是封閉的。在非正則形體造型中，參與集合運(yùn)算的形體可以是體、面、邊、點(diǎn)，運(yùn)算的結(jié)果也是這些形體，這就要求集合運(yùn)算算法中能統(tǒng)一處理這些不同維數(shù)的形體，因此需要引入非正則形體運(yùn)算。

1、正則集與正則集合運(yùn)算算子

Tilove根據(jù)點(diǎn)集拓?fù)鋵W(xué)的原理，給出了正則集的定義。認(rèn)為正則的幾何形體是由其內(nèi)部點(diǎn)的閉包構(gòu)成，即由內(nèi)部點(diǎn)和邊界兩部分組成。對(duì)于幾何造型中的形體，規(guī)定正則形體是三維歐氏空間中的正則集合，因此可以將正則幾何形體描述如下：

主要類型

設(shè)G是三維歐氏空間R3中的一個(gè)有界區(qū)域，且G=bG∪iG，其中bG是G的n－1維邊界，iG是G的內(nèi)部。G的補(bǔ)空間cG稱為G的外部，此時(shí)正則形體G需滿足：

1)bG將iG和cG分為兩個(gè)互不連通的子空間；

2)bG中的任意一點(diǎn)可以使iG和bG連通；

3)bG中任一點(diǎn)存在切平面，其法矢指向cG子空間

4)bG是二維流形。

對(duì)于正則形體集合，可以定義正則集合算子。設(shè)是集合運(yùn)算算子（交、并或差），如果R3中任意兩個(gè)正則形體A、B作集合運(yùn)算：

R=AB

運(yùn)算結(jié)果R仍是R3中的正則形體，則稱為正則集合算子，正則并、正則交、正則差分別記為∪*，∩*、-*。

分類

幾何造型中的集合運(yùn)算實(shí)質(zhì)上是對(duì)集合中的成員進(jìn)行分類的問(wèn)題，Tilove給出了集合成員分類問(wèn)題的定義及判定方法。

Tilove對(duì)分類問(wèn)題的定義為：設(shè)S為待分類元素組成的集合，G為一正則集合，則S相對(duì)于G的成員分類函數(shù)為：

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相對(duì)于G的分類函數(shù)時(shí)，需考慮S的法向量。記-S為S的反向面。形體表面S上一點(diǎn)P相對(duì)于外側(cè)的法向量為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相對(duì)于G的分類函數(shù)C(S,G)可寫為：

C(S,G)={S in G，S out G，S shared(bG)，S shared(-bG)}。

由此，正則集合運(yùn)算定義的形體邊界可表達(dá)為：

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．集合運(yùn)算算法

正則集合運(yùn)算與非正則形體運(yùn)算的區(qū)別在于增加了正則化處理步驟。下面，我們給出一個(gè)非正則形體的集合運(yùn)算算法。

假定參與集合運(yùn)算的形體為A和B，運(yùn)算的結(jié)果形體C=AB，其中集合運(yùn)算符為通常的集合運(yùn)算并、交、差（è 、? 、- ）。

對(duì)于一個(gè)非正則形體L，可以將其分解為L(zhǎng)=L3èL2èL1èL0，其中L3為R3中的正則閉集之并，存在面表、邊表、點(diǎn)表等拓?fù)湓亍2是懸面集，存在邊表和點(diǎn)表。L1是懸邊集，只有端點(diǎn)。L0是孤立點(diǎn)集。

集合運(yùn)算整個(gè)算法包括了以下幾部分：

(1)求交：參與運(yùn)算的一個(gè)形體的各拓?fù)湓厍蠼?，求交的順序采用低維元素向高維元素進(jìn)行。用求交結(jié)果產(chǎn)生的新元素（維數(shù)低于參與求交的元素）對(duì)求交元素進(jìn)行劃分，形成一些子元素。這種經(jīng)過(guò)求交步驟之后，每一形體產(chǎn)生的子拓?fù)湓氐恼w相對(duì)于另一形體有外部、內(nèi)部、邊界上的分類關(guān)系。

2)成環(huán)：由求交得到的交線將原形體的面進(jìn)行分割，形成一些新的面環(huán)。再加上原形體的懸邊、懸點(diǎn)經(jīng)求交后得到的各子拓?fù)湓?，形成一拓?fù)湓厣杉?/p>

(3)分類：對(duì)形成的拓?fù)湓厣?a class="dict" href="/azsoft/k2748790.html">集中的每一拓?fù)湓?，取其上的一個(gè)代表點(diǎn)，根據(jù)點(diǎn)/體分類的原則，決定該點(diǎn)相對(duì)于另一形體的位置關(guān)系，同時(shí)考慮該點(diǎn)代表的拓?fù)湓氐念愋停雌渚S數(shù)），來(lái)決定該拓?fù)湓叵鄬?duì)于另一形體的分類關(guān)系。

(4)取舍：根據(jù)拓?fù)湓氐念愋图捌湎鄬?duì)另一形體的分類關(guān)系，按照集合運(yùn)算的運(yùn)算符要求，要決定拓?fù)湓厥潜Ａ暨€是舍去；保留的拓?fù)湓匦纬梢粋€(gè)保留集。

(5)合并：對(duì)保留集中同類型可合并的拓?fù)湓剡M(jìn)行合并，包括面環(huán)的合并和邊的合并。

(6)拼接：以拓?fù)湓氐墓蚕磉吔缱鳛槠溥B接標(biāo)志，按照從高維到低維的順序，收集分類后保留的拓?fù)湓?，形成結(jié)果形體的邊界表示數(shù)據(jù)結(jié)構(gòu)。

集合的運(yùn)算

主條目：并集

兩個(gè)集合可以相"加"。A和B的

并集

定義

給定集合A，B，定義運(yùn)算∪如下：

并集

示例

• {1, 2}∪{紅色, 白色} = {1, 2, 紅色, 白色}{1, 2, 綠色}∪{紅色, 白色, 綠色} = {1, 2, 紅色, 白色, 綠色}{1, 2}∪{1, 2} = {1, 2}

基本性質(zhì)

作為集合間的二元運(yùn)算，∪運(yùn)算具有以下性質(zhì)。

交換律：

結(jié)合律：

冪等

律

幺元

主條目：交集

一個(gè)新的集合也可以通過(guò)兩個(gè)集合"共"有的元素來(lái)構(gòu)造。A和B的

交集

若

不相交

定義

給定集合A，B，定義運(yùn)算∩如下：

交集

交集

基本性質(zhì)

作為集合間的二元運(yùn)算，∩運(yùn)算具有以下性質(zhì)。

• 交換律

  ：

  

• 結(jié)合律

  ：

  

• 冪等律

  ：

  

空集合

其它性質(zhì)還有：

示例

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

{1, 2, 綠色}∩{紅色, 白色, 綠色} = {綠色}

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

主條目：差集

兩個(gè)集合也可以相"減"。A在B中的相對(duì)補(bǔ)集，寫作B?A，是屬于B的、但不屬于A的所有元素組成的集合。

在特定情況下，所討論的所有集合是一個(gè)給定的全集U的子集。這樣，U?A稱作A的絕對(duì)補(bǔ)集，或簡(jiǎn)稱補(bǔ)集（余集），寫作A′或CUA。

補(bǔ)集可以看作兩個(gè)集合相減，有時(shí)也稱作

差集

定義

給定集合A，B，定義運(yùn)算-如下：

差集

相對(duì)補(bǔ)集

在上下文確定了

全集

補(bǔ)集

余集

基本性質(zhì)

作為集合間的二元運(yùn)算，- 運(yùn)算有如下基本性質(zhì)：

右幺元

左零元

示例

{1, 2}?{紅色, 白色} = {1, 2}

{1, 2, 綠色}?{紅色, 白色, 綠色} = {1, 2}

{1, 2}?{1, 2} =

若U是整數(shù)集，則奇數(shù)的補(bǔ)集是偶數(shù)

主條目：對(duì)稱差

定義

給定集合A，B，定義

對(duì)稱差

作為集合間的二元運(yùn)算，△運(yùn)算具有如下基本性質(zhì)：

交換律

結(jié)合律

幺元

逆元