The Nicholl-Lee-Nicholl (NLN) algorithm for clipping line segments against a rectangular window in the plane (Computer Graphics 21,4 pp 253-262) was proved to be optimal recently in terms of the minimum and maximum number of comparisons and the number of predicates used. A new algorithm is proposed that does not use predicates, but calculates intersections speculatively. Surprisingly, this approach not only leads to a much simpler algorithm, but also takes fewer operations in many cases, including the worst case. It is proved that the new algorithm never takes more operations than the optimal algorithm. Experimental results demonstrate that the new algorithm is 80% to 560% faster than long-established, widely known algorithms.
展开▼
