东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (5): 626-629.DOI: 10.12068/j.issn.1005-3026.2014.05.005

• 信息与控制 • 上一篇    下一篇

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

曹春红1，王鹏1，曹犁歌2   

  1. (1 东北大学 信息科学与工程学院， 辽宁 沈阳110819; 2 长春光华学院 外国语学院， 吉林 长春130033)
  • 收稿日期:2013-07-15 修回日期:2013-07-15 出版日期:2014-05-15 发布日期:2014-08-18
  • 通讯作者: 曹春红
  • 作者简介:曹春红(1976-)，女，吉林四平人，东北大学副教授，博士.
  • 基金资助:
    国家自然科学基金资助项目(61300096)；中央高校基本科研业务费专项资金资助项目(N130404013).

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

CAO Chunhong1， WANG Peng1， CAO Lige2   

  1. 1 School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 2 School of Foreign Languages，Changchun Guandhua University， Changchun 130033，China.
  • Received:2013-07-15 Revised:2013-07-15 Online:2014-05-15 Published:2014-08-18
  • Contact: CAO Chunhong
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

652

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

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

Abstract: 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.

Key words: geometric constraint solving, the graph approach, special constraints, decomposition analysis, solving sequence

中图分类号: