Full Text:   <1653>

CLC number: TP312

On-line Access: 

Received: 2005-02-10

Revision Accepted: 2005-07-10

Crosschecked: 0000-00-00

Cited: 0

Clicked: 2433

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.100 P.100~107

http://doi.org/10.1631/jzus.2005.AS0100


Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting


Author(s):  WANG Jin, LU Guo-dong, PENG Qun-sheng, WU Xuan-hui

Affiliation(s):  State Key Lab. of CAD&CG, Zhejiang University, Hangzhou 310027, China; more

Corresponding email(s):   dwjcom@cmee.zju.edu.cn, lugd@zju.edu.cn

Key Words:  Polygon vertex encoding, Adaptive virtual box, Line segment rejection, Line segment intersection, Line clipping


WANG Jin, LU Guo-dong, PENG Qun-sheng, WU Xuan-hui. Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting[J]. Journal of Zhejiang University Science A, 2005, 6(100): 100~107.

@article{title="Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting",
author="WANG Jin, LU Guo-dong, PENG Qun-sheng, WU Xuan-hui",
journal="Journal of Zhejiang University Science A",
volume="6",
number="100",
pages="100~107",
year="2005",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2005.AS0100"
}

%0 Journal Article
%T Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting
%A WANG Jin
%A LU Guo-dong
%A PENG Qun-sheng
%A WU Xuan-hui
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 100
%P 100~107
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.AS0100

TY - JOUR
T1 - Line clipping against polygonal window algorithm based on the multiple virtual boxes rejecting
A1 - WANG Jin
A1 - LU Guo-dong
A1 - PENG Qun-sheng
A1 - WU Xuan-hui
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 100
SP - 100
EP - 107
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.AS0100


Abstract: 
This paper presents a new algorithm for line clipping against a polygonal window by exploiting the local relationship between each line segment and the polygon. Firstly, a minimal enclosing box (MEB) of the polygon is adopted to reject the invisible line segments located outside the MEB. Secondly, a 45° rotated box is used to encode the endpoint of the line segment, and then reject a portion of the invisible segments crossing polygon corners. Finally, instead of encoding the endpoints of all line segments with respect to the polygonal window, each vertex of the polygon is encoded, taking the line segment to be clipped as reference. For efficient encoding of the polygon vertices, a new concept, termed with slope adaptive virtual box, is introduced regarding each line segment. Such a box can not only conveniently reject all totally invisible lines lying outside the MEB conveniently, but also precisely identify the edges of the polygon with which the line segment potentially intersects. With the summation of the vertex codes, it can be verified whether the line segment is separated from or potentially intersects the polygon window. Based on the product of the codes of adjacent vertices, singular cases of intersection can be solved accurately. Experimental results demonstrate the efficiency and stability of the new algorithm.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Bui, D.H., Skala, V., 1999. New Fast Line Clipping Algorithm in E2 with O(lgN) Complexity. International Conferences SCCG

[2] Cyrus, M., Beck, J., 1978. Generalized two and three dimensional clipping. Computers & Graphics, 3(1):23-28.

[3] Liang, Y.D., Barsky, B.A., 1984. A new concept and method for line clipping. ACM Trans. Graphics, 3(1):1-22.

[4] Liu, Y.K., Liu, G.F., 1993. Line clipping against generalized polygon. Journal of Computer-Aided Design & Computer Graphics, 5(4):269-274 (in Chinese).

[5] Liu, Y.K., Yan, Y., Shi, J.Y., 1999. An efficient algorithm for the line clipping against a polygon. Chinese Journal of Computers, 22(11):1210-1214 (in Chinese).

[6] Lu, G.D., Wu, X.H., 2002. Midpoint-subdivision line clipping algorithm based on filtering technique. Computer-Aided Design & Computer Graphics, 14(6): 513-517 (in Chinese).

[7] Lu, G.D., Wu, X.H., Peng, Q.S., 2002. An efficient line clipping algorithm based on adaptive line rejection. Computers & Graphics, 3(26):409-415.

[8] Newman, W.M., Sproull, R.F., 1979. Principles of Interactive Computer Graphics. McGraw-Hill, New York.

[9] Nicholl, T.M., Lee, D.T., Nicholl, R.A., 1987. An efficient new algorithm for 2D line clipping: Its development and analysis. Computer Graphics, 21(4):253-262.

[10] Skala, V., 1993. Efficient algorithm for line clipping by convex polygon. Computers & Graphics, 17(4):417-421.

[11] Sproull, R.F., Southerland, I.E., 1968. A Clipping Divider. Proceedings of the Fall Joint Computer Conference, 33:765-776.

[12] Wang, J., Liang, Y.D., Peng, Q.S., 1991. A 2-D line clipping algorithm with least arithmetic operations. Chinese Journal of Computers, 14(7):495-504 (in Chinese).

[13] Wang, H.H., Wu, R.X., Cai, S.J., 1998. A new efficient line clipping algorithm based on Geometric transformation. Journal of Software, 9(10):728-733 (in Chinese).

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE