[問題] 請問一下Polygon Clipping的相關演算法

[ccbruce (今、そこに いる僕)]

※ [本文轉錄自 Prob_Solve 看板]

作者: ccbruce (今、そこに　いる僕) 看板: Prob_Solve
標題: [問題] 請問一下Polygon Clipping的相關演算法
時間: Wed Mar  5 22:08:10 2008

有沒有網站有比較多這方面的參考資料。

是這樣的，因為我想要在寫出一個視窗能「半透明」的程式。在Vista有DWM可用；在WinXP
雖有Layered Window可用，但是並不好用，老實講，很難用。

如果要回歸傳統，就要想辦法抓出「蓋在半透明視窗下面的所有視窗」的畫面，把它們一
個個地由下往上疊，再畫上自己視窗的半透明背景來得到半透明效果。

雖然這樣的想法很簡單，但是速度太慢，如果下面只有1, 2個視窗那還好，如果有10幾個
就會非常慢，所以必須有比較快的演算法來決定底下有哪些視窗該抓，哪些不用。

我的構想是把目前視窗的Rectangle當成Subject Polygon，而把下面每個視窗的Rectangle
當成Clipping Polygon，然後執行以下的迴圈：

Let S=The rectangle of my window
Let B=() ;The ordered set of windows

For each below window W
 Let C=The rectangle of W

 If Intersection(S, C)=Empty Set Then
  Continue

 S=S-Intersection(S, C)
 B=B+W

 If S=Empty Set Then
  End Loop
Next

Return B

這裡想到可以加速的地方有：
1.跳過沒交集的視窗
2.Clipping Polygon永遠是矩形

最後，雖然我找到不少演算法是可以把它們交集算出來的，卻不知道怎麼樣才可以作到差
集。如果可以，我還想知道怎麼算聯集，這樣可以試另外的做法。

--
　　　　　　　　　　　　愛　哀　だ　百　は　こ　も　こ
　　　　　　　　　　　　し　し　か　億　か　ん　ろ　ん
　　　　　　　　　　　　い　い　ら　年　な　な　く　な
　　　　　　　　　　　　　　ほ　　　の　い　に　　　に
　　　　　　　　　　　　　　ど　　　年　　　も　　　も
　　　　　　　　　　　　　　に　　　月

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.146.83
※ 編輯: ccbruce         來自: 59.115.146.83        (03/05 22:10)