趙 辰， 林 強， 吳 娟， 羅秋科

（中國物品編碼中心，北京 100029）

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

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

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

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

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

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

定義3幾何體的自由度確定幾何體位置需要的獨立參數(shù)個數(shù)，用DOF(O)來標記幾何體O 的自由度。

定義4幾何約束的約束度描述一個幾何約束所需的代數(shù)方程的個數(shù)，用DEG(C)來標記幾何約束C 的約束度。

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

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

輸入一個幾何約束問題的約束圖。

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

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

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

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

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

連通圖算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 去并擬合算法

在詳細描述去并擬合算法之前，先看一個具體例子。

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

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

圖1 二維基本造型

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

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

去并擬合算法

輸入幾何體 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)的相對位置。

Step 1 將幾何約束問題進行約束圖表示。

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

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

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

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

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

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

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

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

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

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

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

3 求解示例

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

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

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

接下來對范式表述作詳細描述，例3 的處理步驟如下：

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

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

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

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

圖2 三維基本造型

圖3 一個空間幾何圖形

4 總 結(jié)

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

本文提出的去并擬合方法在求解中，需要利用幾何變換方法對約束圖處理，將其他約束轉(zhuǎn)化為距離約束來表示，擴大智能連桿器的作圖范圍。在驅(qū)動點對其軌跡逐步搜索時，通過設(shè)置不同的跨度，來完成對整體的去并擬合算法優(yōu)化處理，通過對跨度的不同設(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.