吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (5): 1583-1590.doi: 10.13229/j.cnki.jdxbgxb201705034

Previous Articles     Next Articles

Identification and process of under- and over-constrained geometric constraint systems based on bipartite graph model

LI Wen-hui1, SUN Ming-yu1, XU Guang-xing2, 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-06-12 Online:2017-09-20 Published:2017-09-20

RICH HTML

0   

PDF (PC)

133

Abstract: In this paper, a geometric constraint system is represented by a bipartite graph model, which expresses geometric primitive parameters and basic geometric constraints, and a new Geometric Constraint Solving (GCS) method based on the maximum matching of bipartite graph is proposed. The under- and over-constrained sub-domains are identified by using the bipartite graph decomposition method. An under-constrained sub-domain is processed by introducing the geometric constraint priority and improving the geometric constraint assembly mechanism. The consistent and inconsistent over-constraints are identified by the modified artificial bee colony algorithm, and the identified over-constrained sub-domain is also effectively processed. Research results show that the GCS method based on the new bipartite graph model is effective.

Key words: computer application, geometric constraint solving, bipartite graph decomposition, under-constrained sub-domain, over-constrained sub-domain

CLC Number: 

  • TP391.7
[1] Betting B, Hoffmann C M. Geometric constraint solving in parametric computer-aided design[J].Journal of Computing and Information Science in Engineering, 2011, 11(2): 1-9.
[2] 夏秋英. 参数化、变量化技术及其CAD系统[J].精密制造与自动化, 2005(1): 53-56.
Xia Qiu-ying. Parametric technology, variation technology and CAD system[J]. Precise Manufacturing & Automation, 2005(1):53-56.
[3] Sun Wei, Ma Tie-qiang, Huang Yu-jun. Research on method of constraint conversion in feature-based data exchange between heterogeneous CAD systems[J].Journal of Mechanical Science and Technology, 2009, 23(1):246-253.
[4] He Chun-hua, Zhang Xiang-wei, Lyu 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: 427-430.
[5] 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.
[6] Cao Chun-hong, Tang Chuan, Zhao Da-zhe, et al. Geometric constraint solving based on GeesePSO optimization[J].Journal of Chinese Computer System, 2011, 32(11): 2299-2302.
[7] Kondo K. Algebraic method for manipulation of dimensional relationships in geometric models[J].Computer-Aided Design, 1992, 24(3): 141-147.
[8] 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.
[9] 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.
[10] 曹春红, 许光星. 基于改进人工蜂群算法的几何约束求解[J].计算机科学与探索, 2015, 9(9): 1122-1131.
Cao Chun-hong, Xu Guang-xing. Geometric constraint solving based on improved artificial bee colony algorithm[J].Journal of Frontiers of Computer Science & Technology, 2015, 9(9): 1122-1131.
[11] 王朝瑞. 图论[M]. 北京:北京工业学院出版社,1987:222-229.
[12] 蒋鲲, 张岩, 潘锲. 用DM-分解求解几何约束问题[J]. 黑龙江大学自然科学学报, 2005, 22(5): 674-680.
Jiang Kun, Zhang Yan, Pan Qie. Geometric constraint solving with DM-decomposition of bigraph[J]. Journal of Natural Science of Heilongjiang University, 2005, 22 (5): 674-680.
[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