约束问题的计算方法：细分方法

几何约束系统的求解是参数化建模的另一个关键技术。几何约束求解技术（GCS）是基于约束满足的参数化设计方法中最核心的技术，几何约束求解技术的好坏和成熟与否是衡量一个基于约束的参数化设计系统的优良的关键，约束系统求解是智能CAD的重要问题，大量的学者和专家对这个问题进行了深入研究，并提出了多种解决方法。主要有四种，即数值计算法、符号计算法、基于规则的方法、基于图论分析的方法。

（一）约束问题的计算方法

1.数值计算法

数值计算法首先把约束问题转化为代数方程，然后运用各种数值计算的工具来求解代数方程，它包括Newton－Raphson方法、Homotopy方法、最优化方法等。数值方法是一种非常通用的变量化求解方法，可以描述和处理各种约束满足问题，事实上很多其他方法无法处理的情形往往都要用数值方法进行处理。

一般情况下，一个几何约束问题首先可以转化为一个方程组：

则问题变为如何求解这个方程组F（X）=0，这里F=（f1，f2，…，fm）T：Rn→Rm是方程组向量，X=（x1，x2，…，xn）T是变元向量。这个方程组能用Newton－Raphson迭代法来求解。迭代公式是Xk+1=Xk－J（Xk）－1F（Xk），这里J（Xk）是F（X）在点Xk的Jacobi矩阵。

2.符号计算法

符号计算法也是先把约束问题转化成代数方程，但和数值计算法不同的是它不直接求解代数方程，而是先用符号的方法，把原方程的形式改变一下，使其求解相对容易，再用数值计算的方法来求解。

符号几何约束求解方法的优点是可以符号求解，即方程组变量的系数可以是一个符号而不是具体的数值，这大大增强了几何约束求解的效力。另外，符号计算法还可以用于判定几何约束问题是否是完全约束的、欠约束的和过约束的，这是数值方法所不能做到的，与数值的几何约束求解方法不同的是符号的几何约束求解法可以求出方程组所有解，不足是求解速度比较慢，通常需要消耗大量的计算时间和空间。

3.基于规则的方法

基于规则的几何约束求解方法首先将几何约束用谓词来代表，然后将一系列重写规则应用于这些谓词，通过一定推理，最后将几何约束问题转化成一个可构造的形式，即可以通过直尺和圆规将满足集合约束的几何图形构造出来。这种方法可以处理一些复杂的几何约束。

基于规则的几何约束求解方法的优点是可构造性。一旦几何约束问题可以转化成可构造的形式，就可以很快构造出满足约束的几何图形，而且构造步骤简单明了，容易被用户理解。但是由于推理过程往往要搜索和匹配整个数据库，所以导致这种方法求解几何约束问题的速度比较慢，而且实现起来也很困难。对于过约束和欠约束问题，基于规则的方法会以交互的方式提醒用户发生过约束和欠约束的地方，同时给出几种可选的解决方案供用户选择，这主要取决于用于推理的数据库的建立原则。

4.基于图论分析的方法

基于图论分析的方法始于Owen，其基本想法是首先将几何约束问题表示为一个关系图或称为约束图，再用图论中的算法将约束问题表示为一个可以通过直接构造的作图问题。自Owen的工作以后，人们提出了很多基于关系图的算法，特别是Hoffmann给出了将一般约束问题分解为可作图子集的算法，使基于关系图的算法在一定意义下达到了顶峰。

（二）纸样设计系统中的约束求解(www.xing528.com)

纸样设计中约束求解是将约束信息分解为若干个DOC（约束度）=1的基本类型，然后转化为约束方程或方程组，再对其求解，从而得到纸样各几何元素的参数值。根据约束求解的结果，约束系统会出现以下情况。

1.过约束（Over－constrA.I.nted）

如果参数化的几何约束系统没有一个解存在，那么该系统是过约束。

2.欠约束（Under－constrA.I.nted）

如果参数化的几何约束系统有无穷个解存在，那么该系统是欠约束。

3.完备约束（Well－constrA.I.nted）

如果参数化的几何约束系统有有限个解存在，那么该系统是完备约束。

在参数化纸样设计中，过约束是不能接受的。但参数化设计的初始，欠约束是必须存在的，并随着设计的不断深化和细化，持续地对欠约束系统施加约束，使之逐步走向完备约束系统。对于完备约束系统，通常只存在有限个解，但用户只能接受其中的一个解。因此，多解的取舍问题是约束满足的重要问题，需要通过增加约束来指定正确解。比如袖子的后袖宽点，该点的约束为：求已知直线L上一点P（x，y），使之到线外一已知点P0（x0，y0）的距离为定长d，如图4－15所示，点P的约束组合为：

图4－15　后袖宽的确定

ON_L，P，L+1（点P在直线L上）D_PP，P，P0，d（点P到P0的距离是d）直线L的解析表达式为y=0，P0点的坐标为［0，（FAH+BAH）/3］，d1=BAH+1，d2=FAH，则约束方程组为：

解得：

此约束虽为完备约束，但仍有两个解。此时需要加一个约束：点P在直线L的负方向上，得唯一解P1（x1，y1）。