基于d-tree分解的几何约束求解器的研究

《基于d-tree分解的几何约束求解器的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC作者姓名：指导教师：密级学位论文基于D．tree分解的几何约束求解器的研究申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：王鹏曹春红副教授东北大学信息科学与工程学院硕士学科类别：工学计算机应用技术2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：马宗民张锡哲，于晓鹏东北大学2014年6月万方数据AThesisinComputerApplicationTechnologyGeometricConstraintSolverBasedonD-treeDecomposi

2、tionAnalysisByWangPengSupervisor：AssociateProfessorCaoChunHongNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：{嘞日期：埘、7、)J7学位论文版权使用授权书本

3、学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：≥酮够签字日期：9,olzk、6、卯．I．两年∥导师签名：嘞光1p签字日期：7p／9、／-≯7万方数据东北大学硕士学位论文摘要基于D．tree分解的几何约束求解器的研究摘要几何约束求解是计算机辅助设计技术的核心内容

4、。基于图论的求解方法作为求解几何约束问题的最重要的方法之一，其优点为求解速度快，有较低的时间复杂度，因此应用最为广泛。分解分析算法作为主要的基于图论的求解方法，在得到广泛应用的同时也有两个问题一直作为研究的焦点：搜索分离对算法的高复杂度问题以及无法指导后续算法求解问题。针对这两个问题，本文提出了一个新的基于D-tree分解的几何约束求解器。针对第～个问题，为降低分解分析算法的时间复杂度，提出D．tree分离对搜索算法和D-tree添加虚边算法。本文将“结点的度”这～概念引入到几何约束求解中。通过对分解分析算法和归约分析

5、算法性质的研究分析，提出并证明一系列新性质。根据这些性质提出D-tree分离对搜索算法和D-tree添加虚边算法。新提出的算法从概念上更容易理解，并且有着更低的时间空间复杂度。在D．tree分离对搜索算法和D．tree添加虚边算法的基础上，提出了D-tree分解分析算法，该算法将分解分析算法每轮递归的时间复杂度由由O(E+玢降低到优玢。针对第二个问题，根据D-tree分解分析算法分解结果的规律性提出D-tree分解结果表示，进而给出了指导后续算法求解的求解序列导出算法。针对分解分析算法与基于数值的求解方法配合求解问题过

6、程中出现的求解顺序不明确问题，根据提出的D-tree分解结果表示本文提出求解序列导出算法。该算法可以给出一个求解序列，使后续算法不必判断直接按顺序求解，避免不必要的资源损失。最后，将D-tree分解分析算法和求解序列导出算法作为主要部分，本文提出基于D．tree分解的几何约束求解器。该求解器可以实现对几何约束图的分解，并给出后续算法的求解序列。通过对两个几何约束问题的求解，表明基于D-tree分解的几何约束求解器从概念上更易理解，有着更好的求解效率并且能避免不必要的资源损失。关键词：分解分析算法；结点的度：求解序列；几

7、何约束求解；虚边万方数据东北大学硕士学位论文AbstractAbstractGeometricconstraintsolvingisthecoreofcomputer-aideddesigntechnology．Thegraphtheorybasedsolvingmethodisoneofthemostimportantmethodsofgeometricconstraintsolving．Theadvantageofthemethodisthatithasafastersolvingspeedandalowertim

8、ecomplexity,SOthatitiswidelyused．Asthepfima叮methodofthegraphtheorybasedsolvingmethod，decompositionanalysisiswidelyusedatthesametimetherearetwoissueshavebeenafocusofre