The Line Clipping Algorithm Basing on Affine Transformation
- 1
Abstract
A new algorithm for clipping line segments by a rectangular window on rectangular coordinate system is presented in this paper. The algorithm is very different to the other line clipping algorithms. For the line segments that cannot be identified as completely inside or outside the window by simple testings, this algorithm applies affine transformations (the shearing transformations) to the line segments and the window, and changes the slopes of the line segments and the shape of the window. Thus, it is clear for the line segment to be outside or inside of the window. If the line segments intersect the window, the algorithm immediately (no solving equations) gets the intersection points. Having applied the inverse transformations to the intersection points, the algorithm has the final results. The algorithm is successful to avoid the complex classifications and computations. Besides, the algorithm is effective to simplify the processes of finding the intersection points. Comparing to some classical algorithms, the algorithm of this paper is faster for clipping line segments and more efficient for calculations.
- D. Hearn and M. P. Baker, “Computer Graphics,” C Version, 2nd Edition, Prentice Hall, Inc., Upper Saddle River, 1998, p. 226.
- M. Cyrus and J. Beck, “Generalized Two and Three Dimensional Clipping,” Computers and Graphics, Vol. 3, No. 1, 1978, pp. 23-28.
- D. Hearn and M. P. Baker, “Computer Graphics,” C Version, 2nd Edition, Prentice Hall, Inc., Upper Saddle River, 1998, p. 233.
- T. M. Nicholl, D. T. Lee and R. A. Nicholl, “An Efficient New Algorithm for 2-D Line Clipping: Its Development and Analysis,” Computers and Graphics, Vol. 21, No. 4, 1987, pp. 253-262.
- D. Hearn and M. P. Baker, “Computer Graphics,” C Version, 2nd Edition, Prentice Hall, Inc., Upper Saddle River, 1998, p. 230.
- C. B. Chen and F. Lu, “Computer Graphics Basis,” Publishing House of Electronics Industry, Beijing, 2006, pp. 167-168.
- V. Skala, “O (lg N) Line clipping Algorithm in E2,” Computers and Graphics, Vol. 18, No. 4, 1994, pp. 517- 527.
- Y. D. Liang and B. A. Barsky, “The Optimal Tree Algorithm for Line Clipping,” Technical Paper Distributed at Eurographics’92 Conference, Cambridge, 1992, pp. 1-38.
- V. Skala, “A New Approach to Line and Line Segment Clipping in Homogeneous Coordinates,” Visual Computer, Vol. 21, No. 11, 2005, pp. 905-914.
- Y. D. Liang, B. A. Barsky and M. Slater, “Some Improvements to a Parametric Line Clipping Algorithm,” Technical Report No. UCB/CSD 92/688, Computer Science Division, University of California, Berkeley, 1992, pp. 1-22.