在几何约束问题中，基于图论求解图元约束状态的方法。其基本思想是将几何约束问题表示成几何约束图。通过约束图中顶点与顶点通过边连接的关系来定义几何图形的状态。这种方法可以更好的处理完全约束与过约束问题。
理论相关
以下内容中部分术语可能在不同的文献里面有不同的定义与称呼，但大同小异。其中部分内容属于属于应用实践中总结而出不代表权威性，需谨慎阅读。
一、基础定义
在开始前，先来确定一些基本概念。
1、几何约束系统用约束图G来表示，其中V代表顶点的集合，E代表约束的集合。
G
(
V
,
E
)
G(V,E)
G(V,E)
2、视图的基础图元在约束图中被视为特征顶点。
v
∈
V
v \in V
v∈V
3、为特征顶点添加施加的几何约束在约束途中被视为边或环。
e
∈
E
e \in E
e∈E
4、根据约束作用的对象数量分为一元约束、二元约束、多元约束（可视为二元约束的推广）。
一元约束：
| 约束 | 描述 |
|---|---|
| H_RING | 水平 |
| V_RING | 垂直 |
| R_RING | 半径 |
| FIX_RING | 固定 |
| … | … |
二元约束：
| 约束 | 描述 |
|---|---|
| POINT_COINCIDE | 点重合 |
| POINT_TO_POINT | 点到点距离 |
| POINT_TO_LINE | 点到线距离 |
| POINT_TO_CIRCLE | 点到圆距离 |
| POINT_ON_LINE | 点在线上 |
| POINT_ON_CIRCLE | 点在圆上 |
| LINE_LINE_ANGLE | 线与线夹角 |
| LINE_LINE_PARALLEL | 线与线平行 |
| LINE_LINE_PERPENDICULAR | 线与线垂直 |
| LINE_LINE_EQUAL | 线与线长度相等 |
| LINE_CIRCLE_TANGENT | 线圆相切 |
| CIRCLE_CIRCLE_TANGENT | 圆圆相切 |
| … | … |
多元约束：
| 约束 | 描述 |
|---|---|
| SYMMETRIC | 对称约束 |
| LINEEAR_ARRAY | 线性阵列约束 |
| CIRCULAR_ARRAY | 环形阵列约束 |
| … | … |
5、根据约束作用的对象类型分为直接约束、间接约束（此分类可以探讨）。
间接约束：
| 约束 | 描述 |
|---|---|
| LINE_LINE_EQUAL | 线与线长度相等 |
| CIRCLE_CIRCLE_EQUAL | 圆与圆半径相等 |
| … | … |
注：上面列出的约束用来描述图元间显式或隐式长度间的关系。
6、插值约束相对不那么常用，其中比较有待表性的就是中点约束。
插值约束：
| 约束 | 描述 |
|---|---|
| CENTER | 线段、圆弧中点约束 |
| … | … |
7、在约束图G中每一条边e（二元约束）具有类型唯一性，即两个顶点之间只存在一条同类型的边（比如两Point之间只能有一个欧氏距离约束），应用场景中重复添加的显式约束必然是过约束。
8、环（一元约束、自由度约束），根据图元自由度定义的约束，可以视为与自由度等价的约束类型。
提示：环所映射的约束度是判断完全约束与约束度溢出引发的过约束的重要指标，所以非常重要。
9、核心约束问题可以归纳为特征顶点间的距离或夹角问题，或者说所有的问题都是在核心约束上的推广。
10、理论上约束的种类可以无限细分，不过在应用场景会依据不同软件的功能侧重进行设置。
二、自由度dof（degree of free）
这里的自由度泛指刚体自由度，而是指草图几何元素的自由度。
1、点、线、圆，椭圆，实际生产中大部分图形也是这几种基础图元组合而得，曲线在这里不做讨论。
2、几何元素自由度对照表。
| 几何元素 | 自由度 | 描述 |
|---|---|---|
| 点 | 2 | x、y |
| 线 | 2 | slope、intercept |
| 圆 | 3 | x、y、radius |
| 椭圆 | 5 | x、y、radius1、radius2、angle |
三、约束度doc（degree of constraint）
由约束引发几何元素自由度减少的量称为该约束的约束度。
1、系统中可以引发几何元素自由度减少的约束，其约束度对照表。
| 约束类型 | 约束度 | 描述 |
|---|---|---|
| H_RING | 1 | 水平约束 |
| V_RING | 1 | 垂直约束 |
| R_RING | 1 | 半径约束 |
| FIX_RING | 2 or 3 or 4 | 固定约束，约束度根据图元类型而定 |
四、欠约束、完全约束、过约束
通过图来解算核心目就是为了分别找到约束问题集中的完全约束与过约束问题的集合，还可以为后续数值解算提供提升效率的数据依据。
提示：完全约束与过约束对象的自由度可以视为优化问题中的约束条件。
定义：几何元素的剩余自由度sdof（surplus degree of free）
提示：在理想情况下，特征顶点的约束状态可用以下方式来判断。
1、当sdof > 0时，欠约束。
2、当sdof = 0时，完全约束。
3、当sdof < 0时，过约束。
五、显式约束与隐式约束
这里将用户可通过软件界面可以主动添加并删除的约束统称为显式约束，反之用户不能通过软件界面交互与感知的约束统称为隐式约束。
施加隐式约束不光可以让后续特征顶点状态的求解中逻辑自洽，还有加速数值计算收敛速度的作用。
提示：这里提到的数值计算收敛速度的提升只是个人在实践中的经验与看法，并没有实质的理论支持。
| 约束 | 描述 |
|---|---|
| X_RING | x分量约束 |
| Y_RING | y分量约束 |
| A_RING | 倾角约束 |
| … | … |
注：不同的系统可能在隐式约束的分类与处理，甚至叫法上相差很大。
六、刚体约束模型
定义：刚体是指在运动中和受力作用后，形状和大小不变，而且内部各点的相对位置不变的物体。
同一纬度下所有刚体的自由度都是恒定且相同的，2维平面刚体自由度为3，3维空间中刚体自由度为6。
| 约束 | 自由度 | 描述 |
|---|---|---|
| 2维平面 | 3 | X，Y，rotateZ |
| 3维空间 | 6 | X，Y，X，rotateX，rotateY，rotateZ |
我们来定义一个约束问题：
- 已知一组约束问题g(v,e)，v是特征顶点集，e是边集（二元约束集合）。
- n是特征顶点集的数量，m是边集的数量，dof是刚体的自由度（在2维草图中是3，3维空间中是6）。
根据以上约束问题我们引入一组式子来判断刚体的状态。
- 2n - m > dof，刚体欠定义。
- 2n - m = dof，刚体完全定义。
- 2n - m < dof，刚体过定义。
提示：在不考虑特例的情况下，可以直接套用上式来判断刚体的定义情况。
知道了以上刚体的特性后，我们在应用场景中找到约束问题中的刚体结构，然后在对刚体内部特征顶点的自由度进行判断。理想情况下如果刚体内部只要发现上面提到的自由度被约束，就可以视作该刚体内部的所有特征顶点都是完全约束。
提示：刚体的自由度可以映射到一元约束X_RING，Y_RING，A_RING上。
非常不幸的是，在实际编码中，判断刚体的规约操作不光比较耗时，而且其完备性并不理想。特别是在面对大量特殊约束与冗余无副作用的约束时，此方法显得异常笨重且难以维护。
提示：对刚体约束模型的使用纯属个人感受（可能存在理解偏差等因素），如果有涉及这部分内容大佬可以提供以下参考建议。
关于刚体约束模型相关内容，我在国内外的比较早期的草图几何约束文献中都有看到。如果要用到图论法，深入去看一下这部分内容应该还是很有参考价值的。
七、约束传播模型
任意完全定义的顶点都能够使与它有二元约束关系顶点的自由度减少，即对该顶点施加一个隐式自由度约束。
定义：顶点v1，v2。 其中f(x1为v1的全局最优解，x2为v2任意解，e为v1与v2间的约束，s为v2的剩余自由度*
f
(
x
1
∗
,
x
2
)
:
e
=
s
−
1
f(x1*, x2) : e = s - 1
f(x1∗,x2):e=s−1
问题描述：已知顶点A的剩余自由度为0即完全约束、顶点B无约束即自由度处于最大，为A、B施加一个二元约束AB。这个时候B的自由度减1，然后通过B的剩余自由度判断其定义状态。继续添加一个顶点C其自由度为0也是完全约束状态，这个时候如果为B、C施加一个二元约束BC，B的自由度同样减1。这个时候如果A的自由度为2的化剩余自由度为0为完全定义状态。
通过以上规律可以总结出约束的传播具有普遍性与一贯性，将其归类后得出以下结论：
1、约束传播具有稳定的前提与条件。
-
传播源，即传播因子，在约束问题中表现为一元约束。
- 通过约束传播的基本型结合系统中的实际操作得知，固定约束就是传播因子的一种。扩展一下，如果当前集合元素处于完全约束，那么它的的一元约束都被认为是传播因子也就是传播性。
- 基本上所有的一元约束都具有传播性，当然绝大多数前提是满足集合元素的完全约束。这并不绝对，因为意外其它的自由度约束是具有独立传播的能力的，当然这也是有前提的，关于这点下一节在讨论。
| 约束 | 描述 |
|---|---|
| X_RING | x分量约束 |
| Y_RING | y分量约束 |
| A_RING | 倾角约束 |
| H_RING | 水平约束 |
| V_RING | 垂直约束 |
| R_RING | 半径约束 |
| FIX_RING | 固定约束 |
| … | … |
-
传播路径，即二元约束，路径分为强路径与普通路径。强路径是产生绝大多数过约束的必要条件。后面过约束内容会详细讲到。
- 我们先来回到上一个问题中提到的自由度约束独立传播的问题上。将问题放在这里的原因是因为可独立传播除了固定约束外都对传播路径有所要求。
暂时无法在飞书文档外展示此内容 - 传播路径只能是核心二元约束，即距离或夹角的约束。
- 我们先来回到上一个问题中提到的自由度约束独立传播的问题上。将问题放在这里的原因是因为可独立传播除了固定约束外都对传播路径有所要求。
-
传播对象，即约束传播的目标对象，其接受传播的条件如下。
- 传播对象必须处于欠约束状态。
- 如果传播路径是强路径则可以忽略传播源条件。
2、传播生成的约束具有依赖性，同时依赖于主动传播条件与传播条件。
- 依赖约束都是自由度约束即一元约束，与几何元素的约束度等价，在性质上与其它正常一元数别无二致。
- 依赖约束同时依赖于传播源与传播路径，这样的好处是，在删除其挂载的几何元素、传播路径或传播源的时候能够将其找到并删除。
- 依赖约束只能通过隐式创建，删除的过程也依赖其挂在的几何元素或依赖的传播条件。
- 依赖约束的约束度总和与传播源约束度总和等价。
3、约束传播具有唯一性，即依赖约束的传播条件唯一。
4、为了方便在约束传播后结算剩余自由度，增加了抽象约束的概念。抽象约束但不指带任何具体自由度的约束，抽象自由度属于一元隐式约束且约束度恒等于1。
| 约束 | 描述 |
|---|---|
| AB_RING | 抽象约束 |
约束传播模型，在数据结构上记录了用户不断定义几何图形的过程，这个过程产生的结果不仅可以直观的展示在视图，也方便编码过程中随时了解几何元素的状态并随时做出调整。
八、参数驱动型约束
之所以要把参数驱动约束单独放到后面，主要还是其特殊性，因为该约束是参数化设计中使用频繁、功能依赖性很高的约束类型。
参数驱动型约束*
| 约束名 | 描述 |
|---|---|
| POINT_TO_POINT | 点到点的距离 |
| POINT_TO_LINE | 点到线的距离 |
| LINE_LINE_ANGLE | 线与线的夹角 |
| … | … |
磁约束顾名思义可以通过输入参数来调整约束的几何信息，原则上只要可以将几何信息映射到位置、角度、距离等数据的约束都可以作为驱动型约束。文章来源：https://www.toymoban.com/news/detail-441448.html
九、过约束
在前面已经对过约束做出基础定义，但在应用场景中，这显然不够。事实上也确实如此，除了约束度溢出的情况能造成过约束外，重复的驱动型约束同样被视为过约束条件，当然，在不同的软件系统中可能有更加广泛与细致的定义。既然一千个人心中有一千个哈姆雷特的观点，这里部分内容就索性留白。文章来源地址https://www.toymoban.com/news/detail-441448.html
本文的内容中心主要集中在图论法的基础认知铺垫，并提出了基于约束传播性的基础求解模型。在文中提到的所有约束类型均是真实开发中所运用到的，并不代表任何标准，在不同的系统设计中完全可以有适用自身场景的约束抽象。
到了这里，关于草图几何约束——图论法（一）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
