The Optimal Tree Algorithm for Line Clipping

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
```