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

• Orginal Article • Previous Articles     Next Articles

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)

135

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

CLC Number: 

  • 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] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd