EdgeBreaker 壓縮算法是一個數學算法。
基本介紹
- 中文名：EdgeBreaker 壓縮算法
- 所屬學科：數學
Edg ebreaker 算法的格線遍歷過程是基於區域增長原理的: 在遍歷格線過程中要始終維持一個由邊組成的有向邊界, 這個邊界把格線分成已遍歷部分和未遍歷部分, 然後每遍歷一個多邊形, 則輸出一個該多邊形和邊界的拓撲關係操作( 符) , 並把該多邊形歸入已編碼部分 其具體遍歷過程如下: 先選擇任意一個三角形形成最初的邊界, 再選擇任意一條邊為當前邊Edgebreaker 算法採用5 個操作符C , L , E , R 和S 記錄當前三角形與邊界的拓撲關係, 其中, C 表示第3 頂點不在邊界上的拓撲情況;L 和R 表示第3 頂點在邊界上且當前三角形除了當前邊外還有一條邊( e) 在邊界上, L 和R 分別表示e 在當前邊的不同方向; 使用S 把圖形分成2 部分, 同時需要用額外的偏移或其他操作記錄分支信息; E 表示三角形的3 條邊都在邊界上 圖1 所示為C, L , E , R 和S , 其中, 深灰色部分為格線已遍歷部分, 白色部分為格線未遍歷部分, 深灰色和白色的分界線為邊界; 黑實邊為當前邊; 淺灰色三角形為當前三角形, 其被遍歷後歸入深灰色部分; 黑色大圓點為第3 頂點; 黑虛線表示下一個當前邊 圖2 所示為該算法壓縮過程示意圖, 圖中帶箭頭黑色線段表示三角格線遍歷順序, 其中有分支的地方是S 操作( 把圖形分成2 部分) 圖2 的最後遍歷結果為CCRCRSERCSCRRCRRRERC RCRCRRRLL R L ( 最後的E 操作可省略) , 共有31個操作符 獲取操作符序列後,Edgebreaker 算法採用霍夫曼編碼對其壓縮得到最終的壓縮結果
EdgeBreaker 壓縮算法
