几何约束求解的去并拟合方法

赵 辰， 林 强， 吴 娟， 罗秋科

（中国物品编码中心，北京 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.