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

来源期刊：东北大学学报(自然科学版)2014年第5期

论文作者：曹春红 王鹏 曹犁歌

文章页码：626 - 629

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

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