查詢結果分析
來源資料
頁籤選單縮合
題名 | 有效率的二維多邊形切割演算法 |
---|---|
作 者 | 黃竹明; 林宗興; | 書刊名 | 技術學刊 |
卷期 | 9:4 1994.12[民83.12] |
頁次 | 頁379-382 |
分類號 | 440.11 |
關鍵詞 | 電腦圖形學; 多邊形; 切割; 演算法; Computer graphics; Polygon; Clipping; Algorithm; |
語文 | 中文(Chinese) |
中文摘要 | 多邊形切割演算法,在1974年首先由Sutherland和Hodgman(SH)所提出。SH演算法是利用外積法來判斷點的位置是落在線段的左邊或是右邊,它需要較多的乘除運算來執行多邊形的切割。為了減少乘除運算次數,Liang和Barsky(LB)提出參數直線方程式法,它的乘除運算次數幾乎是SH演算法的一半。然而,SH及LB兩種演算法都有同樣的限制─「只能切割凸多邊形」,這種限制嚴重影響它的應用範圍。本論文提出一個以參數直線方程式法為架構的切割凹凸多邊形演算法。這個演算法的乘除運算次數與LB演算法相同,但它改善了LB演算法無法切割凹多邊形的缺點。一般而言,本論文所提之演算法比SH和DLB演算法更能有效率地的切割各種多邊形。 |
英文摘要 | SH algorithm, issued by Sutherland and Hodgman(SH) in 1974, used Cross-Product method to tell whether a certain point lies on the left or right side of a line segment. This particular algorithm needs a lot of mul./div. operations in order to carry out the polygon clippings. Later on, LiangBarsky(LB) introduced the Parameter Line Equation method whose execution time is almost half of that of SH algorithm's. However, both SH and LB algorithms have similar constraint that both of them can only be used to clip the convex polygons. The application is severely restricted accordingly. Based on the structure of the Parameter Line Equation, an algorithm able to clip both convex and concave polygons is hereby proposed in this paper. The algorithm not only improves SH and LB algorithms, but also has the same execution speed as the LB algorithm. In general, the performance of the proposed algorithm has proven to be better than SH and LB algorithms. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。