吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (4): 1273-1279.doi: 10.13229/j.cnki.jdxbgxb201704037

• 论文 • 上一篇    下一篇

几何约束求解的扩展C-树分解法

李文辉1, 孙明玉1, 曹春红2   

  1. 1.吉林大学 计算机科学与技术学院,长春30012;
    2.东北大学 计算机科学与工程学院,沈阳110819
  • 收稿日期:2016-05-15 出版日期:2017-07-20 发布日期:2017-07-20
  • 通讯作者: 孙明玉(1978-),男,讲师,博士.研究方向:计算机辅助设计,计算机图形学.E-mail:sunmingyu370@sohu.com
  • 作者简介:李文辉(1961-)男,教授,博士生导师.研究方向:计算机辅助设计,计算机图形学.E-mail:liwh@jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61300096); 吉林省科技厅发展计划项目(20140101181JC).

Extension C-tree decomposition method for geometric constraint solving

LI Wen-hui1, SUN Ming-yu1, CAO Chun-hong2   

  1. 1.College of Computer Science and Technology, Jilin University,Changchun 130012, China;
    2.College of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
  • Received:2016-05-15 Online:2017-07-20 Published:2017-07-20

RICH HTML

0   

PDF (PC)

118

摘要： 为了有效分解几何约束系统,本文提出了一种基于增量LMA(ILMA)算法的扩展C-树分解法,该方法将几何约束系统分解为一棵扩展C-树。与C-树分解法相比,该方法能够保证以任意装配几何约束的方式构造的扩展C-树是几何约束系统的最大化分解。实例分解结果表明:将本文方法应用于几何约束求解是行之有效的。

关键词: 计算机应用, 几何约束求解, 扩展C-树, 增量LMA算法, 广义构造序列

Abstract: A decomposition method of the extended C-Tree based on the increment LMA (ILMA) algorithm was proposed. The method decomposes a geometric constraint system into an extended C-Tree. In comparison with the C-Tree decomposition method, the proposed method can ensure that an extended C-Tree is inevitably the maximum decomposition of the geometric constraint system when constructing it in any way of assembling geometric constraints. Research results show that the proposed method is effective when it is applied to GCS.

Key words: computer application, geometric constraint solving(GCS), extended C-Tree, incremental LMA algorithm, generalize construction sequence

中图分类号: 

  • TP391.7
[1] He Chun-hua, Zhang Xiang-wei, Lv Wen-ge. A new approach for solving geometric constraint based on Election-Survey Algorithm[C]//International Conference on Computer, Mechatronics, Control and Electronic Engineering (CMCE), Changchun, China, 2010, Hong Kong: IITA Association, 2012: 427-430.
[2] Cao Chun-hong, Zhang Bin, Li Wen-hui. The research based on the composite particle swarm optimization algorithm in the geometric constraint solving[J].Journal of Image and Graphics, 2007, 12(4): 713-717.
[3] Cao Chun-hong, Tang Chuan, Zhao Da-zhe, et al. Geometric constraint solving based on geese PSO optimization[J].Journal of Chinese Computer System, 2011, 32(11): 2299-2302.
[4] Kondo K. Algebraic method for manipulation of dimensional relationships in geometric models[J]. Computer-Aided Design, 1992, 24(3): 141-147.
[5] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5): 1484-1509.
[6] Lin Qiang, Gao Xiao-shan, Liu Yuan-yuan. The complete method based on geometric constraint solving[J].Journal of Computer- Aided Design & Computer Graphics, 2007, 19(7): 828-834.
[7] Owen J. Algebraic solution for geometry from dimensional constra- ints[C]//Proceedings of ACM Symposiumon Solid Modeling Foundation, Austin, TX, 1991, 397-407.
[8] Owen J. Constraints of simple geometry in two and three dimensions[J]. Intemational Journal of Computer Geometry and Its Applieations, 1996, 6(5): 421-423.
[9] Fudos I, Hoffmann C M. A graph-constructive approach to solving systems of geometric constraints[J]. ACM Transactions on Graphics, 1997, 16(2): 179-216.
[10] Hoffmann C M. Geometric Constraint Solving in R2 and R3[M]. In: Du D Z, Huang F, eds. Computing in Euclidean Geometry. Singapore: World Scientific, 1995. 266-298.
[11] Hoffmann C M, Lomonosov A, Sitharam M. Finding solvable subsets of constraint graphs[C]//Principles and Practice of Constraint Programming-CP97, Third International Conference, Linz, Austria,1997:463-477.
[12] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric constraint systems: I[J]. Performance measures for CAD. J Symbolic Comput 2001; 31: 367-408.
[13] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric cons- traint systems. II[J]. New algorithms. J Symbolic Comput 2001; 31: 409-427.
[14] Hoffmann C M, Lomonosov Andrew, Sitharam Meera. Decompo-sition plans for geom-etric constraint systems, Part I: Performance measures for CAD[J]. Journal of Symbolic Computation,2001,31(4): 367-408.
[15] Samy Ait-Aoudia, Sebti Foufou. A 2D geometric constraint solver using a graph reduction method[J]. Advances in Engineering Software, 2010; 41: 1187-1194.
[16] Latham R S, Middleditch A E. Connectivity analysis: a tool for processing geometric constraints[J]. Computer-Aided Design 1996,28: 917-928.
[17] Gao X, Lin Q, Zhang G. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving[J]. Computer-Aided Design, 2006; 38(1): 1-13.
[18] Lee J Y, Kwon O-Hwan, Lee Jae-Yeol, et al. A hybrid approach to geometric constr- aint solving with grapg analysis and reduction[J]. Advance in Engineering Software, 2003, 34(2): 103-113.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发