梁友棟-柏世奇算法

梁友棟—柏世奇算法（以梁友棟佮柏世奇的名號名）是算機圖形學中的一个線段裁剪算法。梁友棟—柏世奇算法使用直線的參數方程和不等式組來描述線段和裁剪窗仔口的交集。求解出的交集將被用於知影線的佗一寡部份是應當畫圖佇屏幕頂懸的。這一算法比科恩－蘇澤蘭算法（Cohen-Sutherland algorithm）愛閣較高效，梁友棟—柏世奇算法的基本思想講：佇計算線段佮裁剪窗交集進前做雖然可能加的判斷。

算法講

考慮直線的參數方式：

$ x=x _ { 零 } + t ( x _ { 一 }-x _ { 零 } )=x _ { 零 } + t \ Delta x , $

$ y=y _ { 零 } + t ( y _ { 一 }-y _ { 零 } )=y _ { 零 } + t \ Delta y . $

點佇裁剪窗仔內，若是

$ x _ { \ text { min } } \ leq x _ { 零 } + t \ Delta x \ leq x _ { \ text { max } } $

而且

$ y _ { \ text { min } } \ leq y _ { 零 } + t \ Delta y \ leq y _ { \ text { max } } , $

其實是會當用四个不等式表達：

$ tp _ { i } \ leq q _ { i } , \ quad i=一 , 二 , 三 , 四 , $

其中

$ { \ begin { aligned } p _ { 一 } &=-\ Delta x , & q _ { 一 } &=x _ { 零 }-x _ { \ text { min } } , & & { \ text { ( 倒 ) } } \ \ p _ { 二 } &=\ Delta x , & q _ { 二 } &=x _ { \ text { max } }-x _ { 零 } , & & { \ text { ( 正 ) } } \ \ p _ { 三 } &=-\ Delta y , & q _ { 三 } &=y _ { 零 }-y _ { \ text { min } } , & & { \ text { ( 落 ) } } \ \ p _ { 四 } &=\ Delta y , & q _ { 四 } &=y _ { \ text { max } }-y _ { 零 } . & & { \ text { ( 上 ) } } \ end { aligned } } $

算最終線段：

一 . 和裁剪窗平行的直線佇邊仔內底有 $ p _ { i }=零 $ 二 . 若對著這款的 $ i $ $ q _ { i } < 零 $，則線段全部咧裁剪窗仔的外口，會當去予人消除三 . 當 $ p _ { i } < 零 $ 時，線對裁剪窗仔外向內行；$ p _ { i } > 零 $ 四 . 嘿無空的 $ p _ { k } $ , $ u=q _ { i } / p _ { i } $ 五 . 著每一條線，計算 $ u _ { 一 } $ 和 $ u _ { 二 } $。著 $ u _ { 一 } $ 檢查 $ p _ { i } < 零 $ 的邊界（即對外向內底）。令 $ u _ { 一 } $ 為 $ \ { 零 , q _ { i } / p _ { i } \ } $ $ u _ { 二 } $ 檢查 $ p _ { i } > 零 $ 的邊界（也對外口）。令 $ u _ { 二 } $ 為 $ \ { 一 , q _ { i } / p _ { i } \ } $ $ u _ { 一 } > u _ { 二 } $

示例代碼

參見

其他裁剪算法：

科恩－蘇澤蘭算法
Cyrus–Beck 算法
Nicholl–Lee–Nicholl 算法
快速裁剪

參考文獻

Liang , Y . D . , and Barsky , B . , " A New Concept and Method for Line Clipping " , _ ACM Transactions on Graphics _ , 三 ( 一 ) : 一–二十二 , January 一千九百八十四 .
Liang , Y . D . , B . A . , Barsky , and M . Slater , _ Some Improvements to a Parametric Line Clipping Algorithm _ , CSD 被九十二交六百八十八 , Computer Science Division , University of California , Berkeley , 一千九百九十二 .
James D . Foley . _ Computer graphics : principles and practice _ . Addison-Wesley Professional , 九百九十六 . p . 一百十七喔 .

外部連結

http : / / hinjang . com / articles / 四 . html # eight
Skytopia : The Liang-Barsky line clipping algorithm in a nutshell !