基于有向图的二维约束求解算法研究

图学学报

基于有向图的二维约束求解算法研究

出版日期:2010-02-26 发布日期:2015-08-11

2D Geometric Constraint Solving with Directed Graph

Online:2010-02-26 Published:2015-08-11

摘要/Abstract

摘要： 针对过约束、几何完全定义状态判定和约束求解效率等问题，提出了基于约束图，利用自由度理论和约束冲突机制，通过反向约束方向平衡约束，进而通过排序进行约束求解的算法。算法采用约束图记录约束和几何的关系；通过约束平衡的方法进行过约束和几何完全定义的判定；采用排序求解方法，将庞大计算问题转化为一组相对简单的计算问题。算法已得到初步应用，对过约束和几何完全定义状态的判定有明显的效果，而且提高了约束求解效率。

关键词: 计算机应用, 几何约束求解, 约束图, 过约束, 完全定义, 排序求解

Abstract: In order to solve the over-constrained problem and enhance computational efficiency, an algorithm, which is based on the constructing directed constraint graph, revealing constraint conflict, then reversing the direction of the related constraint to balance the constraint graph, and finally sorting the graph to get the solving sequence of geometric entities, is presented. The method of balancing constraints can help transforming the over-constrained problem into well-constrained.

Key words: computer application, solution of geometric constraint, constraint graph, over-constrained, well-constrained, sort algorithm

王世平，郭连水. 基于有向图的二维约束求解算法研究[J]. 图学学报.

WANG Shi-ping, GUO Lian-shui. 2D Geometric Constraint Solving with Directed Graph[J]. Journal of Graphics.

[1]	张盾, 黄志开, 王欢, 吴义鹏, 王颖, 邹家豪. 基于多尺度特征实现超参进化的野生菌分类研究与应用[J]. 图学学报, 2022, 43(4): 580-589.
[2]	曾凡锋，段漾波. 一种基于页眉线的扭曲文档图像快速校正方法[J]. 图学学报, 2016, 37(1): 79-83.
[3]	景天虎，马小龙，刘均利，莫时旭. 基于科技文档的AutoCAD 插图精准出图方法[J]. 图学学报, 2016, 37(1): 125-139.
[4]	何大治，李萍，张茜菡. 疏散过程中人员绕行行为的几何算法[J]. 图学学报, 2016, 37(1): 139-142.
[5]	景天虎，马小龙，刘均利，莫时旭. Word 文档中AutoCAD 数据格式图形显示效果的高效编辑研究[J]. 图学学报, 2015, 36(5): 811-818.
[6]	付光辉，席平，张宝源，李吉星. 涡轮气冷叶片传热分析数据提取技术研究[J]. 图学学报, 2015, 36(3): 384-391.
[7]	邹昆，沃焱，李文生. 一种基于位置关系判定的GPU 三维几何图元拾取方法[J]. 图学学报, 2015, 36(2): 262-267.
[8]	张顺，夏俊芳，翟建波，张秀梅. 气力式水稻芽种直播精量排种器关键部件的设计与仿真[J]. 图学学报, 2014, 35(3): 412-416.
[9]	赵海峰，杜廷娜，叶荣波，赵海波. 心形线双曲拱坝三维建模[J]. 图学学报, 2014, 35(2): 195-199.
[10]	刘荣来，吴玉光. 三维标注信息的管理方法研究[J]. 图学学报, 2014, 35(2): 313-318.
[11]	祁海群，唐敦兵，王强，康与云，刘佩惠，殷磊磊. 基于MBD的飞机工装数字化定义与管理技术研究[J]. 图学学报, 2014, 35(1): 57-62.
[12]	贾雨，王莹，姚兴苗. 交互式等值线图纸矢量化方法[J]. 图学学报, 2013, 34(3): 25-28.
[13]	刘炀，顾晓彤，汤传玲，丁必荣，王静. Inventor 文档特性快速生成及标题栏国标化技术[J]. 图学学报, 2013, 34(2): 148-152.
[14]	唐益明，刘晓平. 与或非功能树的无损简化策略[J]. 图学学报, 2013, 34(1): 31-40.
[15]	魏永乐，晁彩霞. 基于ObjectARX 开发工程图模块的研究[J]. 图学学报, 2013, 34(1): 71-76.