二維工件輪廓轉換成正交多邊形之演算法

Abstract

在影像處理、計算機圖學、語法型態辨認、超大型積體電路設計....等領 域中, 分解多邊形成為簡單形狀的集合扮演極為重要的角色, 分解方法可 分成分割及覆蓋二種。所謂簡單形狀通常係指長方形、 三角形、凸狀多 邊形、星狀多邊形...等。然而一般常見的圖形是由直線及圓弧所構成, 因此如何使用適當的多邊形來代替非多邊形圖形, 以便利用簡單形狀易被 處理的特性, 是項極為重要的課題。本研究係針對一般常見的二維工件 圖, 以儘可能維持工件的外形及面積大小為原則, 先將工件圖輪廓轉換成 與其近似的多邊形, 再將多邊形轉換成與其近似的正交多邊形。 其目的 是將來能分解該正交多邊形為可重疊的長方形, 每一個長方形以一段簡化 線骨架來表示, 以便進行工件的分類;文中所提出的方法可克服工件圖擺 向之問題, 以符合實際情況之需要。