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

• • 上一篇    下一篇

基于二部图模型的欠、过约束几何约束系统的识别和处理

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

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.东北大学 计算机科学与工程学院,沈阳 110819
  • 收稿日期:2016-06-12 出版日期:2017-09-20 发布日期:2017-09-20
  • 作者简介:李文辉(1961-),男,教授,博士生导师.研究方向:计算机辅助设计,计算机图形学.E-mail:liwenhui2050@163.com
  • 基金资助:
    国家自然科学基金项目(61300096); 吉林省科技厅发展计划项目(20140101181JC)

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)

134

摘要： 采用表达几何基元参数和基本几何约束的二部图模型表示几何约束系统,提出一种新的基于二部图最大匹配的几何约束求解方法,并由二部图分解法对几何约束系统的欠、过约束属性进行识别。通过加入几何约束优先级,改进几何约束装配机制来处理欠约束几何约束系统;当处理过约束的几何约束系统时,由改进的人工蜂群算法识别一致性与非一致性过约束并对识别的过约束子域进行有效处理。研究结果表明,本文基于新的二部图模型的几何约束求解方法是行之有效的。

关键词: 计算机应用, 几何约束求解, 二部图分解, 欠约束子域, 过约束子域

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

中图分类号: 

  • 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] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[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
本系统由北京玛格泰克科技发展有限公司设计开发