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

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

作　　者：曹春红[1] 王鹏[1] 曹犁歌 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819 [2]长春光华学院外国语学院,吉林长春130033

出　　处：《东北大学学报（自然科学版）》2014年第5期626-629,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61300096);中央高校基本科研业务费专项资金资助项目(N130404013)

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

关 键 词：几何约束求解 基于图论方法 特殊约束 分解分析 求解序列 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]