TWI616271B

TWI616271B - 向量物件擴張與排版方法

Info

Publication number: TWI616271B
Application number: TW106115323A
Authority: TW
Inventors: 林泓宏; 黃仲廷; 蘇嘉祥
Original assignee: 南臺科技大學
Priority date: 2017-05-09
Filing date: 2017-05-09
Publication date: 2018-03-01
Also published as: TW201900327A

Abstract

本發明為一種向量物件擴張與排版方法。所述擴張方法為：I.沿一物件的一輪廓線取得多個向量座標點a_i；II.假設該物件與另一物件之間要保留的裁切間距為D，則該物件要擴張的距離d為D/2；III.以向量座標點a_i為交點之相鄰線段往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i；IV.獲得每一向量座標點a_i的實際擴張距離，組成一擴張輪廓線。所述排版方法為：I.使一物件為基準物件，另一物件為靠近物件；II.將該靠近物件往該基準物件靠近，直到該靠近物件接觸該基準物件，再繪製含該基準物件及該靠近物件之一最小外框；III.使該靠近物件自360度的方向往該基準物件靠近，以獲得多個最小外框；IV.取該多個最小外框之最小者為一排版外框。

Description

向量物件擴張與排版方法

本發明係有關於一種向量物件擴張與排版方法，特別是指在向量空間中，對裁切物件作物件擴張及物件排版的發明。

在作裁切物件的排版前，需要先對裁切物件作擴張計算，可以確保相鄰的裁切物件之間，能夠有足夠的裁切間隙，避免裁切時由於沖頭的定位誤差，造成裁切物件部份缺損的問題。

傳統裁切物件的擴張是使用裁切物件的影像作影像像素的處理，是在有限精度下作Erosion/Dilation的計算。

物件擴張完成後，再進行排版。參閱第十一圖所示，為習知業界對裁切物件(A)採用人工排版的示意圖。習知以人工規劃裁切物件的布局方法不僅耗時也不夠精確，且以簡易排列的方式為之，其所空出之邊緣與間隙仍大，往往造成鋪料件的浪費。

爰此，本發明提出一種向量物件擴張與排版方法，是在向量空間中，對裁切物件作物件擴張及物件排版。

本發明之向量物件擴張方法包括下列步驟： I.沿著一物件的一輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}；II.給定該物件與另一物件之間要保留的裁切間距為D，則該物件要擴張的距離d為D/2；III.將以該向量座標點a_i為交點之相鄰線段L_i(a_i+1-a_i)及L_i-1(a_i-a_i-1)往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i；IV.重複執行步驟III，藉以獲得該輪廓線A上每一向量座標點a_i的實際擴張距離，計算組成一擴張輪廓線。

進一步，當該向量座標點a_i與相鄰的向量座標點a_i-1、a_i+1之線段L₁、L₂形成凸角，若該向量座標點a_i至該向量座標點b_i的長度s大於2倍d時，則採用s等於d的至少3個點來描述擴張後的外框；當該向量座標點a_i與相鄰的向量座標點a_i-1及a_i+1之線段L₁、L₂形成凹角時，若擴張後之向量座標點b_i形成凸角，則刪除該向量座標點a_i；當該物件的輪廓線擴張後之該擴張輪廓線產生交疊，則擷取該擴張輪廓線最外圍的輪廓作為新的擴張輪廓線。

進一步，該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|=dcscθ/2，若該向量座標點a_i至該向量座標點b_i的長度s大於2倍d時，則設定 s=d：，並採用至少3個點來描述擴張後的外框。更進一步，以3個點來描述擴張後的外框時，該3個點設定為b_i,b_i ^′,b_i ^〞，其中，

進一步，當該向量座標點a_i相鄰的向量座標點a_i-1及a_i+1形成凹角時，在夾角的角平分線上設定一臨界點，該向量座標點a_i至該臨界點的距離為，其中L為min{|L_i-1|,|L_i|}，若該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|大於Lsecθ/2，此時，則移除向量座標點a_i。

進一步，當該物件的輪廓線擴張後之該擴張輪廓線產生交疊，先計算該擴張輪廓線中，每條線的交疊，並將計算出的交點插入到點串列的兩條線之間，標注該點為交點並將該點與該點串列建立連接；接下來再找到一個能確定在該擴張輪廓線最外圍的點，從該點開始搜尋，每遇到交點則跳至連結點，否則繼續下一點；依照以上的規則就能取得外圍點的串列。

進一步，步驟III中，計算交點b_i時，先定義一逆時針旋轉矩陣，以三角函數求解該向量座標點a_i至該向量座標點b_i的向量；第一段向量V₁的方向垂直於L_i-1，長度固定為d，則；第二段向量 V₂的方向平行於L_i-1，長度為d/tan，其中，，，則向量座標點b_i=a_i+V₁+V₂。

本發明之向量物件排版方法，包括下列步驟：I.使二物件中，其中一物件為基準物件，另一物件為靠近物件；II.以該基準物件為中心，將該靠近物件往該基準物件靠近，直到該靠近物件接觸該基準物件，此時，繪製含該基準物件及該靠近物件之一最小外框；III.掃描360度範圍，使該靠近物件往該基準物件靠近，藉以獲得多個最小外框；IV.擷取該多個最小外框之最小者為一排版外框。

進一步，本發明之向量物件排版方法結合向量物件擴張方法，當要使該二物件靠近時，先對每一物件的一輪廓線作向量擴張，包括下列步驟： I.沿著每一物件的輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a_i,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}；II.假設該二物件之間要保留的裁切間距為D，則每一物件要擴張的距離d為D/2；III.將以該向量座標點a_i為交點之相鄰線段L_i(a_i+1-a_i)及L_i-1(a_i-a_i-1)往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i；IV.重複執行步驟III，藉以獲得每一向量座標點a_i的實際擴張距離，組成一擴張輪廓線，將該擴張輪廓線作為該物件新的輪廓線進行排版。

進一步，該靠近物件以相對該基準物件360度的各角度方向往該基準物件靠近，且在每一角度方向上，該靠近物件以本身旋轉360度的角度方位往該基準物件靠近。更進一步，使該基準物件與該靠近物件採用邊對角的方式靠近。所述邊對角的方式靠近係沿著每一物件的輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}，使該靠近物件的每一向量座標點a_i，往該基準物件的每一線段靠近，取得最小距離的向量座標點a_i及線段，即該靠近物件與該基準物件在該方位的最小靠近距離，該靠近物件與該基準物件以該最小靠近距離靠近後，可描繪該最小外框。

進一步，該最小外框之形狀為矩形。

進一步，以該二個物件為一群組，將多個群組之排版外框以水平或垂直方式堆疊。

透過上述技術特徵可產生以下功效：可於裁切工具機中精準計算物件裁切間隙，避免刀模裁切時造成物件過度裁切問題，相較於一般影像物件擴張，向量物件擴張法有更高的精確度和效率；同時，基於物件擴張結果，我們提出實用的緊密物件排版方法，能對各式多邊形物件作緊密排版，使裁切佈局上能有效利用材料，減少裁切料件浪費。

(1)‧‧‧基準物件

(2)‧‧‧靠近物件

(3)‧‧‧排版外框

(A)‧‧‧裁切物件

[第一圖]係為本發明的向量物件擴張示意圖。

[第二圖]係為本發明進行向量物件擴張時，產生凸角過凸的示意圖。

[第三圖]係針對第二圖當凸角過凸時的解決方案示意圖。

[第四圖]係為本發明進行向量物件擴張時，產生凹角變凸角的示意圖。

[第五圖]係為本發明進行向量物件擴張時，擴張輪廓線產生交疊的示意圖。

[第六圖]係針對第五圖當擴張輪廓線產生交疊時的解決方案示意圖。

[第七圖]係為本發明進行向量物件排版時，採用邊對角的靠近的示意圖。

[第八圖]係為本發明進行向量物件排版時，靠近物件以相對基準物件360度的各角度方向往基準物件靠近的示意圖。

[第九圖]係為本發明進行向量物件排版時，在每一角度方向上，靠近物件以本身旋轉360度的角度方位往基準物件靠近的示意圖。

[第十圖]係為本發明進行向量物件排版時，物件採用排版外框緊密排列的示意圖。

[第十一圖]係為習知排版型態示意圖。

綜合上述技術特徵，本發明向量物件擴張與排版方法的主要功效將可於下述實施例清楚呈現。

本實施例在進行欲裁切物件的排版時，先作物件的擴張，避免裁切刀具裁切到物件本身，其中，物件的擴張是在向量空間中進行。

參閱第一圖所示，向量物件擴張方法包括：I.沿著一物件的一輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}。II.給定該物件與另一物件之間要保留的裁切間距為D，則該物件要擴張的距離d為D/2。III.將以該向量座標點a_i為交點之相鄰線段L_i(a_i+1-a_i)及L_i-1(a_i-a_i-1)往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i，其中，在計算交點b_i時，先定義一逆時針旋轉矩陣，以三角函數求解該向量座標點a_i至該向量座標點b_i的向量；第一段向量V₁的方向垂直於L_i-1，長度固定為d，則；第二段向量 V₂的方向平行於L_i-1，長度為d/tan，其中，，，則向量座標點b_i=a_i+V₁+V₂。IV.重複執行步驟III，藉以獲得該輪廓線A上每一向量座標點a_i的實際擴張距離，計算組成一擴張輪廓線。

但是在進行向量物件擴張時，對於一些圖形可能產生三個問題，包括：1.凸角過凸、2.凹角變凸角、3.擴張輪廓線產生交疊。

參閱第二圖及第三圖所示，針對問題1之解決方案：該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|=dcscθ/2，若該向量座標點a_i至該向量座標點b_i的長度s大於2倍d時，則設定s=d：，並採用至少3個點來描述擴張後的外框。例如第三圖所示，以3個點來描述擴張後的外框時，該3個點設定為b_i,b_i ^′,b_i ^〞，，，

參閱第四圖所示，針對問題2之解決方案：當該向量座標點a_i與相鄰的向量座標點a_i-1及a_i+1形成凹角時，在夾角的角平分線上設定一臨界點，該向量座標點a_i至該臨界點的距離為，其中L為min{|L_i-1|,|L_i|}，若該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|大於Lsecθ/2，此時，則在所有向量座標點的串列中移除向量座標點a_i。

參閱第五圖及第六圖所示，針對問題3之解決方案：當該物件的輪廓線擴張後之該擴張輪廓線產生交疊，則擷取該擴張輪廓線最外圍的輪廓作為新的擴張輪廓線。例如第六圖中，該物件擴張後之擴張輪廓線的點串列為[1234567]，先計算該擴張輪廓線中，每條線的交疊，並將計算出的交點插入到點串列的兩條線之間，標注該點為交點並將該點與該點串列建立連接，形成點串列[12●▲3■★45★●6▲■7]；接下來再找到一個能確定在該擴張輪廓線最外圍的點，例如圖示中點1，從該點開始搜尋，每遇到交點則跳至連結點，否則繼續下一點，例如點1開始後接續為點2，點2之後遇到交點●即跳至連結點 6，連結點6之後接續為交點▲，再跳至連結點3，連結點3之後為交點■，再跳至連結點7，依照以上的規則就能取得該擴張輪廓線最外圍的輪廓的點串列[12●6▲3■7]。

當欲裁切的物件完成擴張後，進行物件排版，同樣的，物件排版是在向量空間中進行。

向量物件排版方法包括下列步驟：

I.參閱第七圖所示，使二物件中，其中一物件為基準物件(1)，另一物件為靠近物件(2)。

II.以該基準物件(1)為中心，將該靠近物件(2)往該基準物件(1)靠近，直到該靠近物件(2)接觸該基準物件(1)，此時，繪製含該基準物件(1)及該靠近物件(2)之一最小外框，其中，使該基準物件(1)與該靠近物件(2)採用邊對角的方式靠近。所述邊對角的方式靠近係沿著每一物件的輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}，使該靠近物件的每一向量座標點a_i，往該基準物件的每一線段靠近，取得最小距離D的向量座標點a_i及線段，即該靠近物件(2)與該基準物件(1)在該方位的最小靠近距離，該靠近物件(2)與該基準物件(1)以該最小靠近距離靠近後，可描繪該最小外框。

III.參閱第八圖及第九圖所示，掃描360度範圍，使該靠近物件(2)往該基準物件(1)靠近，藉以獲得多個最小外框。其中，如第八圖所示，該靠近物件(2)以相對該基準物件(1)360度的各角度方向往該基準物件(1)靠近。再如第九圖所示，且在每一角度方向上，該靠近物件(2)以本身旋轉360度的角度方位往該基準物件(1)靠近。藉此獲得該靠近物件(2)與該基準物件(1)在任一方向及位置的最小外框。

IV.參閱第十圖所示，擷取該多個最小外框之最小者為一排版外框(3)，以該二個物件為一群組，將多個群組之排版外框(3)以水平或垂直方式堆疊，因此，該最小外框之形狀為矩形，方便作最密的堆疊。

透過本發明方法，物件的擴張可達成前述更高的精確度和效率的功效；並且物件的排版可達到更緊密的效果。

綜合上述實施例之說明，當可充分瞭解本發明之操作、使用及本發明產生之功效，惟以上所述實施例僅係為本發明之較佳實施例，當不能以此限定本發明實施之範圍，即依本發明申請專利範圍及發明說明內容所作簡單的等效變化與修飾，皆屬本發明涵蓋之範圍內。

Claims

一種向量物件擴張方法，包括下列步驟：I.沿著一物件的一輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}；II.給定該物件與另一物件之間要保留的裁切間距為D，則該物件要擴張的距離d為D/2；III.將以該向量座標點a_i為交點之相鄰線段L_i及L_i-1往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i；IV.重複執行步驟III，藉以獲得該輪廓線A上每一向量座標點a_i的實際擴張距離，計算組成一擴張輪廓線。
如申請專利範圍第1項所述之向量物件擴張方法，進一步，當該向量座標點a_i與相鄰的向量座標點a_i-1、a_i+1之線段L₁、L₂形成凸角，若該向量座標點a_i至該向量座標點b_i的長度s大於2倍d時，則採用s等於d的至少3個點來描述擴張後的外框；當該向量座標點a_i與相鄰的向量座標點a_i-1及a_i+1之線段L₁、L₂形成凹角時，若擴張後之向量座標點b_i形成凸角，則刪除該向量座標點a_i；當該物件的輪廓線擴張後之該擴張輪廓線產生交疊，則擷取該擴張輪廓線最外圍的輪廓作為新的擴張輪廓線；其中，該凸角或該凹角的角度為θ。
如申請專利範圍第1項所述之向量物件擴張方法，其中，步驟III中，計算交點b_i時，先定義一逆時針旋轉矩陣，以三角函數求解該向量座標點a_i至該向量座標點b_i的向量；第一段向量V₁的方向垂直於L_i-1，長度固定為d，則；第二段向量V₂的方向平行於L_i-1，長度為d/tan，其中，，，則向量座標點b_i=a_i+V₁+V₂。
如申請專利範圍第2項所述之向量物件擴張方法，其中，該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|=dcscθ/2，若該向量座標點a_i至該向量座標點b_i的長度s大於2倍d時，則設定s=d：，並採用至少3個點來描述擴張後的外框。
如申請專利範圍第4項所述之向量物件擴張方法，其中，以3個點來描述擴張後的外框時，該3個點設定為b_i,b_i ^′,b_i ^〞，其中，，b_i=a_i+，，是一逆時針旋轉矩陣。
如申請專利範圍第2項所述之向量物件擴張方法，其中，當該向量座標點a_i相鄰的向量座標點a_i-1及a_i+1形成凹角時，在夾角的角平分線上設定一臨界點，該向量座標點a_i至該臨界點的距離為，其中L為min{|L_i-1|,|L_i|}，若該向量座標點a_i至該向量座標點b_i的長度s=|b_i-a_i|大於Lsecθ/2，此時，則移除向量座標點a_i。
如申請專利範圍第2項所述之向量物件擴張方法，其中，當該物件的輪廓線擴張後之該擴張輪廓線產生交疊，先計算該擴張輪廓線中，每條線的交疊，並將計算出的交點插入到點串列的兩條線之間，標注該點為交點並將該點與該點串列建立連接；接下來再找到一個能確定在該擴張輪廓線最外圍的點，從該點開始搜尋，每遇到交點則跳至連結點，否則繼續下一點；依照以上的規則就能取得外圍點的串列。
一種向量物件排版方法，包括下列步驟：I.使二物件中，其中一物件為基準物件，另一物件為靠近物件；II.以該基準物件為中心，將該靠近物件往該基準物件靠近，直到該靠近物件接觸該基準物件，此時，繪製含該基準物件及該靠近物件之一最小外框；III.掃描360度範圍，使該靠近物件往該基準物件靠近，藉以獲得多個最小外框；IV.擷取該多個最小外框之最小者為一排版外框。
如申請專利範圍第8項所述之向量物件排版方法，其中，要使該二物件靠近時，先對每一物件的一輪廓線作向量擴張，包括下列步驟：I.沿著每一物件的輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}；II.假設該二物件之間要保留的裁切間距為D，則每一物件要擴張的距離d為D/2；III.將以該向量座標點a_i為交點之相鄰線段L_i(a_i+1-a_i)及L_i-1(a_i-a_i-1)往外平移距離d之後，重新計算交點b_i之向量座標，以獲得該向量座標點a_i的實際擴張距離為b_i-a_i；IV.重複執行步驟III，藉以獲得每一向量座標點a_i的實際擴張距離，組成一擴張輪廓線，將該擴張輪廓線作為該物件新的輪廓線進行排版。
如申請專利範圍第8項所述之向量物件排版方法，其中，該靠近物件以相對該基準物件旋轉360度的方向往該基準物件靠近，且在每一方向上，該靠近物件以本身旋轉360的方位往該基準物件靠近。
如申請專利範圍第9項所述之向量物件排版方法，其中，使該基準物件與該靠近物件採用邊對角的方式靠近。
如申請專利範圍第11項所述之向量物件排版方法，其中，所述邊對角的方式靠近係沿著每一物件的輪廓線取得多個向量座標點，而將該輪廓線A表示為：A={a₁,a₂,a₃…a_n}，其中每一向量座標點a_i為平面座標點[x_i,y_i]^T，並且，與其中一向量座標點a_i相鄰的向量座標點為a_i-1及a_i+1，則該輪廓線表示為多個線段L={a₂-a₁,a₃-a₂,a₄-a₃…a_i-a_i-1…a_n-a_n-1,a₁-a_n}={L₁,L₂,L₃…L_i…L_n-1,L_n}，使該靠近物件的每一向量座標點a_i，往該基準物件的每一線段靠近，取得最小距離的向量座標點a_i及線段，即該靠近物件與該基準物件在該方位的最小靠近距離，該靠近物件與該基準物件以該最小靠近距離靠近後，可描繪該最小外框。
如申請專利範圍第8項所述之向量物件排版方法，其中，該最小外框之形狀為矩形。
如申請專利範圍第8項所述之向量物件排版方法，其中，以該二個物件為一群組，將多個群組之排版外框以水平或垂直方式堆疊。