?2016-2026 Matools All rights reserved,
粵ICP備17059708號
?
Liang-Barsky算法
在Cohen-Sutherland算法提出后，梁友棟和Barsky又針對標(biāo)準(zhǔn)矩形窗口提出了更快的Liang-Barsky直線段裁剪算法。
梁算法的主要思想：
（1）用參數(shù)方程表示一條直線
（2）把被裁剪的紅色直線段看 成是一條有方向的線段，把窗口 的四條邊分成兩類：
入邊和出邊
?
裁剪結(jié)果的線段起點是直線和兩條入邊的交點以及始端點三 個點里最前面的一個點，即參數(shù)u最大的那個點；
裁剪線段的終點是和兩條出邊的交點以及端點最后面的一個 點，取參數(shù)u最小的那個點。
值得注意的是，當(dāng)u從-∞到+∞遍歷直線時，首先對裁剪窗口的兩條邊界直線（下邊和左邊）從外面向里面移動，
再對裁 剪窗口兩條邊界直線（上邊和右邊）從里面向外面移動。
?
如果用u1，u2分別表示 線段（u1≤u2）可見部分的開始和結(jié)束
Liang-Barsky算法的基本出發(fā)點是直線的參數(shù)方程
?
?
（1）分析Pk=0的情況
如果還滿足qk<0
則線段完全在邊界外，應(yīng)舍 棄該線段
如果qk≥0
則進一步判斷
（2）當(dāng)pk≠0時：
當(dāng)pk<0時
線段從裁剪邊界延長線的外部 延伸到內(nèi)部，是入邊交點
當(dāng)pk > 0時
線段從裁剪邊界延長線的內(nèi)部 延伸到外部，是出邊交點
線段和窗口邊界一共有四個交點，根據(jù)pk的符號，就知道 哪兩個是入交點，哪兩個是出交點
當(dāng)p k < 0時：對應(yīng)入邊交點
當(dāng)p k > 0時：對應(yīng)出邊交點
一共四個u值，再加上u=0、u=1兩個端點值，總共六個值
把pk＜0的兩個u值和0比較去找最大的，把pk＞0的兩個u值 和1比較去找最小的，這樣就得到兩個端點的參數(shù)值
?
?
?
熱門工具 換一換