张杏莉， 胡运红， 卢新明

（山东科技大学信息科学与工程学院，山东 青岛 266510）

一种新的几何约束系统参数取值范围的计算方法

张杏莉， 胡运红， 卢新明

（山东科技大学信息科学与工程学院，山东 青岛 266510）

在利用参数化CAD系统进行图形设计的过程中，通过修改图形对象的可变参数重新生成图形是最常见的一种操作。但用户在改变参数的过程中，由于事先并不知道有效的参数值，也没有任何引导信息，导致了用户只能盲目地不断输入参数值，通过反复输入参数值来满足约束关系的需要。该文将结构约束引入参数有效取值范围求解的范畴，并提出了确定一类常用的二维参数化CAD模型中参数的有效范围的计算方法和算法。算法复杂度为O(n2) 。

计算机辅助设计；参数CAD；参数取值范围；几何约束；方位约束；结构约束

CAD软件的参数驱动原理是通过修改图形对象的参数或标注尺寸来改变图形对象的定位及尺寸，重新生成所需图形。参数驱动技术是参数化、变量化的绘图系统的核心技术，采用该设计方法，可以快速有效地进行产品开发。在这些软件中保证图形对象间拓扑结构不变的情况下改变图形参数的值并重新生成几何图形是最常见的操作，但用户在设计过程中经常会遇到参数驱动失败的情况，这是因为用户事先并不知道正确的参数值而给出了错误的或非法的参数值，这在一定程度上降低了产品开发的效率，增加了开发的难度。如图1所示，图1(a)表示C3与C1、C2内切，其中C3的约束为与C1、C2内切，参数为半径，此时 C3的半径应满足C3R<(C1R+C2R-D12)/2（其中C1R表示C1的半径，C2R表示 C2的半径，C3R表示 C3的半径，D12表示C1和C2圆心点间的距离）；图1(b)表示在给C3半径重新赋值时生成的新的几何实体，此时，C3的约束仍为与C1、C2内切，但新生成的几何实体的拓扑形状发生了改变，此时C3R>(D12+C1R+C2R)/2；而当给C3半径的赋值处于区间((C1R+C2R-D12)/2, (D12+C1R+C2R)/2)时，C3不存在，则直接导致几何实体发生改变。

图1 几何实体重建失败

几何实体重建失败一方面可能是由于该几何实体参数化设计模型本身导致的；另一方面可能是由于不合理的重建计划造成的；同时还有可能是由于前两个方面同时造成的。这常常给设计者在诊断一个几何实体重建失败的原因时，造成很大的麻烦[1]。因此，如果在用户改变某个参数值之前，参数绘图系统自动给出该参数的有效取值范围，将会大大提高设计的效率，降低设计的难度，也增加软件的人性化和智能化程度。因此，实时地给出当前参数的正确取值范围就成为一个新的急需解决的问题。

Hoffman和Kim[2]在二维环境中对只包含水平线段和垂直线段的闭合、不自交、良约束的直线多边型做了一些研究, 并只允许包含水平方向和垂直方向的距离约束。他们确定了在保证线段间拓扑结构不变的情况下相关直线上下移动的范围，另外，他们还指出了同一时间只能考虑一个距离参数的取值范围。

蒋鲲等[1]人将几何实体限制为只包含水平直线和垂直直线的封闭且不自交的矩形，将要求的参数限制为水平的距离约束和垂直的距离约束，给出了求解每个参数有效取值范围的代数算法。

Joan-Arinyo等[3]对于尺规可构造性问题给出了有效的方法。Hilderick A.Van der Meiden和Willen F.Bronsvoort[4]提出的求解方法考虑了三维环境中基于点的距离约束和角度约束的良约束几何约束系统，他们将几何约束系统中的几何实体分解成三角形和四面体子问题，在计算某个距离约束参数的取值范围时，找出问题的退化子问题并根据退化子问题求出参数的临界值。

在文献[1-4]中都只考虑了距离约束和角度约束，均为尺寸约束，还没有考虑结构约束，本文中，笔者将几何实体增加到直线和圆，另外还将考虑一种最基本也是最常用的结构约束，即相切约束。

1 提出问题

本文考虑的参数模型中包含线段和圆，另外还将考虑一种结构约束即相切约束。从数学的角度来看，每一个几何约束都可以用一组方程组来求解[5]。因此，要获得整个几何约束模型的解，需要解大量的方程组。最终的目的是得到一个想要的解，所以从大量的非线性方程组的解中选择一个符合设计者设计意图的解就成了最关键的问题。然而，当图形元素不断增加，几何约束的个数不断增多，图形对象不断复杂化，方程组的解则以指数级增长，从中选择一个满意的解很有可能变成一个NP问题[6]。

在作者的系统中，通过使用附加的方位约束来解决根的选择问题。例如，已知半径过圆外一点做与圆外切圆时，可以得到满足条件的两个解C1和C2，系统根据用户的交互信息获取用户的设计意图从而选择其中一个解，同时为此圆附加方位约束值。如图2所示，可以根据生成圆的圆心相对于点P与已知圆C的圆心的连线的位置来区分这两个外切圆，若选择 C1，为其附加的方位约束值为“outeleft”，若选择C2，为C2附加的方位约束值为“outerigh”。

本文只考虑二维环境中给定包括直线段和圆的参数化模型，如何确定模型中圆的半径参数的有效取值范围，使得设计者只要在给定的有效范围内赋值，就会得到有效的、不改变原有模型的拓扑形状的新的图形。

画圆的方法很多，在表1中对画圆方法进行归类。

图2 过P点做与圆C外切的圆

表1 画圆方法归类

对于上述问题，使用笔者创建的LK参数绘图系统建立的参数化模型是完整约束的，因此不需要考虑过约束或者是欠约束的情况[7]。

2 参数取值范围计算方法及算法

一个几何实体的完整约束的参数化模型(WCPM)可以描述为：WCPM = (G，R)，其中G ={(g，s)| g为几何实体（线、圆、非特征点），s为g的方位约束值}；R = {GR}，GR = { |i≠j且gi，gj两者之间存在的约束关系，其中 gi对gj的位置或大小有约束关系}。

在参数驱动过程中将借助有向约束图来完成判断需要重新计算和定位的图形对象，下面对有向约束图的生成过程做简单叙述。

在绘图的过程中，根据操作命令和交互信息自动获取设计约束，并将该设计约束转化为有向图的边，也就是说，每生成一个图形元素，对相关的设计约束进行处理，生成相应的有向边，有向边指向新生成的图形元素，有向边的尾部和与新生成的图形元素有约束关系的已经绘制的图形元素相连接，即WCPM中每一个GR关系都可以转化成有向约束图中的一条有向边。

在有向约束图中，规定图素的特征点不能作为结点出现在有向约束图中，而一般意义上的点除外。从这一点来看，使用该方法生成的有向约束图中结点的类型和文献[5]中的约束图结点的类型有一定的区别。例如，线段的两个端点在本文中作为特征点来处理，不出现在有向约束图中，而在文献[5]中，线段的端点是约束图中的结点。

有向约束图中每个结点的父结点为该结点依赖的所有前驱结点，也是约束计算的前提条件，对于二维环境中的参数化模型，每个结点最多只有三个父亲结点；每个结点的子孙结点是指从当前结点出发与当前结点存在简单路径的所有结点。

另外，每一个几何实体的方位约束值都有非常重要的作用，在本文中，方位约束值有两个用途，第一，解决了根的选择问题；第二，可以使自身及其它图素的半径参数的有效范围更加的精确。如图3所示，其中C1的圆心坐标为(300,200)，半径为50，C2的圆心坐标为(350, 150)，半径为80，做与C1、C2内切，半径为20的圆C3，此时，圆C3的约束为与C1、C2分别内切，参数为半径，根据交互信息获取设计者意图并自动为C3添加方位约束值为“rightlitt”，它的意思是该圆位于C2、C1两圆圆心连线的右侧，且该圆为半径小于任何一个内切圆的小圆，该模型的当前有向约束图如图4所示。在不加方位约束的情况下求解 C3的半径的取值范围，得到(0,29.64466]，在添加方位约束情况下，半径的有效取值范围为(0, 29.64052]，保证了C3的圆心点在C2与C1圆心连线的右侧，可见方位约束是算法中必不可少的内容。

图3 与C1、C2内切的圆C3

图4 图3的有向约束图

下面的算法中将讨论如何确定模型中圆的半径参数的有效取值范围。

算法1 参数化模型中圆的半径参数的有效范围的确定算法

输 入 某圆的ID号

输 出 该圆的半径取值范围

第一步 判断该圆的半径是否为参数，如果是，转第二步，否则，退出；

第二步 根据该圆的ID号获取类型值，设其ID号为L，并将该圆记为CL，则假设该圆圆心坐标为(CLX, CLY)，半径为CLR，根据有向约束图，得到指向该圆的父结点的 ID号，根据父结点个数及每个父结点的ID号利用算法2列出方程组，再根据该圆的 ID号及方位约束值，再次利用算法2列出方程组，转第三步；

第三步 根据有向约束图，得到该圆的子孙结点所表示图素ID号、类型和方位约束值，再获取每一个子孙结点的父结点个数及ID号，再反复利用算法2列出方程组，与第二步所得的方程组联立组成一个大的方程组；

第四步 用拟牛顿法解此联立方程组，求CLR的最大值UR和最小值LR；

第五步 将该半径的有效取值范围(UR, LR]输出在绘图系统的状态显示区。

算法2 根据所求图素ID号，父结点ID号、方位约束值，列出对应方程组

输 入 所求图素ID号，父结点ID号、方位约束值

输 出 方程组

第零步 设所求图素 ID号为 L，且该图素为圆，则假设该圆圆心坐标为PC(CLX, CLY)，半径为CLR，若所求图素为线段，则返回；

第一步 若所求图素ID号，父结点ID号不为空，方位约束值为空，则转第二步；若所求圆ID号和方位约束值不为空，则转第三步；否则，返回；

第二步 若所求图素的父结点为圆，其 ID号为K，设其圆心为(CKX, CKY)，半径为CKR；若父结点为直线段，设该直线的ID号为K，直线方程式为aK*x+bK*y+cK= 0；若父结点为普通点或为某一图素的特征点，设点ID号为K，则设该点坐标为(PKX, PKY)；

若该图素为点，则有两种可能，第一，点在圆上，则方程式为(CLX-PKX)^2+(CLY

-PKY)^2 =CLR^2；第二，点为所求圆的圆心，则所求圆的圆心坐标(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；第二，两圆内切，则方程式为：(CLX-CKX)^2+(CLY-CKY)^2 =(CLR-CKR)^2，返回；（其中的未知量仅为所求圆圆心(CX, CY)及半径CR，其余均为已知量）

第三步 若父结点 ID号为空，将参数方位约束值转换成相应方程组（只有圆有方位约束值）。

若圆类型为comcir、dpcir、tpcir，则该圆没有方位约束值，返回；

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

（1） 圆位于一条有向线段的右侧或左侧；

（2） 圆位于某圆圆心到某条线段的垂线的右侧或左侧；

（3） 圆位于两圆圆心连线的右侧或左侧。

星雨将“石压蛤蟆”“死蚯蚓”“大道曰返”讲给李离听，李离也笑得前仰后合，一边又正色对星雨讲：“颜老师的字雄秀独出，一变古法，兼收汉魏晋宋以来风流，我朝书法名家，没有谁超过他的。字如其人，他格力天纵，神乎其神，难以预测！练百花拂穴手中的‘快雪时晴’‘钟林毓秀’，都应体会书圣的笔意！”星雨听得半懂不懂，只是觉得颜师父的课虽然没什么意思，但这些促狭师兄太有意思了……

计算出有向线段的起点坐标PS(SX, SY)、终点坐标PE(EX, EY)、PSPE与X正轴的夹角A1，A1∈[0°,360°), A1=ATN((EY-SY)/(EX-SX))(设 EX≠SX)。

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

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

若方位约束值中包括 litt，则表示该圆为内切于其它圆的小圆，即该圆的半径小于任何一个内切圆，此时添加方程式：(CLX-CMX)^2+(CLY-CMY)^2

若方位约束值中包括bigg，则表示该圆为内切于其它圆的大圆，即该圆的半径大于任何一个内切圆，此时添加方程式：(CLX-CMX)^2+(CLY-CMY)^2>CMR^2，其中 M 为这些内切圆中半径最大的圆的ID号；

若方位约束值中包括inne，则表示该圆和另一个圆为内切关系，则添加方程式：(CLX-CKX)^2+(CLY-CKY)^2

3 实 例

图5所示的吊钩是一个非常不规则的零件，圆弧连接比较多，在画图过程中，要借助多个圆并使用裁剪功能后得到最终零件图。图5给出了吊钩的尺寸标注及最终零件图，图6所示为做图过程，图中的所有圆都给了相应的标识，其中C3的圆心坐标为(0, 0)，半径为36。下面就以此例来说明在参数驱动过程中圆C5的半径取值范围。

图5 吊钩

图6 图5的做图过程

图7 图5的有向约束图

根据上述有向约束图的生成方法，图5所示吊钩的有向约束图如图7所示。下面根据算法来求C5的半径取值范围。

输 入 ID = 5

第一步 该圆的做图方法为：相切、相切、半径，半径是参数，转第二步；

第二步 当前所求圆ID号为5，该圆类型为rttcir，方位约束值为inneouteleft，设其圆心为(C5X,C5Y)，半径为C5R, C5的父结点的ID号分别为2和4，则3次调用算法2：

（1） 父结点 ID号为 2，其圆心设为(C2X,C2Y)，半径为C2R，该父结点为圆，且C2与C5为外切关系，得方程式(C5X-C2X)^2+ (C5Y-C2Y)^2= (C5R+C2R)^2，其中 C2X、C2Y、C2R均为己知量，如图5所示，其中C2X= 5，C2Y= 0，C2R= 29。

（2） 父结点 ID号为 4，其圆心设为(C4X,C4Y)，半径为C4R，该父结点为圆，且C4与C5为内切关系，得方程式(C5X-C4X)^2+(C5Y-C4Y)^2= (C5R-C4R)^2，其中C4X、C4Y是辅助线F1：X =-35与圆C3的第二个交点，计算可知，C4R为己知量，C4X=-35，C4Y=-8.4261，C4R= 24。

（3） 此时父结点ID号为空，转算法2的第三步，将C5的方位约束值转为相应方程式。C5的约束方位值为包含了 inne，增加方程式：(C5X-C4X)^2+(C5Y-C4Y)^20。

此时所得方程式如下：(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的子孙结点为C6，C6为当前所求圆，其ID号为6，类型值为rttcir，方位约束值为inneouterigh，因为该子孙结点为圆，因此设其圆心坐标为(C6X, C6Y)，半径为C6R，并从有向约束图中得知其父结点为C5和C4，也会三次调用算法2：

（1） 父结点 ID号为 4，其圆心设为(C4X,C4Y)，半径为C4R，该父结点为圆，且C4与C6为内切关系，得方程式(C6X-C4X)^2+(C6Y-C4Y)^2= (C6R-C4R)^2，其中 C4X= -35，C4Y= -8.4261，C4R= 24。

（2） 父结点 ID号为 5，其圆心设为(C5X,C5Y)，半径为C5R，该父结点为圆，且C6与C5为外切关系，得方程式(C6X-C5X)^2+(C6Y-C5Y)^2= (C6R+C5R)^2，另外C6R= 2。

（3） 此时父结点 ID号为空，转算法二的第四步，将C6的方位约束值转为相应方程式。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

第四步 联立第二步和第三步所得方程式，用拟牛顿法求解C5R的最大值和最小值，最终得到C5的半径 C5R的取值范围为(0,17.90074]。

第五步 将该半径的有效取值范围(0,17.90074]输出在绘图系统的状态显示区，让设计者参考。

经实验证明，圆C5的半径参数在(0,17.90074]范围内取任何一个值都可以保证模型中各图形间约束关系、拓扑形状不发生改变，而在这个范围之外的数值则会导致模型重建失败。

4 结 束 语

为了避免在参数驱动时由于赋值的不合理而导致的几何实体重建失败的情况，本文提出了一个解决算法，对于二维环境中的包括线段和圆的良约束几何约束系统，给出了二维参数化模型中圆的半径参数的有效取值范围的计算方法，在给定的取值范围内任何一个值都保证在约束关系、拓扑形状不变的情况下得到一个想要的解。

本文提出的算法不仅适用于计算绘图过程中当前绘制的圆的半径的有效取值范围，也适用于参数驱动过程中圆的半径的有效取值范围，另外，使用多次该算法可以同时计算出当前模型中所有半径的有效取值范围。

[1]蒋 鲲, 朱长才, 高小山. 参数化 CAD中参数的有效范围[J]. 计算机辅助设计与图形学学报, 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]孟祥旭, 汪嘉业, 刘慎权. 基于有向超图的参数化表示模型及其实现[J]. 计算机学报, 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-），女，山西芮城人，讲师，博士研究生，主要研究方向为计算机辅助软件工程，计算机图形学。

book=6,ebook=123