幾何約束求解的去并擬合方法

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出包括所有幾何元素的構造序列。

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

Step 2 刪除該頂點及與其相關聯的邊，對于余下的約束圖執行Step 1；

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

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

連通圖算法

Latham 和Middleditch[13]提出了一種基于圖論中最大b-匹配的變量化設計方法。通過該方法生成的連通圖為一個有向圖。圖中的每個結點表示一個幾何體或約束，邊只存在于幾何體結點與約束結點之間，每條邊都有一個非負的整數權，并且滿足條件：① 與任一約束結點相關聯的邊、其權重之和不大于該約束的約束度；② 與任一幾何體結點相關聯的邊的權重之和不大于該幾何體的自由度。如果該連通圖的權重之和不小于其它權重，則該權重為最大權重。邊的方向由最大權重導出，每條邊都存在一個由幾何體結點指向約束結點的方向，如果該邊權重不為零，則同時存在一個由約束結點指向幾何體結點的方向。當約束圖處于滿足上述兩個條件的最大權重狀態后，采用深度優先方法搜索處于最大權重狀態的連通圖的強連通分支，再根據各連通分支之間邊的方向，確定適當的求解順序。

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

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

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

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

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

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

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

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

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

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

定義7待測量對象根據有向圖與構造序列，選取驅動體進行求解，定義最終的過約束體為待測量對象，則其上一個約束關系為待測約束。

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

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

2 去并擬合算法

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

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

廣義構造序列如下： C1：{ A} ,{ B },{ C }, { D, E , F }

圖1 二維基本造型

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

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

去并擬合算法

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

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

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

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

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

Step 4 依據有向圖表示和廣義構造序列，判斷能否完成對剩余幾何體的構造，如果能夠完全構造，轉到Step 5，否則，執行Step 6。

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

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

Step 7 根據差值和精度，得到滿足條件的解，算法結束。

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

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

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

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

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

3 求解示例

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

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

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

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

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

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

（3） 根據有向圖，可以對點C、A、E 和連桿參考點D 和H 進行構造。根據參考值|DB|和|HG|，可以將連桿機構驅動點G 和B 的軌跡由球簡化為圓，此時，驅動體G 和B 的待測量對象變為點F。

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

圖2 三維基本造型

圖3 一個空間幾何圖形

4 總 結

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

本文提出的去并擬合方法在求解中，需要利用幾何變換方法對約束圖處理，將其他約束轉化為距離約束來表示，擴大智能連桿器的作圖范圍。在驅動點對其軌跡逐步搜索時，通過設置不同的跨度，來完成對整體的去并擬合算法優化處理，通過對跨度的不同設置大大降低去并擬合算法的復雜度。

[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.