趙 辰， 林 強(qiáng)， 吳 娟， 羅秋科

（中國(guó)物品編碼中心，北京 100029）

幾何約束求解技術(shù)是基于約束滿足的參數(shù)化設(shè)計(jì)方法中的核心技術(shù)，幾何約束求解是指在用戶輸入一個(gè)草圖以后，用戶還可以隨時(shí)在需要的時(shí)候，以任意方式、順序重新輸入幾何約束，然后由計(jì)算機(jī)自動(dòng)導(dǎo)出精確的滿足用戶要求的幾何圖形的一種基于約束的參數(shù)化設(shè)計(jì)方法，工程設(shè)計(jì)領(lǐng)域中許多問(wèn)題都可歸結(jié)為幾何約束滿足問(wèn)題。幾何約束求解技術(shù)可應(yīng)用于許多領(lǐng)域，如：參數(shù)化繪圖設(shè)計(jì)，化學(xué)分子建模，平面與空間連桿設(shè)計(jì)，裝配設(shè)計(jì)，計(jì)算機(jī)視覺(jué)，計(jì)算機(jī)輔助教學(xué)等等，它對(duì)應(yīng)的幾何求解方法主要有四種：數(shù)值計(jì)算方法[1-2]、符號(hào)計(jì)算方法[3-4]、基于規(guī)則的方法[5-6]和基于圖論的方法[7-8]。這四種方法各有自己的優(yōu)勢(shì)和局限性，實(shí)際的幾何約束問(wèn)題求解系統(tǒng)一般都是混合這幾種算法，以求達(dá)到最佳效果。

文獻(xiàn)[9]提出了幾何約束求解的一種方法 ――AGDG 算法，該方法對(duì)幾何圖形的處理分為以下4 步：① 對(duì)幾何問(wèn)題使用約束圖表示，使用LIM0 進(jìn)行求解；② 對(duì)于LIM0 不能夠完全求解的幾何問(wèn)題，使用Owen 和Hoffmann 的三角分解算法[10-11]進(jìn)行處理；③ 如果仍然不能完全求解，使用幾何變換方法處理；④ 對(duì)于前面不能完全求解問(wèn)題，采用數(shù)值方法進(jìn)行求解。AGDG 方法的前3 個(gè)步驟能夠進(jìn)行處理的幾何約束問(wèn)題和部分C－Tree 算法能夠求解的幾何約束問(wèn)題都可以通過(guò)尺規(guī)作圖進(jìn)行求解。文獻(xiàn)[12]提出了C－Tree 算法，作為對(duì)AGDG 方法的補(bǔ)充。

對(duì)于幾何約束問(wèn)題，通過(guò)尺規(guī)作圖可以很好的保證幾何問(wèn)題求解的實(shí)時(shí)性，通過(guò)數(shù)值求解，因?yàn)樗惴◤?fù)雜度關(guān)系，不能確保實(shí)時(shí)效果?；诖?，本文在Latham－Middleditch 連通圖理論[13]的基礎(chǔ)之上，提出了一種新的基于圖論的方法 ——去并擬合方法，同C－Tree 算法相比，在算法復(fù)雜度增加不大的情況下，求解范圍大幅增加，而同數(shù)值方法相比，在算法復(fù)雜度方面又有明顯改進(jìn)，實(shí)時(shí)效果有了顯著提高。

1 去并擬合方法中的基本概念與算法

定義1幾何體幾何圖形中最基本最具有特征的幾何元素。例如，空間中的點(diǎn)、線、面、球等。

定義2幾何約束兩個(gè)或多個(gè)幾何體之間具有的幾何關(guān)系，如點(diǎn)在線上，點(diǎn)在面上，點(diǎn)點(diǎn)距離等。

定義3幾何體的自由度確定幾何體位置需要的獨(dú)立參數(shù)個(gè)數(shù)，用DOF(O)來(lái)標(biāo)記幾何體O 的自由度。

定義4幾何約束的約束度描述一個(gè)幾何約束所需的代數(shù)方程的個(gè)數(shù)，用DEG(C)來(lái)標(biāo)記幾何約束C 的約束度。

定義5剛體如果與一個(gè)約束系統(tǒng)對(duì)應(yīng)的圖形解為有限個(gè)，則該約束系統(tǒng)為幾何上完整約束，亦稱之為剛體。

LIM0算法該算法是由Gao 等[14]基于圖論的算法提出的，具體描述如下：

輸入一個(gè)幾何約束問(wèn)題的約束圖。

輸出包括所有幾何元素的構(gòu)造序列。

Step 1 如果約束圖G 中存在頂點(diǎn)v，且滿足條件DEG( v ) ≤ DOF( v)，執(zhí)行Step 2。否則如果約束圖不含頂點(diǎn)，則該約束問(wèn)題可以順序構(gòu)造，執(zhí)行Step 3。如果約束圖中仍然有頂點(diǎn)，則該約束問(wèn)題不能順序構(gòu)造。

Step 2 刪除該頂點(diǎn)及與其相關(guān)聯(lián)的邊，對(duì)于余下的約束圖執(zhí)行Step 1；

Step 3 按照與刪除順序相反的順序輸出頂點(diǎn)的序列，即構(gòu)造序列。

LIM0 算法為去并擬合方法的基石，其算法復(fù)雜度為O(n+e)。

連通圖算法

Latham 和Middleditch[13]提出了一種基于圖論中最大b-匹配的變量化設(shè)計(jì)方法。通過(guò)該方法生成的連通圖為一個(gè)有向圖。圖中的每個(gè)結(jié)點(diǎn)表示一個(gè)幾何體或約束，邊只存在于幾何體結(jié)點(diǎn)與約束結(jié)點(diǎn)之間，每條邊都有一個(gè)非負(fù)的整數(shù)權(quán)，并且滿足條件：① 與任一約束結(jié)點(diǎn)相關(guān)聯(lián)的邊、其權(quán)重之和不大于該約束的約束度；② 與任一幾何體結(jié)點(diǎn)相關(guān)聯(lián)的邊的權(quán)重之和不大于該幾何體的自由度。如果該連通圖的權(quán)重之和不小于其它權(quán)重，則該權(quán)重為最大權(quán)重。邊的方向由最大權(quán)重導(dǎo)出，每條邊都存在一個(gè)由幾何體結(jié)點(diǎn)指向約束結(jié)點(diǎn)的方向，如果該邊權(quán)重不為零，則同時(shí)存在一個(gè)由約束結(jié)點(diǎn)指向幾何體結(jié)點(diǎn)的方向。當(dāng)約束圖處于滿足上述兩個(gè)條件的最大權(quán)重狀態(tài)后，采用深度優(yōu)先方法搜索處于最大權(quán)重狀態(tài)的連通圖的強(qiáng)連通分支，再根據(jù)各連通分支之間邊的方向，確定適當(dāng)?shù)那蠼忭樞颉?/p>

Latham 和Middleditch 提出了飽和結(jié)點(diǎn)的概念。指出如果連通圖中的一個(gè)約束結(jié)點(diǎn)的約束度或是一個(gè)幾何體結(jié)點(diǎn)的自由度等于與之關(guān)聯(lián)的邊的權(quán)重之和，則稱該結(jié)點(diǎn)是飽和的，否則為不飽和的。如果一個(gè)連通圖處于最大權(quán)重狀態(tài)時(shí)，該約束問(wèn)題時(shí)結(jié)構(gòu)欠約束的當(dāng)且僅當(dāng)該圖包含不飽和幾何體結(jié)點(diǎn)；該問(wèn)題是結(jié)構(gòu)過(guò)約束的當(dāng)且僅當(dāng)該圖包含不飽和約束結(jié)點(diǎn)。利用該性質(zhì)，Latham 和Middleditch 提出了可以確定欠約束或過(guò)約束的情況的算法，并給出了利用消去低優(yōu)先權(quán)重約束，以修正過(guò)約束和欠約束問(wèn)題，并確定獨(dú)立可解約束子集。通過(guò)添加或刪除約束的方法將其化為完整約束方法。

文獻(xiàn)[13]還描述了關(guān)于幾何約束問(wèn)題的強(qiáng)連通子圖和偏序關(guān)系，并由此提出可增廣路徑，并由此證明，當(dāng)幾何約束問(wèn)題的連通圖中沒(méi)有其他可增廣路徑時(shí)，即為最大權(quán)圖。

定義6廣義構(gòu)造序列通過(guò)Latham 和Middleditch 的b-匹配算法求解一個(gè)幾何約束問(wèn)題，并將該幾何約束問(wèn)題處理為如下形式： G = C1, C2, … , Cn其中，每個(gè) Ci是一個(gè)由幾何體 組成的集合，使得：

（2） 不存在滿足條件（1）的真子集。

滿足條件（1）和（2）的表達(dá)式 G = C1, C2, … , Cn，稱之為廣義構(gòu)造序列。

去并擬合方法為約束求解技術(shù)中的一種，即求解幾何約束問(wèn)題時(shí)，首先通過(guò)連通圖對(duì)幾何約束問(wèn)題進(jìn)行處理，得到廣義構(gòu)造序列，根據(jù)廣義構(gòu)造序列和偏序，確定基元素和驅(qū)動(dòng)體；對(duì)余下幾何體，通過(guò)去除特殊的約束關(guān)系，擬和剩余的約束體和約束關(guān)系，然后合并被去除約束關(guān)系，來(lái)完成對(duì)約束問(wèn)題求解的一種方法。

去并擬合方法需要根據(jù)增廣路徑和偏序關(guān)系，自行完成對(duì)幾何約束問(wèn)題的基元素、驅(qū)動(dòng)體和待測(cè)量對(duì)象的設(shè)置，并自行判斷去除約束關(guān)系Ri，以及自行判定驅(qū)動(dòng)體的驅(qū)動(dòng)軌跡，令驅(qū)動(dòng)體沿驅(qū)動(dòng)軌跡運(yùn)動(dòng)，通過(guò)LIM0 算法對(duì)剩余幾何體進(jìn)行求解，計(jì)算出各個(gè)幾何體之間的相當(dāng)位置，對(duì)幾何體之間的相對(duì)約束關(guān)系進(jìn)行動(dòng)態(tài)測(cè)量，同待測(cè)約束Ri相比較，如果差值在用戶許可范圍之內(nèi)，即為所求。

基元素的確定對(duì)于幾何約束問(wèn)題的求解，一般只關(guān)注于該幾何體的相對(duì)位置，而忽略其絕對(duì)位置。通過(guò)有向圖處理幾何約束問(wèn)題，首先被確定的一組幾何體，如果同剩余幾何體存在著約束關(guān)系，則稱這一組幾何體為一組基元素，基元素在坐標(biāo)系中所處的位置，稱之為基準(zhǔn)位置。

驅(qū)動(dòng)體的確定使用去并擬合方法對(duì)幾何約束問(wèn)題進(jìn)行處理，由有向圖得到廣義構(gòu)造序列，依據(jù)廣義構(gòu)造序列，對(duì)于不能同時(shí)確定的幾何體，根據(jù)強(qiáng)連通圖和偏序關(guān)系，對(duì)于優(yōu)先級(jí)最高的幾何體，使用去除約束關(guān)系，得到有約束關(guān)系屬性的非完備幾何體，根據(jù)該幾何體的約束關(guān)系得到其運(yùn)動(dòng)軌跡，則該幾何體為驅(qū)動(dòng)體，幾何體的運(yùn)動(dòng)軌跡為驅(qū)動(dòng)軌跡。在動(dòng)態(tài)測(cè)量的時(shí)候，由驅(qū)動(dòng)體繞驅(qū)動(dòng)軌跡進(jìn)行運(yùn)動(dòng)，并依據(jù)其拖動(dòng)的相關(guān)元素，完成代測(cè)量對(duì)象的約束測(cè)量，對(duì)于一個(gè)幾何約束問(wèn)題往往有多個(gè)驅(qū)動(dòng)體。

在去并擬合方法中，根據(jù)構(gòu)造序列，選取驅(qū)動(dòng)體后，定義最后的過(guò)約束點(diǎn)為待測(cè)量對(duì)象，去除的約束關(guān)系為待測(cè)約束。當(dāng)驅(qū)動(dòng)體繞其運(yùn)動(dòng)軌跡運(yùn)動(dòng)時(shí)，對(duì)由驅(qū)動(dòng)體與待測(cè)量對(duì)象的相對(duì)位置關(guān)系進(jìn)行計(jì)算，得到兩個(gè)待測(cè)體的相對(duì)距離，稱為測(cè)量約束。當(dāng)驅(qū)動(dòng)體繞驅(qū)動(dòng)軌跡分步運(yùn)行時(shí)，將不同的測(cè)量約束同待測(cè)約束進(jìn)行比較，得到滿足用戶需求的位置，即為幾何體的解。至于精度關(guān)系，根據(jù)需要將整個(gè)運(yùn)動(dòng)軌跡分為N 步來(lái)完成，還需要定義該驅(qū)動(dòng)點(diǎn)繞軌跡運(yùn)動(dòng)的間隔，即根據(jù)不同需要，可以對(duì)N 進(jìn)行不同設(shè)置。

定義7待測(cè)量對(duì)象根據(jù)有向圖與構(gòu)造序列，選取驅(qū)動(dòng)體進(jìn)行求解，定義最終的過(guò)約束體為待測(cè)量對(duì)象，則其上一個(gè)約束關(guān)系為待測(cè)約束。

定義8測(cè)量約束在去并擬合方法中，在驅(qū)動(dòng)體繞其運(yùn)動(dòng)軌跡運(yùn)動(dòng)時(shí)，對(duì)由該驅(qū)動(dòng)體構(gòu)造的兩個(gè)測(cè)量體的相對(duì)位置進(jìn)行計(jì)算，并依據(jù)其位置關(guān)系，得到兩個(gè)待測(cè)體的相對(duì)距離，即為測(cè)量距離。

去并擬合方法的并行處理與串行處理如果通過(guò)設(shè)置驅(qū)動(dòng)體ip 和待測(cè)量對(duì)象iq ，利用去并擬合方法完成對(duì)幾何元素 iΩ 的化簡(jiǎn)，然后通過(guò)設(shè)置驅(qū)動(dòng)體 jp 和待測(cè)量對(duì)象jq 來(lái)完成對(duì)剩余幾何元素 jΩ 的化簡(jiǎn)。以此類推，最后通過(guò)設(shè)置驅(qū)動(dòng)體kp 和待測(cè)量對(duì)象kq 來(lái)完成對(duì)剩余元素Ωk的化簡(jiǎn)，則對(duì)于該圖形所設(shè)置的驅(qū)動(dòng)體pi, pj,… , pk之間的處理方式為串行處理。如果通過(guò)設(shè)置驅(qū)動(dòng)點(diǎn) pi和待測(cè)量對(duì)象 qi，利用去并擬合方法不能夠完成對(duì)幾何元素 Ωi的化簡(jiǎn)，而通過(guò)同時(shí)設(shè)置驅(qū)動(dòng)體 pi, pj,… ,pk和待測(cè)量對(duì)象qi, qj,… , qk來(lái)完成對(duì)剩余幾何元素 Ωi的化簡(jiǎn)，則驅(qū)動(dòng)體 pi, pj,… ,pk之間的處理方式為并行處理。

2 去并擬合算法

在詳細(xì)描述去并擬合算法之前，先看一個(gè)具體例子。

例1 一個(gè)二維圖形如圖1 所示，由A、B、C、D、E、F 六點(diǎn)組成，有AB，BC，AC，BE，AD，CF，EF，DE，DF 共9 個(gè)距離約束，為三連通問(wèn)題，不能規(guī)尺作圖，通過(guò)Latham 的最大b-匹配方法，結(jié)果如下：

廣義構(gòu)造序列如下： C1：{ A} ,{ B },{ C }, { D, E , F }

圖1 二維基本造型

根據(jù)有向圖和廣義構(gòu)造序列，得到基元素為：A，B，C 組成的三角形，令D 點(diǎn)為驅(qū)動(dòng)體，待測(cè)對(duì)象為F，驅(qū)動(dòng)軌跡為過(guò)A 點(diǎn)，以|AD|為半徑的圓C0。故令D 為圓C0上任意一點(diǎn)，由|BE|，|DE|完成了E 點(diǎn)構(gòu)造， F 點(diǎn)作為待測(cè)量對(duì)象，約束|FD|為參考約束，而F 點(diǎn)與D 點(diǎn)的實(shí)際距離為測(cè)量約束，令D 點(diǎn)繞C0運(yùn)動(dòng)時(shí)，對(duì)測(cè)量約束進(jìn)行動(dòng)態(tài)測(cè)量，當(dāng)測(cè)量約束同參考約束之間的差值小于用戶所輸入的精度d，即為正確解。

對(duì)于一個(gè)幾何問(wèn)題，通過(guò)去并擬合方法進(jìn)行求解，如果設(shè)置單個(gè)驅(qū)動(dòng)體不能完全求解，則可以設(shè)置多個(gè)驅(qū)動(dòng)體進(jìn)行并聯(lián)或者串連處理，而對(duì)于任一個(gè)驅(qū)動(dòng)體，必然有一個(gè)待測(cè)量對(duì)象對(duì)應(yīng)。當(dāng)所有的測(cè)量約束與待測(cè)約束的差值，都滿足用戶給定的輸入精度時(shí)，即為正解。

去并擬合算法

輸入幾何體 x0, x1( x0), x2( x0, x1), … , xn( x0, x1, … , xn?1)的約束關(guān)系，精度d。

輸出幾何體 x0, x1( x0), x2( x0, x1), … , xn( x0, x1, … , xn?1)的相對(duì)位置。

Step 1 將幾何約束問(wèn)題進(jìn)行約束圖表示。

Step 2 通過(guò)幾何變換方法處理，并運(yùn)行LIM0算法求解，如果能夠完全求解，則跳到Step 7，否則執(zhí)行Step 3。

Step 3 使用Latham 算法進(jìn)行有向圖匹配，得到廣義構(gòu)造序列，由偏序關(guān)系給出強(qiáng)連通子圖和基元素，并根據(jù)基元素和強(qiáng)連通子圖來(lái)確定驅(qū)動(dòng)體和待測(cè)量對(duì)象。

Step 4 依據(jù)有向圖表示和廣義構(gòu)造序列，判斷能否完成對(duì)剩余幾何體的構(gòu)造，如果能夠完全構(gòu)造，轉(zhuǎn)到Step 5，否則，執(zhí)行Step 6。

Step 5 使用ComputePos()得到幾何體的相對(duì)位置，依據(jù)連桿參考點(diǎn)完成相對(duì)距離的動(dòng)態(tài)測(cè)量，由參考距離與精度d 來(lái)完成連桿驅(qū)動(dòng)體的確定，并跳到Step 7。

Step 6 判斷能否通過(guò)基元素和驅(qū)動(dòng)體的選 取來(lái)完成對(duì)iΩ 的部分構(gòu)造，如果能夠完成部分幾何體mΩ 構(gòu)造，則利用串行處理，根據(jù)有向圖，令完成的幾何體mΩ 為基元素，重新生成驅(qū)動(dòng)體和待測(cè)量對(duì)象進(jìn)并對(duì)幾何體imΩ－ 進(jìn)行構(gòu)造，并 跳至Step 4。如果不能夠化簡(jiǎn)，則利用并行處理，根據(jù)有向圖，在原先的基元素和驅(qū)動(dòng)體的基礎(chǔ)之上，繼續(xù)添加驅(qū)動(dòng)體和待測(cè)量對(duì)象，并跳至Step 4。

Step 7 根據(jù)差值和精度，得到滿足條件的解，算法結(jié)束。

令驅(qū)動(dòng)點(diǎn)對(duì)驅(qū)動(dòng)路徑的搜索分為m 步，則該算法復(fù)雜度為：O(m*(n*m+e))。

去并擬合方法求解的表述范式通過(guò)去并擬合方法來(lái)完成對(duì)于一個(gè)幾何問(wèn)題的求解，往往可以通過(guò)一個(gè)數(shù)學(xué)表達(dá)式來(lái)完成對(duì)求解過(guò)程的詳細(xì)描述。接下來(lái)，作者給出一個(gè)比較典型的去并擬合方法的表達(dá)形式如表達(dá)式(1)所示

如果是去并擬合的串行處理，則范式如式(2)所示

對(duì)于去并擬合的并行處理，范式描述如式(3)所示

去并擬合方法求解的智能性通過(guò)去并擬合方法求解，其智能性主要體現(xiàn)在以下幾個(gè)方面：首先，能夠自動(dòng)完成對(duì)驅(qū)動(dòng)體和待測(cè)量對(duì)象的設(shè)置，并自動(dòng)給出驅(qū)動(dòng)體的驅(qū)動(dòng)軌跡；其次，利用動(dòng)態(tài)測(cè)量功能，當(dāng)驅(qū)動(dòng)體沿驅(qū)動(dòng)軌跡分步運(yùn)動(dòng)，對(duì)每一步都動(dòng)態(tài)求解并測(cè)量約束數(shù)值，依據(jù)測(cè)量約束和待測(cè)約束的差值進(jìn)行判斷，如果能夠滿足用戶需求，即為最終結(jié)果。最后，依據(jù)用戶精度，自動(dòng)完成用戶精度解的選取，并自動(dòng)完成各個(gè)幾何體的實(shí)際位置的計(jì)算，即幾何自動(dòng)作圖。

3 求解示例

接下來(lái)通過(guò)具體示例來(lái)詳細(xì)描述去并擬合方法在約束求解器中的應(yīng)用。

例3 圖3 為3D 幾何約束求解問(wèn)題，由點(diǎn)A、B、C、D、E、F、G、H、X、Y、U、V 共12 個(gè)點(diǎn)組成，共有30 個(gè)距離約束，對(duì)于該問(wèn)題，需要通過(guò)并行處理來(lái)完成求解。通過(guò)最大匹配算法得到一個(gè)廣義構(gòu)造序列如下

根據(jù)廣義構(gòu)造序列，可以得到基元素為：U，V，X，Y 四點(diǎn)。通過(guò)去并擬合方法對(duì)有向圖進(jìn)行處理，最后可以得到的完整解的范式表示為

接下來(lái)對(duì)范式表述作詳細(xì)描述，例3 的處理步驟如下：

（1） 定義基元素，由以下幾何體組成： U、V、X、Y。

（2） 確定兩個(gè)驅(qū)動(dòng)體為G，B，待測(cè)量對(duì)象分別為點(diǎn)H 和點(diǎn)D。驅(qū)動(dòng)體G 的驅(qū)動(dòng)軌跡為以U 為球心，|UG|為半徑的球。連桿驅(qū)動(dòng)點(diǎn)B 的軌跡為以Y 為球心，|YB|為半徑的球。

（3） 根據(jù)有向圖，可以對(duì)點(diǎn)C、A、E 和連桿參考點(diǎn)D 和H 進(jìn)行構(gòu)造。根據(jù)參考值|DB|和|HG|，可以將連桿機(jī)構(gòu)驅(qū)動(dòng)點(diǎn)G 和B 的軌跡由球簡(jiǎn)化為圓，此時(shí)，驅(qū)動(dòng)體G 和B 的待測(cè)量對(duì)象變?yōu)辄c(diǎn)F。

（4） 由有向圖，F(xiàn) 點(diǎn)可以由(|HF|，|EF|，|YF|)確定，根據(jù)測(cè)量約束與待測(cè)約束的的差值同精度值d 相比較來(lái)完成對(duì)驅(qū)動(dòng)體G 與B 的確定。

圖2 三維基本造型

圖3 一個(gè)空間幾何圖形

4 總 結(jié)

本文提出一套完備算法來(lái)求解廣義構(gòu)造序列，由偏序關(guān)系給出強(qiáng)連通子圖，對(duì)不能直接規(guī)尺作圖的幾何問(wèn)題，提出去并擬合算法求解，同數(shù)值求解相比，算法復(fù)雜度大大降低，同C-Tree算法想比，在求解范圍方面又有所增廣。

本文提出的去并擬合方法在求解中，需要利用幾何變換方法對(duì)約束圖處理，將其他約束轉(zhuǎn)化為距離約束來(lái)表示，擴(kuò)大智能連桿器的作圖范圍。在驅(qū)動(dòng)點(diǎn)對(duì)其軌跡逐步搜索時(shí)，通過(guò)設(shè)置不同的跨度，來(lái)完成對(duì)整體的去并擬合算法優(yōu)化處理，通過(guò)對(duì)跨度的不同設(shè)置大大降低去并擬合算法的復(fù)雜度。

[1] Ge J, Chou S C, Gao X. Geometric constraint satisfaction using optimization methods [J]. Compute Aided Design, 2000, 31(14)： 867-879.

[2] Lamure H, Michelucci D. Solving geometric constraint by homotopy [J]. IEEE Trans Vis Compute Graph, 1996, 2(1)： 28-34.

[3] Hoffmann C M, Chiang C S. Variable-radius circles of cluster merging in geometric constraints. I. translational cluster [J]. Compute Aided Design, 2002, 34(11)： 789-797.

[4] Owen J C. Algebraic solution for geometry from dimensional constraints [C]//ACM Symposium Foundation of Solid Modeling, 1991： 397-407.

[5] Bruderlin B. Using geometric rewriting rules for solving geometric problems symbolically [J]. Theorm Compute Science, 1993, 116： 291-303.

[6] Kramer G A. Solving geometric constraints systems： a case study in kinematics [C]//Cambridge, MA; MIT Press, 1992： 326-350.

[7] Durand C, Hoffmann C M, Systematic A. Framework for solving geometric constraint analytically [J]. J Symbolic Compute, 2000, 30(5)： 493-529.

[8] Joan-Arinyo R, Soto A, Correct A. Rule-based geometric constraint solver [J]. Compute Graph, 1997, 21(5)： 599-609.

[9] Gao X S, Lin Q. MMP/geometer——a software package for automated geometry reasoning [C]//Automated Deduction in Geometry, (ed. F. Winkler), Springer, Berlin, 2004： 44-66.

[10] Hoffmann C. Geometric constraint solving in R2and R3, in “computing in euclidean geometry”[C]//eds D.Z. Du and F. Huang, World Scientic, 1995： 266-298.

[11] Owen J. Algebraic solution for geometry from dimensional constraints, in ACM Symp [C]//Found of Solid Modeling, ACM Press, Austin TX, 1991： 397-407.

[12] Gao X S, Lin Q, Zhang G. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving [J]. Computer-Aided Design, 2006, 38(1)： 1-13.

[13] Latham R S， Middleditch A E. Connectivity analysis： a tool for processing geometric constraints [J]. Computer Aided Design, 1996： 28(11)： 917-928.

[14] Gao X S, Hoffmann C M, Yang W. Solving spatial basic geometric constraint configurations with locus intersection [J]. Computer Aided Design, 2004, 36(2)： 111-122.

[15] Gao X S, Jiang K. Survey on geometric constraint solving (in Chinese) [J]. J. of CAD & CG, 2004, 16(4)： 385-396.