# The Optimal Tree Algorithm for Line Clipping

### You-Dong Liang and Brian A. Barsky

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-92-691

July 1992

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-691.pdf

This paper develops a new algorithm for line clipping based on the concept of the optimal tree. A careful analysis results in an algorithm that classifies a given line segment in such a way that at most one procedure is invoked to clip it; furthermore, there are five such procedures that cover all cases. The result is an algorithm that is provably optimal and according to experimental tests outperforms previous algorithms. For both the two-dimensional and three-dimensional cases, and on both the Sun 3/160 and the DECStation 5000/200, the new algorithm performed uniformly faster than all the other "standard" algorithms for each of four different sizes of data space. Only the two-dimensional case is described in detail. Although in the three-dimensional case this algorithm is significantly faster than the other known algorithms, the code is huge and more complex than the new two-dimensional algorithm, and there are more special cases that need to be handled.

BibTeX citation:

@techreport{Liang:CSD-92-691, Author = {Liang, You-Dong and Barsky, Brian A.}, Title = {The Optimal Tree Algorithm for Line Clipping}, Institution = {EECS Department, University of California, Berkeley}, Year = {1992}, Month = {Jul}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6246.html}, Number = {UCB/CSD-92-691}, Abstract = {This paper develops a new algorithm for line clipping based on the concept of the optimal tree. A careful analysis results in an algorithm that classifies a given line segment in such a way that at most one procedure is invoked to clip it; furthermore, there are five such procedures that cover all cases. The result is an algorithm that is provably optimal and according to experimental tests outperforms previous algorithms. For both the two-dimensional and three-dimensional cases, and on both the Sun 3/160 and the DECStation 5000/200, the new algorithm performed uniformly faster than all the other "standard" algorithms for each of four different sizes of data space. Only the two-dimensional case is described in detail. Although in the three-dimensional case this algorithm is significantly faster than the other known algorithms, the code is huge and more complex than the new two-dimensional algorithm, and there are more special cases that need to be handled.} }

EndNote citation:

%0 Report %A Liang, You-Dong %A Barsky, Brian A. %T The Optimal Tree Algorithm for Line Clipping %I EECS Department, University of California, Berkeley %D 1992 %@ UCB/CSD-92-691 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1992/6246.html %F Liang:CSD-92-691