基于D-tree分解的欠约束与完备约束的几何约束求解

提出了解决欠约束、完备约束的几何约束问题的D-tree分解算法.首先，提出了一种适用范围更广的处理特殊约束策略，可以将这种特殊约束与普通约束统一化，采用转化策略将欠约束的几何约束问题转化为完备约束的几何约束问题.然后，根据几何约束图中结点的度的性质给出了D-tree分解算法，相比经典算法，D-tree分解算法拥有更低算法复杂度和相同的求解域.最后，根据D-tree分解算法结果的规律性，给出了一个为基于数值的求解方法导出求解序列的策略.D-tree分解算法通过导出的求解序列将提高几何约束求解中基于数值的求解方法的求解效率.

Well Constrained and Under Constrained Geometric Constraint Solving Based on D tree Decomposition

A D tree decomposition algorithm was presented to solve the well constrained and under constrained geometric constraint problems. Firstly， as a preliminary work， a broader range handling strategy was proposed which could unify the special constraints with the ordinary constraints. A transformation strategy was used which could transform the under constrained geometric constraint problem into well constrained geometric constraint problem. Secondly， according to properties of the degree of nodes in the geometric constraint graph， the D tree decomposition algorithm was proposed， which had a lower computational complexity and the same solution domain compared with the classical algorithm. Finally， according to the regularity of the D tree decomposition algorithm’s results， a export strategy to numerical constraint solver’s solving sequence was presented. The solving sequence exported by D tree decomposition algorithm could improve the solving efficiency of geometric constraint solving’s numerical solution.