一種新的幾何約束系統(tǒng)參數(shù)取值范圍的計(jì)算方法

張杏莉， 胡運(yùn)紅， 盧新明

（山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266510）

一種新的幾何約束系統(tǒng)參數(shù)取值范圍的計(jì)算方法

張杏莉， 胡運(yùn)紅， 盧新明

（山東科技大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266510）

在利用參數(shù)化CAD系統(tǒng)進(jìn)行圖形設(shè)計(jì)的過程中，通過修改圖形對(duì)象的可變參數(shù)重新生成圖形是最常見的一種操作。但用戶在改變參數(shù)的過程中，由于事先并不知道有效的參數(shù)值，也沒有任何引導(dǎo)信息，導(dǎo)致了用戶只能盲目地不斷輸入?yún)?shù)值，通過反復(fù)輸入?yún)?shù)值來滿足約束關(guān)系的需要。該文將結(jié)構(gòu)約束引入?yún)?shù)有效取值范圍求解的范疇，并提出了確定一類常用的二維參數(shù)化CAD模型中參數(shù)的有效范圍的計(jì)算方法和算法。算法復(fù)雜度為O(n2) 。

計(jì)算機(jī)輔助設(shè)計(jì)；參數(shù)CAD；參數(shù)取值范圍；幾何約束；方位約束；結(jié)構(gòu)約束

CAD軟件的參數(shù)驅(qū)動(dòng)原理是通過修改圖形對(duì)象的參數(shù)或標(biāo)注尺寸來改變圖形對(duì)象的定位及尺寸，重新生成所需圖形。參數(shù)驅(qū)動(dòng)技術(shù)是參數(shù)化、變量化的繪圖系統(tǒng)的核心技術(shù)，采用該設(shè)計(jì)方法，可以快速有效地進(jìn)行產(chǎn)品開發(fā)。在這些軟件中保證圖形對(duì)象間拓?fù)浣Y(jié)構(gòu)不變的情況下改變圖形參數(shù)的值并重新生成幾何圖形是最常見的操作，但用戶在設(shè)計(jì)過程中經(jīng)常會(huì)遇到參數(shù)驅(qū)動(dòng)失敗的情況，這是因?yàn)橛脩羰孪炔⒉恢勒_的參數(shù)值而給出了錯(cuò)誤的或非法的參數(shù)值，這在一定程度上降低了產(chǎn)品開發(fā)的效率，增加了開發(fā)的難度。如圖1所示，圖1(a)表示C3與C1、C2內(nèi)切，其中C3的約束為與C1、C2內(nèi)切，參數(shù)為半徑，此時(shí) C3的半徑應(yīng)滿足C3R<(C1R+C2R-D12)/2（其中C1R表示C1的半徑，C2R表示 C2的半徑，C3R表示 C3的半徑，D12表示C1和C2圓心點(diǎn)間的距離）；圖1(b)表示在給C3半徑重新賦值時(shí)生成的新的幾何實(shí)體，此時(shí)，C3的約束仍為與C1、C2內(nèi)切，但新生成的幾何實(shí)體的拓?fù)湫螤畎l(fā)生了改變，此時(shí)C3R>(D12+C1R+C2R)/2；而當(dāng)給C3半徑的賦值處于區(qū)間((C1R+C2R-D12)/2, (D12+C1R+C2R)/2)時(shí)，C3不存在，則直接導(dǎo)致幾何實(shí)體發(fā)生改變。

圖1 幾何實(shí)體重建失敗

幾何實(shí)體重建失敗一方面可能是由于該幾何實(shí)體參數(shù)化設(shè)計(jì)模型本身導(dǎo)致的；另一方面可能是由于不合理的重建計(jì)劃造成的；同時(shí)還有可能是由于前兩個(gè)方面同時(shí)造成的。這常常給設(shè)計(jì)者在診斷一個(gè)幾何實(shí)體重建失敗的原因時(shí)，造成很大的麻煩[1]。因此，如果在用戶改變某個(gè)參數(shù)值之前，參數(shù)繪圖系統(tǒng)自動(dòng)給出該參數(shù)的有效取值范圍，將會(huì)大大提高設(shè)計(jì)的效率，降低設(shè)計(jì)的難度，也增加軟件的人性化和智能化程度。因此，實(shí)時(shí)地給出當(dāng)前參數(shù)的正確取值范圍就成為一個(gè)新的急需解決的問題。

Hoffman和Kim[2]在二維環(huán)境中對(duì)只包含水平線段和垂直線段的閉合、不自交、良約束的直線多邊型做了一些研究, 并只允許包含水平方向和垂直方向的距離約束。他們確定了在保證線段間拓?fù)浣Y(jié)構(gòu)不變的情況下相關(guān)直線上下移動(dòng)的范圍，另外，他們還指出了同一時(shí)間只能考慮一個(gè)距離參數(shù)的取值范圍。

蔣鯤等[1]人將幾何實(shí)體限制為只包含水平直線和垂直直線的封閉且不自交的矩形，將要求的參數(shù)限制為水平的距離約束和垂直的距離約束，給出了求解每個(gè)參數(shù)有效取值范圍的代數(shù)算法。

Joan-Arinyo等[3]對(duì)于尺規(guī)可構(gòu)造性問題給出了有效的方法。Hilderick A.Van der Meiden和Willen F.Bronsvoort[4]提出的求解方法考慮了三維環(huán)境中基于點(diǎn)的距離約束和角度約束的良約束幾何約束系統(tǒng)，他們將幾何約束系統(tǒng)中的幾何實(shí)體分解成三角形和四面體子問題，在計(jì)算某個(gè)距離約束參數(shù)的取值范圍時(shí)，找出問題的退化子問題并根據(jù)退化子問題求出參數(shù)的臨界值。

在文獻(xiàn)[1-4]中都只考慮了距離約束和角度約束，均為尺寸約束，還沒有考慮結(jié)構(gòu)約束，本文中，筆者將幾何實(shí)體增加到直線和圓，另外還將考慮一種最基本也是最常用的結(jié)構(gòu)約束，即相切約束。

1 提出問題

本文考慮的參數(shù)模型中包含線段和圓，另外還將考慮一種結(jié)構(gòu)約束即相切約束。從數(shù)學(xué)的角度來看，每一個(gè)幾何約束都可以用一組方程組來求解[5]。因此，要獲得整個(gè)幾何約束模型的解，需要解大量的方程組。最終的目的是得到一個(gè)想要的解，所以從大量的非線性方程組的解中選擇一個(gè)符合設(shè)計(jì)者設(shè)計(jì)意圖的解就成了最關(guān)鍵的問題。然而，當(dāng)圖形元素不斷增加，幾何約束的個(gè)數(shù)不斷增多，圖形對(duì)象不斷復(fù)雜化，方程組的解則以指數(shù)級(jí)增長(zhǎng)，從中選擇一個(gè)滿意的解很有可能變成一個(gè)NP問題[6]。

在作者的系統(tǒng)中，通過使用附加的方位約束來解決根的選擇問題。例如，已知半徑過圓外一點(diǎn)做與圓外切圓時(shí)，可以得到滿足條件的兩個(gè)解C1和C2，系統(tǒng)根據(jù)用戶的交互信息獲取用戶的設(shè)計(jì)意圖從而選擇其中一個(gè)解，同時(shí)為此圓附加方位約束值。如圖2所示，可以根據(jù)生成圓的圓心相對(duì)于點(diǎn)P與已知圓C的圓心的連線的位置來區(qū)分這兩個(gè)外切圓，若選擇 C1，為其附加的方位約束值為“outeleft”，若選擇C2，為C2附加的方位約束值為“outerigh”。

本文只考慮二維環(huán)境中給定包括直線段和圓的參數(shù)化模型，如何確定模型中圓的半徑參數(shù)的有效取值范圍，使得設(shè)計(jì)者只要在給定的有效范圍內(nèi)賦值，就會(huì)得到有效的、不改變?cè)心Ｐ偷耐負(fù)湫螤畹男碌膱D形。

畫圓的方法很多，在表1中對(duì)畫圓方法進(jìn)行歸類。

圖2 過P點(diǎn)做與圓C外切的圓

表1 畫圓方法歸類

對(duì)于上述問題，使用筆者創(chuàng)建的LK參數(shù)繪圖系統(tǒng)建立的參數(shù)化模型是完整約束的，因此不需要考慮過約束或者是欠約束的情況[7]。

2 參數(shù)取值范圍計(jì)算方法及算法

一個(gè)幾何實(shí)體的完整約束的參數(shù)化模型(WCPM)可以描述為：WCPM = (G，R)，其中G ={(g，s)| g為幾何實(shí)體（線、圓、非特征點(diǎn)），s為g的方位約束值}；R = {GR}，GR = { |i≠j且gi，gj兩者之間存在的約束關(guān)系，其中 gi對(duì)gj的位置或大小有約束關(guān)系}。

在參數(shù)驅(qū)動(dòng)過程中將借助有向約束圖來完成判斷需要重新計(jì)算和定位的圖形對(duì)象，下面對(duì)有向約束圖的生成過程做簡(jiǎn)單敘述。

在繪圖的過程中，根據(jù)操作命令和交互信息自動(dòng)獲取設(shè)計(jì)約束，并將該設(shè)計(jì)約束轉(zhuǎn)化為有向圖的邊，也就是說，每生成一個(gè)圖形元素，對(duì)相關(guān)的設(shè)計(jì)約束進(jìn)行處理，生成相應(yīng)的有向邊，有向邊指向新生成的圖形元素，有向邊的尾部和與新生成的圖形元素有約束關(guān)系的已經(jīng)繪制的圖形元素相連接，即WCPM中每一個(gè)GR關(guān)系都可以轉(zhuǎn)化成有向約束圖中的一條有向邊。

在有向約束圖中，規(guī)定圖素的特征點(diǎn)不能作為結(jié)點(diǎn)出現(xiàn)在有向約束圖中，而一般意義上的點(diǎn)除外。從這一點(diǎn)來看，使用該方法生成的有向約束圖中結(jié)點(diǎn)的類型和文獻(xiàn)[5]中的約束圖結(jié)點(diǎn)的類型有一定的區(qū)別。例如，線段的兩個(gè)端點(diǎn)在本文中作為特征點(diǎn)來處理，不出現(xiàn)在有向約束圖中，而在文獻(xiàn)[5]中，線段的端點(diǎn)是約束圖中的結(jié)點(diǎn)。

有向約束圖中每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)為該結(jié)點(diǎn)依賴的所有前驅(qū)結(jié)點(diǎn)，也是約束計(jì)算的前提條件，對(duì)于二維環(huán)境中的參數(shù)化模型，每個(gè)結(jié)點(diǎn)最多只有三個(gè)父親結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)的子孫結(jié)點(diǎn)是指從當(dāng)前結(jié)點(diǎn)出發(fā)與當(dāng)前結(jié)點(diǎn)存在簡(jiǎn)單路徑的所有結(jié)點(diǎn)。

另外，每一個(gè)幾何實(shí)體的方位約束值都有非常重要的作用，在本文中，方位約束值有兩個(gè)用途，第一，解決了根的選擇問題；第二，可以使自身及其它圖素的半徑參數(shù)的有效范圍更加的精確。如圖3所示，其中C1的圓心坐標(biāo)為(300,200)，半徑為50，C2的圓心坐標(biāo)為(350, 150)，半徑為80，做與C1、C2內(nèi)切，半徑為20的圓C3，此時(shí)，圓C3的約束為與C1、C2分別內(nèi)切，參數(shù)為半徑，根據(jù)交互信息獲取設(shè)計(jì)者意圖并自動(dòng)為C3添加方位約束值為“rightlitt”，它的意思是該圓位于C2、C1兩圓圓心連線的右側(cè)，且該圓為半徑小于任何一個(gè)內(nèi)切圓的小圓，該模型的當(dāng)前有向約束圖如圖4所示。在不加方位約束的情況下求解 C3的半徑的取值范圍，得到(0,29.64466]，在添加方位約束情況下，半徑的有效取值范圍為(0, 29.64052]，保證了C3的圓心點(diǎn)在C2與C1圓心連線的右側(cè)，可見方位約束是算法中必不可少的內(nèi)容。

圖3 與C1、C2內(nèi)切的圓C3

圖4 圖3的有向約束圖

下面的算法中將討論如何確定模型中圓的半徑參數(shù)的有效取值范圍。

算法1 參數(shù)化模型中圓的半徑參數(shù)的有效范圍的確定算法

輸 入 某圓的ID號(hào)

輸 出 該圓的半徑取值范圍

第一步 判斷該圓的半徑是否為參數(shù)，如果是，轉(zhuǎn)第二步，否則，退出；

第二步 根據(jù)該圓的ID號(hào)獲取類型值，設(shè)其ID號(hào)為L(zhǎng)，并將該圓記為CL，則假設(shè)該圓圓心坐標(biāo)為(CLX, CLY)，半徑為CLR，根據(jù)有向約束圖，得到指向該圓的父結(jié)點(diǎn)的 ID號(hào)，根據(jù)父結(jié)點(diǎn)個(gè)數(shù)及每個(gè)父結(jié)點(diǎn)的ID號(hào)利用算法2列出方程組，再根據(jù)該圓的 ID號(hào)及方位約束值，再次利用算法2列出方程組，轉(zhuǎn)第三步；

第三步 根據(jù)有向約束圖，得到該圓的子孫結(jié)點(diǎn)所表示圖素ID號(hào)、類型和方位約束值，再獲取每一個(gè)子孫結(jié)點(diǎn)的父結(jié)點(diǎn)個(gè)數(shù)及ID號(hào)，再反復(fù)利用算法2列出方程組，與第二步所得的方程組聯(lián)立組成一個(gè)大的方程組；

第四步 用擬牛頓法解此聯(lián)立方程組，求CLR的最大值UR和最小值LR；

第五步 將該半徑的有效取值范圍(UR, LR]輸出在繪圖系統(tǒng)的狀態(tài)顯示區(qū)。

算法2 根據(jù)所求圖素ID號(hào)，父結(jié)點(diǎn)ID號(hào)、方位約束值，列出對(duì)應(yīng)方程組

輸 入 所求圖素ID號(hào)，父結(jié)點(diǎn)ID號(hào)、方位約束值

輸 出 方程組

第零步 設(shè)所求圖素 ID號(hào)為 L，且該圖素為圓，則假設(shè)該圓圓心坐標(biāo)為PC(CLX, CLY)，半徑為CLR，若所求圖素為線段，則返回；

第一步 若所求圖素ID號(hào)，父結(jié)點(diǎn)ID號(hào)不為空，方位約束值為空，則轉(zhuǎn)第二步；若所求圓ID號(hào)和方位約束值不為空，則轉(zhuǎn)第三步；否則，返回；

第二步 若所求圖素的父結(jié)點(diǎn)為圓，其 ID號(hào)為K，設(shè)其圓心為(CKX, CKY)，半徑為CKR；若父結(jié)點(diǎn)為直線段，設(shè)該直線的ID號(hào)為K，直線方程式為aK*x+bK*y+cK= 0；若父結(jié)點(diǎn)為普通點(diǎn)或?yàn)槟骋粓D素的特征點(diǎn)，設(shè)點(diǎn)ID號(hào)為K，則設(shè)該點(diǎn)坐標(biāo)為(PKX, PKY)；

若該圖素為點(diǎn)，則有兩種可能，第一，點(diǎn)在圓上，則方程式為(CLX-PKX)^2+(CLY

-PKY)^2 =CLR^2；第二，點(diǎn)為所求圓的圓心，則所求圓的圓心坐標(biāo)(CX, CY)確定，即添加方程式CLX= PKX，CLY= PKY，返回；

ABS(aK*CLX+bK*CLY+cK)/((aK*aK+bK*bK)^0.5)=CLR，返回；

若該圖素為圓，則有兩種可能，第一，兩圓外切，則方程式為：(CLX-CKX)^2+(CLY-CKY)^2 =(CLR+CKR)^2；第二，兩圓內(nèi)切，則方程式為：(CLX-CKX)^2+(CLY-CKY)^2 =(CLR-CKR)^2，返回；（其中的未知量?jī)H為所求圓圓心(CX, CY)及半徑CR，其余均為已知量）

第三步 若父結(jié)點(diǎn) ID號(hào)為空，將參數(shù)方位約束值轉(zhuǎn)換成相應(yīng)方程組（只有圓有方位約束值）。

若圓類型為comcir、dpcir、tpcir，則該圓沒有方位約束值，返回；

所求否則，若方位約束值中包括righ或left，則：

（1） 圓位于一條有向線段的右側(cè)或左側(cè)；

（2） 圓位于某圓圓心到某條線段的垂線的右側(cè)或左側(cè)；

（3） 圓位于兩圓圓心連線的右側(cè)或左側(cè)。

星雨將“石壓蛤蟆”“死蚯蚓”“大道曰返”講給李離聽，李離也笑得前仰后合，一邊又正色對(duì)星雨講：“顏老師的字雄秀獨(dú)出，一變古法，兼收漢魏晉宋以來風(fēng)流，我朝書法名家，沒有誰超過他的。字如其人，他格力天縱，神乎其神，難以預(yù)測(cè)！練百花拂穴手中的‘快雪時(shí)晴’‘鐘林毓秀’，都應(yīng)體會(huì)書圣的筆意！”星雨聽得半懂不懂，只是覺得顏師父的課雖然沒什么意思，但這些促狹師兄太有意思了……

計(jì)算出有向線段的起點(diǎn)坐標(biāo)PS(SX, SY)、終點(diǎn)坐標(biāo)PE(EX, EY)、PSPE與X正軸的夾角A1，A1∈[0°,360°), A1=ATN((EY-SY)/(EX-SX))(設(shè) EX≠SX)。

若為 righ，則(CLY-SY)*COS(A1)-(CLX-SX)*SIN(A1)<0；

若為 left，則(CLY-SY)*COS(A1)-(CLX-SX)*SIN(A1)>0；

若方位約束值中包括 litt，則表示該圓為內(nèi)切于其它圓的小圓，即該圓的半徑小于任何一個(gè)內(nèi)切圓，此時(shí)添加方程式：(CLX-CMX)^2+(CLY-CMY)^2

若方位約束值中包括bigg，則表示該圓為內(nèi)切于其它圓的大圓，即該圓的半徑大于任何一個(gè)內(nèi)切圓，此時(shí)添加方程式：(CLX-CMX)^2+(CLY-CMY)^2>CMR^2，其中 M 為這些內(nèi)切圓中半徑最大的圓的ID號(hào)；

若方位約束值中包括inne，則表示該圓和另一個(gè)圓為內(nèi)切關(guān)系，則添加方程式：(CLX-CKX)^2+(CLY-CKY)^2

3 實(shí) 例

圖5所示的吊鉤是一個(gè)非常不規(guī)則的零件，圓弧連接比較多，在畫圖過程中，要借助多個(gè)圓并使用裁剪功能后得到最終零件圖。圖5給出了吊鉤的尺寸標(biāo)注及最終零件圖，圖6所示為做圖過程，圖中的所有圓都給了相應(yīng)的標(biāo)識(shí)，其中C3的圓心坐標(biāo)為(0, 0)，半徑為36。下面就以此例來說明在參數(shù)驅(qū)動(dòng)過程中圓C5的半徑取值范圍。

圖5 吊鉤

圖6 圖5的做圖過程

圖7 圖5的有向約束圖

根據(jù)上述有向約束圖的生成方法，圖5所示吊鉤的有向約束圖如圖7所示。下面根據(jù)算法來求C5的半徑取值范圍。

輸 入 ID = 5

第一步 該圓的做圖方法為：相切、相切、半徑，半徑是參數(shù)，轉(zhuǎn)第二步；

第二步 當(dāng)前所求圓ID號(hào)為5，該圓類型為rttcir，方位約束值為inneouteleft，設(shè)其圓心為(C5X,C5Y)，半徑為C5R, C5的父結(jié)點(diǎn)的ID號(hào)分別為2和4，則3次調(diào)用算法2：

（1） 父結(jié)點(diǎn) ID號(hào)為 2，其圓心設(shè)為(C2X,C2Y)，半徑為C2R，該父結(jié)點(diǎn)為圓，且C2與C5為外切關(guān)系，得方程式(C5X-C2X)^2+ (C5Y-C2Y)^2= (C5R+C2R)^2，其中 C2X、C2Y、C2R均為己知量，如圖5所示，其中C2X= 5，C2Y= 0，C2R= 29。

（2） 父結(jié)點(diǎn) ID號(hào)為 4，其圓心設(shè)為(C4X,C4Y)，半徑為C4R，該父結(jié)點(diǎn)為圓，且C4與C5為內(nèi)切關(guān)系，得方程式(C5X-C4X)^2+(C5Y-C4Y)^2= (C5R-C4R)^2，其中C4X、C4Y是輔助線F1：X =-35與圓C3的第二個(gè)交點(diǎn)，計(jì)算可知，C4R為己知量，C4X=-35，C4Y=-8.4261，C4R= 24。

（3） 此時(shí)父結(jié)點(diǎn)ID號(hào)為空，轉(zhuǎn)算法2的第三步，將C5的方位約束值轉(zhuǎn)為相應(yīng)方程式。C5的約束方位值為包含了 inne，增加方程式：(C5X-C4X)^2+(C5Y-C4Y)^20。

此時(shí)所得方程式如下：(C5X-C2X)^2+(C5Y-C2Y)^2 = (C5R+C2R)^2；C2X= 5；C2Y= 0；C2R=29；(C5X-C4X)^2+(C5Y-C4Y)^2=(C5R-C4R)^2；C4X=-35；C4Y=-8.4261；C4R=24；(C5X-C4X)^2+(C5Y-C4Y)^20。

第三步 C5的子孫結(jié)點(diǎn)為C6，C6為當(dāng)前所求圓，其ID號(hào)為6，類型值為rttcir，方位約束值為inneouterigh，因?yàn)樵撟訉O結(jié)點(diǎn)為圓，因此設(shè)其圓心坐標(biāo)為(C6X, C6Y)，半徑為C6R，并從有向約束圖中得知其父結(jié)點(diǎn)為C5和C4，也會(huì)三次調(diào)用算法2：

（1） 父結(jié)點(diǎn) ID號(hào)為 4，其圓心設(shè)為(C4X,C4Y)，半徑為C4R，該父結(jié)點(diǎn)為圓，且C4與C6為內(nèi)切關(guān)系，得方程式(C6X-C4X)^2+(C6Y-C4Y)^2= (C6R-C4R)^2，其中 C4X= -35，C4Y= -8.4261，C4R= 24。

（2） 父結(jié)點(diǎn) ID號(hào)為 5，其圓心設(shè)為(C5X,C5Y)，半徑為C5R，該父結(jié)點(diǎn)為圓，且C6與C5為外切關(guān)系，得方程式(C6X-C5X)^2+(C6Y-C5Y)^2= (C6R+C5R)^2，另外C6R= 2。

（3） 此時(shí)父結(jié)點(diǎn) ID號(hào)為空，轉(zhuǎn)算法二的第四步，將C6的方位約束值轉(zhuǎn)為相應(yīng)方程式。C6的約束方位值為包含了 inne，增加方程式：(C6X-C4X)^2+(C6Y-C4Y)^2

第三步所得方程式如下：(C6X-C4X)^2+(C6Y-C4Y)^2=(C6R-C4R)^2；(C6X-C5X)^2+(C6YC5Y)^2=(C6R+C5R)^2；C6R=2；(C6X-C4X)^2+(C6Y-C4Y)^2

第四步 聯(lián)立第二步和第三步所得方程式，用擬牛頓法求解C5R的最大值和最小值，最終得到C5的半徑 C5R的取值范圍為(0,17.90074]。

第五步 將該半徑的有效取值范圍(0,17.90074]輸出在繪圖系統(tǒng)的狀態(tài)顯示區(qū)，讓設(shè)計(jì)者參考。

經(jīng)實(shí)驗(yàn)證明，圓C5的半徑參數(shù)在(0,17.90074]范圍內(nèi)取任何一個(gè)值都可以保證模型中各圖形間約束關(guān)系、拓?fù)湫螤畈话l(fā)生改變，而在這個(gè)范圍之外的數(shù)值則會(huì)導(dǎo)致模型重建失敗。

4 結(jié) 束 語

為了避免在參數(shù)驅(qū)動(dòng)時(shí)由于賦值的不合理而導(dǎo)致的幾何實(shí)體重建失敗的情況，本文提出了一個(gè)解決算法，對(duì)于二維環(huán)境中的包括線段和圓的良約束幾何約束系統(tǒng)，給出了二維參數(shù)化模型中圓的半徑參數(shù)的有效取值范圍的計(jì)算方法，在給定的取值范圍內(nèi)任何一個(gè)值都保證在約束關(guān)系、拓?fù)湫螤畈蛔兊那闆r下得到一個(gè)想要的解。

本文提出的算法不僅適用于計(jì)算繪圖過程中當(dāng)前繪制的圓的半徑的有效取值范圍，也適用于參數(shù)驅(qū)動(dòng)過程中圓的半徑的有效取值范圍，另外，使用多次該算法可以同時(shí)計(jì)算出當(dāng)前模型中所有半徑的有效取值范圍。

[1]蔣 鯤, 朱長(zhǎng)才, 高小山. 參數(shù)化 CAD中參數(shù)的有效范圍[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2003,15(8)：1016-1020.

[2]Hoffmann C M, Kim K –J. Towards valid parametric CAD models [J]. Computer-Aided Design, 2001, 33：81-90.

[3] Joan-Arinyo R, Mata N. Applying constructive geometric constraint solvers to geometric problems with interval parameters [J]. Nonlinear Analysis, 2001,47：213-224.

[4]Hilderick A Van der Meiden, Willem F Bronsvoort. A constructive approach to calculate parameter ranges for systems of geometric constraints [J]. Computer-Aided Design, 2006, 38：275-283.

[5]fudos I, Hoffmann C M. A graph-constructive approach to solving systems of geometric constraints [J]. ACM Transactions on Graphics, 1997, 16(2)：179-216.

[6]Mata N, Kreinovich V. NP-hardness in geometric construction problems with one interval parameter [C]//Applications of Interval Analysis to Systems and Control with Special Emphasis on Recent Advances in Modal Interval Analysis (MISC'99), Girona(Spain),1999：85-98.

[7]孟祥旭, 汪嘉業(yè), 劉慎權(quán). 基于有向超圖的參數(shù)化表示模型及其實(shí)現(xiàn)[J]. 計(jì)算機(jī)學(xué)報(bào), 1997, 20(11)：982-988.

A New Approach to Calculating Parameter Ranges for Systems of Geometric Constraints

ZHANG Xing-li, HU Yun-hong, LU Xin-ming
( College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao Shandong 266510, China )

In parametric CAD graphic design, it is a common operation to modify the parameters of graph objects to regenerate graphics. Users usually need to repeatedly enter parameter values in the geometric constraint system to get a satisfactory solution. In the process of changing the value of parameters, the allowable parameter values are not known to the user beforehand and there is no guide information, so users have to input the parameter values in a trial-and-error way. This paper introduces structural constraints to the field of interval parameters and proposes an algebraic algorithm for determining the valid ranges of parameter values. The complexity of the algorithm is O(n2).

computer aided design; parametric CAD; parameter ranges; geometric constraints; position constraints; structural constraints

TP 391

A

1003-0158(2010)06-0085-07

2009-01-08

張杏莉（1981-），女，山西芮城人，講師，博士研究生，主要研究方向?yàn)橛?jì)算機(jī)輔助軟件工程，計(jì)算機(jī)圖形學(xué)。

book=6,ebook=123