﻿ 矢量图形在非自交多边形中的裁剪算法
 计算机系统应用  2018, Vol. 27 Issue (11): 231-235 PDF

1. 山西大同大学 数学与计算机科学学院, 大同 037009;
2. 山西大同大学 教育科学与技术学院, 大同 037009;
3. 山西大同大学 网络信息中心, 大同 037009

Clipping Algorithm of Vector Graphics in Nonself-Crossing Polygons
KANG Yao-Long1, FENG Li-Lu2, ZHANG Jing-An3, ZHU Yuan-Yuan2
1. School of Mathematics and Computer Science, Shanxi Datong University, Datong 037009, China;
2. School of Education Science and Technology, Shanxi Datong University, Datong 037009, China;
3. Network Information Center, Shanxi Datong University, Datong 037009, China
Foundation item: Research Project of Shanxi Datong University (2015K2); Project of the 12th Five-Year Plan of Shanxi Education Science (GH-14023); Soft Science Research Program of Datong (2016135); Youth Science Research Project of Shanxi Datong University (2015Q20)
Abstract: Efficiency of the clipping algorithm in computer graphics will directly affect the graphics computing, processing, display speed, and user experience. Around the redundant computing, reuse of objects, multithreading control, etc. in the reducing cycle, this study improved traditional vector clipping algorithms in Java environment. This improved algorithm is superior to the traditional vector graphics clipping algorithm in terms of execution efficiency and memory consumption. The application of proposed algorithm can effectively improve the efficiency of engineering graphics generation.
Key words: nonself-crossing polygons     vector graphics     clipping

1 矢量图形在非自交多边形边界中的裁剪

 图 1 线段、圆与凸多边形裁剪

 图 2 线段、圆与凹多边形裁剪

2 矢量图形在非自交多边形边界中裁剪的传统算法 2.1 线段裁剪非自交多边形传统算法思路

2.2 圆裁剪非自交多边形传统算法思路

3 矢量图形在非自交多边形边界中裁剪的改进算法 3.1 改进算法的思路 3.1.1 降低循环中冗余计算

(1) 直线中交点求解冗余

(2) 圆中交点求解冗余

3.1.2 重用对象

3.1.3 多线程控制

3.2 线段裁剪非自交多边形改进算法

Step 1. 用int nPoints变量存储多边形的顶点数量, 利用两个一维整型数组分别存储点的x, y坐标, 实现二维数组的功能, 并且设置标志量flag1flag2为true.

Step 2. 获取一条线段, 判断斜率是否存在, 如果不存在设置标志量flag2=false; 如果存在求解线段的斜率k2b2.

Step 3. 依次遍历多边形的每条边, 在每一次循环之前都将上一次用于存储线段和多边形的交点以及在多边形内部线段的顶点的列表plist清空, 并且获取当前线段的坐标封装在类Line的对象line中.

Step 4. 判断斜率是否存在, 如果不存在设置标志量flag1=false; 如果存在求解该线段的k1, b1.

Step 5. 判断所获取的两条线段是否有交点, 如果无交点转Step 11; 如果有交点转Step 6.

Step 6. 如果(!flag1&&!flag2)或(k1==k2&&flag1&&flag2)跳出本次循环, 转Step 3; 否则求解交点坐标.

Step 7. 当所求交点坐标中不含有该点, 则将交点存储在列表中, 否则不作处理, 转Step 3进行下轮循环, 直到多边形的每条边都被遍历完转Step 8.

Step 8. 分别判断线段的两个端点是否在多边形内部, 如果在则存入列表中, 不再不作处理, 转Step 2直到所有的线段都被求解完转Step 9.

Step 9. 对列表中的点进行排序.

Step 10. 依次遍历列表中的点, 判断两点的中点坐标是否在多边形内部, 如果在则进行绘制; 否则不进行处理.

Step 11. 结束.

3.3 圆裁剪非自交多边形改进算法

(1) 多边形某条边(线段)与圆求交点的算法思路

 ${{a}}x + {{b}}y + {{c}} = 0$ (1)

 ${\left( {x - {{x}}0} \right)^2} + {\left( {y - {{y}}0} \right)^2} = {{{r}}^2}$ (2)
 图 3 线段与圆求交点

P1P2的参数方程为:

 $\left\{\begin{array}{l}x = {{x1 + (x2}} - {{x1)}}t\\y = {{y}}1 + ({{y}}2 - {{y}}1)t,\;\;t \in \left[ {0,1} \right]\end{array}\right.$ (3)

 ${{A}}*{t^2} + {{B}}*t + {{C}} = 0$ (4)

 $\left\{\begin{array}{l}{{A = x}}{{\rm{1}}^{\rm{2}}}{{ + x}}{{\rm{2}}^{\rm{2}}}{{ + y}}{{\rm{1}}^{\rm{2}}}{{ + y}}{{\rm{2}}^{\rm{2}}}{{ - 2*x1*x2 - 2*y1*y2}}\\{{B = 2}}({{x0*x1 + x1*x2 + y0*y1 }}\\\;\;\;\;\;\;+{{y1*y2 - x0*x2 - y0*y2 - x12 - y12}}) \\{{C = x}}{{\rm{0}}^{\rm{2}}}{{ + x}}{{\rm{1}}^{\rm{2}}}{{ + y}}{{\rm{0}}^{\rm{2}}}{{ + y}}{{\rm{1}}^{\rm{2}}}{{ - 2*x0*x1 - 2*y0*y1 - }}{{{r}}^{\rm{2}}}\end{array}\right.$

${{delta}} = {{{B}}^{\rm{2}}} - {{4*A*C}}$ , 若 ${{delta}} = 0$ , 则只有一个解: $t{\rm{1 = }}t{\rm{2 = }} - {{B/(2*A)}}$ ; 若 ${{delta}} > 0$ , 则有两个解: $t1 = ( - {{B}} + {\rm{sqrt}}({{delta}}))/2*{{A}}$ , $t2 = ( - {{B}} - {\rm{sqrt}}({{delta}}))/2*{{A}}$ . 如果 $0 \leqslant ti \leqslant 1$ , 则将ti代入式(3)所求出的点是线段与圆的交点, 否则不是交点.

(2) 圆与多边形交点的排序算法

$x \geqslant {{x}}0$ : 先按照y值从小到大进行排序, 如果y值相等, 则当 $y < {{y}}0$ 时, 按照x从小到大排序, 如果y值相等, 则当 $y > {{y}}0$ 时, 按照x从大到小排序.

$x < {{x}}0$ :先按照y值从大到小进行排序, 如果y值相等, 则当 $y > {{y}}0$ 时, 按照x从大到小排序, 当 $y < {{y}}0$ 时, 按照x从小到大排序.

(3) 判断圆弧是否裁剪的算法

Q1, Q2,…, Qk是多边形与被裁减圆的所有交点, 并且进行顺时针方向排序. 对两相邻的交点Qi, Qi+1( $0 \leqslant i \leqslant {{K}}$ )之间的圆弧是否绘制, 可采用中点检测法(圆弧存在方向, 即顺时针方向).

① 若M3在窗口外, 圆弧QiQi+1被裁剪.

② 若M3在窗口内, 圆弧QiQi+1被保留.

4 系统仿真实验及分析

(1) 系统仿真实验环境

(2) 单个圆裁剪

 图 4 对一个单圆的裁剪

(3) 百万级数量的线段和圆裁剪

 图 5 裁剪前图形

 图 6 传统裁剪算法的执行内存消耗

 图 7 传统裁剪算法的执行时间消耗

 图 8 改进后裁剪算法的执行内存消耗

 图 9 改进后裁剪算法的执行时间消耗

(4) 实验结果分析

5 总结

 [1] Chlebus E, Krot K. CAD 3D models decomposition in manufacturing processes. Archives of Civil and Mechanical Engineering, 2016, 16(1): 20-29. DOI:10.1016/j.acme.2015.09.008 [2] Qin FW, Li LY, Gao SM, et al. A deep learning approach to the classification of 3D CAD models. Journal of Zhejiang University Science C, 2014, 15(2): 91-106. DOI:10.1631/jzus.C1300185 [3] Koch S, Behrens BA, Hübner S, et al. 3D CAD modeling of deep drawing tools based on a new graphical language. Computer-Aided Design and Applications, 2018, 15(5): 619-630. DOI:10.1080/16864360.2018.1441228 [4] Scheffler R, Murugan VR, Wrobel G, et al. Graphical modelling of a meta-model of CAD models for deep drawing tools. INCOSE International Symposium, 2016, 26(1): 1090-1104. DOI:10.1002/iis2.2016.26.issue-1 [5] Elias R. 2D graphics. Elias R. Digital Media: A Problem-Solving Approach for Computer Graphics. Cham: Springer International Publishing, 2014. 9–64. [6] Jeli Z, Popokonstantinovic B, Stojicevic M. Usage of 3D computer modelling in learning engineering graphics. Cvetković D. Virtual Learning. London: IntechOpen, 2016. [7] 苗永春, 唐权华. 任意多边形窗口的矢量圆裁剪算法. 计算机辅助设计与图形学学报, 2016, 28(9): 1451-1458. DOI:10.3969/j.issn.1003-9775.2016.09.007 [8] Hua H. Irregular architectural layout synthesis with graphical inputs. Automation in Construction, 2016, 72: 388-396. DOI:10.1016/j.autcon.2016.09.009 [9] 汤德佑, 周子琳. 基于临界多边形的不规则件启发式排样算法. 计算机应用, 2016, 36(9): 2540-2544. [10] Mirza MJ, Tahir MW, Anjum N. On singularities computation and classification of redundant robots. Proceedings of International Conference on Computing, Communication and Control Engineering. Dubai, UAE. 2015. 12–16. [11] Yüksek K, Alparslan M, Mendi E. Effective 3-D surface modeling for geographic information systems. Natural Hazards and Earth System Sciences, 2016, 16(1): 123-133. DOI:10.5194/nhess-16-123-2016 [12] 刘凯. AutoCAD坐标标注在工程图中的应用. 软件导刊, 2015, 14(1): 52-53.