﻿ 任意多边形窗口的圆裁剪算法
 计算机系统应用  2018, Vol. 27 Issue (8): 170-175 PDF

1. 新疆师范高等专科学校, 乌鲁木齐 830043;
2. 北京邮电大学世纪学院 移动媒体与文化计算北京市重点实验室, 北京 102101

Algorithm for Circle Clipping Based on Arbitrary Polygon Window
YANG Qin1, LI Ning2, WANG Liang-Liang1
1. Xinjiang Teacher’s College, Urumqi 830043, China;
2. Mobile Media and Culture Computing Key Laboratory of Beijing, Century College, Beijing University of Posts and Telecommunications, Beijing 102101, China
Foundation item: National Science and Technology Support Program (2014BAH13F02)
Abstract: For the problem of the circle clipping against arbitrary polygon window, the more comprehensive and effective clipping algorithm is proposed in this study. First, according to x-scan line algorithm, the spatial relationship between the circle and the polygon window is determined. Next, for the case of the polygon window and the circle intersection, the intersect points of the circle and each side of the polygon window are calculated in the counterclockwise direction and sorted correctly. At last, according to the relationship between two points, determining to draw a line or a circle arc. The whole circle clipping is obtained. The result expresses that the algorithm can be comprehensive and effective to complete circle clipping.
Key words: polygon window     circle     clipping     spatial relationship

1 引言

2 直线段和圆的位置关系

(1) 圆与多边形窗口每条直线段是否有相交; 如果相交, 如何求交点;

(2) 圆和多边形的位置关系如何确定.

 ${(x - {x_0})^2} + {(y - {y_0})^2} = {r^2}$ (1)

 $\left\{ {\begin{array}{*{20}{c}}{x = {x_1} + ({x_2} - {x_1})t}\\{y = {y_1} + ({y_2} - {y_1})t}\end{array}} \right.\quad \quad t \in [0,1]$ (2)

 图 1 直线段和圆的位置关系

 $a{t^2} + bt + c = 0$ (3)

 $a = {({x_2} - {x_1})^2} + {({y_2} - {y_1})^2}$
 $b = 2[({x_2} - {x_1})({x_1} - {x_0}) + ({y_2} - {y_1})({y_1} - {y_0})]$
 $c = {({x_1} - {x_0})^2} + {({y_1} - {y_0})^2} - {r^2}$

$\Delta = {b^2} - 4ac$ ,

$\Delta < 0$ , 说明方程(3)没有解;

$\Delta = 0$ , 说明方程(3)有且仅有一个解: ${t_1} = {t_2} = - \displaystyle\frac{b}{{2a}}$ ;

$\Delta > 0$ , 说明方程(3)有两个解, 分别为: ${t_1} = \displaystyle\frac{{ - b + \sqrt \Delta }}{{2a}}$ , ${t_2} = \displaystyle\frac{{ - b - \sqrt \Delta }}{{2a}}$ .

3 基于多边形窗口的圆的裁剪

 图 2 多边形窗口和圆的位置关系

3.1 $x{\rm{ - }}$ 扫描线算法判断多边形窗口和圆的位置关系

3.2 基于多边形窗口的圆的裁剪.

(1) $\forall \;{n_i} = 0$ $\forall \;{n_i} = 2$

(2) ${n_i}$ 的取值即有0也有2

(3) $\forall \;{n_i} = 1$

(4) ${n_i}$ 的取值中0, 1, 2都有

① 如果 ${Q_i}$ , ${Q_{i + 1}}$ 为多边形窗口中同一条直线段与圆的交点, 则弧 ${Q_i}{Q_j}$ 被裁剪, 绘制直线段 ${Q_i}{Q_j}$ ;

② 如果 ${Q_i}$ , ${Q_{i + 1}}$ 为多边形窗口中不同直线段与圆的交点, 则弧 ${Q_i}{Q_{i + 1}}$ 被绘制;

③ 如果 ${Q_i}$ , ${Q_{i + 1}}$ 中, 一个点为多边形窗口中一条边与圆的交点, 另一点为圆内的多边形顶点, 则绘制直线段 ${Q_i}{Q_{i + {\rm{1}}}}$ .

4 算法实现与实例仿真 4.1 多边形窗口和圆的位置关系

4.2 实例仿真

 图 3 算法框架

 图 4 多边形窗口与圆分离及裁剪结果

 图 5 圆在多边形窗口内及裁剪结果

 图 6 多边形窗口在圆内及裁剪结果

 图 7 多边形窗口与圆相交及裁剪结果

5 结论

 [1] Huang WJ, Wang Y. A novel algorithm for line clipping. Proceedings of 2009 International Conference on Computational Intelligence and Software Engineering. Wuhan, China. 2009. 1–5. [2] 洪燕, 洪智化, 刘欣. 一种更有效的矩形窗口线裁剪算法. 景德镇高专学报, 2014, 29(3): 17-18. DOI:10.3969/j.issn.1008-8458.2014.03.008 [3] 王蕊, 阎晓敏, 唐棣. 基于矩形窗口分区编码的圆形裁剪新算法. 辽宁大学学报(自然科学版), 2011, 38(2): 177-180. DOI:10.3969/j.issn.1000-5846.2011.02.019 [4] 张钧, 王鹏. 一种新的矢量数据多边形的快速裁剪算法. 中国图象图形学报, 2008, 13(12): 2409-2413. DOI:10.11834/jig.20081225 [5] 黄文钧. 基于矩阵乘法的多边形窗口线裁剪算法. 计算机科学, 2013, 40(10): 309-317. DOI:10.3969/j.issn.1002-137X.2013.10.066 [6] 陆国栋, 邢世海, 彭群生. 基于顶点编码的多边形窗口线裁剪高效算法. 计算机学报, 2002, 25(9): 987-993. DOI:10.3321/j.issn:0254-4164.2002.09.014 [7] 苗永春, 唐权华. 任意多边形窗口的矢量圆裁剪算法. 计算机辅助设计与图形学学报, 2016, 28(9): 1451-1458. DOI:10.3969/j.issn.1003-9775.2016.09.007 [8] 杭后俊, 孙丽萍. 任意多边形窗口的圆裁剪算法. 计算机技术与发展, 2009, 19(5): 235-237, 241. DOI:10.3969/j.issn.1673-629X.2009.05.066 [9] Simonson L J. Industrial strength polygon clipping: a novel algorithm with applications in VLSI CAD. Computer-Aided Design, 2010, 42(12): 1189-1196. DOI:10.1016/j.cad.2010.06.008