二维线段裁剪的概率模型

Probability Model for 2D Line Clipping

相对于矩形窗口的二维线段裁剪是计算机图形学中的基本操作之一 ,已有多种裁剪算法 .由于这些算法在不同情况下各具优劣 ,一般只能分不同情况比较算法的性能 ,无法比较算法的平均性能 .本文首先分析了线段与窗口之间位置关系的概率分布 ,从而得到二维线段裁剪的概率模型 .接着使用该模型计算出一些常用算法的平均运算次数 ,并对算法的平均性能进行比较 .

D line segment clipping (line clipping) against a rectangular window is a basic operation in computer graphics. So far a lot of clipping algorithms have been proposed. Since different algorithms have superiority and inferiority in different conditions, we have to compare their performances in different conditions and can not compare their average performances. In this paper we analyze the probability distribution of the relative positions between the line segment and the window, and get the probability model for 2D line clipping. Then we use this model to calculate the average amounts of computations of some widely used algorithms and compare their average performances. This model also corrects some incorrect viewpoints about the probability distribution of the relative positions between the line segment and the window in some papers.