[發明專利]基于二元組塊樹的矩形優化排樣方法及裝置

在審

• 申請號: 202010796212.0
• 申請日: 2020-08-10
• 公開（公告）號: CN111932011A
• 公開（公告）日: 2020-11-13
• 發明（設計）人: 陸宇升;廖淑珍;黃晴
• 申請（專利權）人: 南寧市永恒影像有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京細軟智谷知識產權代理有限責任公司 11471
• 代理人: 岳鳳羽

本發明涉及一種基于二元組塊樹的矩形件優化排樣方法及裝置，該方法基于預設映射關系，屬于矩形優化排列技術領域，該方法及裝置，將目標板材坐標映射為預設分辨率位圖坐標；根據矩形件集合和預設組合規則，在預設分辨率位圖坐標上構造二元組塊樹；基于目標板材坐標，獲取二元組塊樹的根節點的實例，確定矩形件集合的排樣結果。通過將目標板材坐標映射到預設分辨率位圖坐標，克服了現有基于二元組塊樹的排樣技術的不足，減少生成的二元組塊數量，避免因為消耗過多計算機內存資源導致的排樣失敗。

技術領域

本發明屬于矩形優化排列技術領域，具體涉及一種基于二元組塊樹的矩形優化排樣方法及裝置。

背景技術

矩形件排樣優化的問題是指將一系列規格大小不一的矩形件原料在矩形區域中按最優方式進行排布，使零件排放在矩形區域內，各個零件互不重疊，并滿足相應的工藝要求，從而盡可能多地排放所需的矩形件，以使材料的利用率達到最高。此類問題廣泛地存在現實生產中，如鈑金下料、造紙工業、玻璃切割、家具生產、印刷、照片沖印等各行業中。當前社會的發展對于資源的消耗日益增大，特別對于鋼材、紙張等工業原料的需求越來越大。提高原材料的利用率對于保護生態環境，提高企業的生產率進而獲得更大的經濟效益具有重大意義。

通常矩形件排樣優化問題屬于NP(Non-deterministic Polynomial Complete，多項式復雜程度的非確定性)完全問題，無法在短時間內求得最優解。現有的排樣方法通常采用啟發式算法，例如遺傳算法，模擬退火算法，蟻群算法，粒子群算法等，再結合某種排布規則，例如BL算法，最低水平線算法，分層排布算法等。

但是，在現有的很多矩形件排樣應用場景中，存在尺寸很大的矩形件，而且數量多，矩形件尺寸規格多，從而導致啟發式算法搜索空間太大，有限時間內無法找到理想目標板材利用率的排樣方案的技術問題。而一些基于二元組塊樹的排樣技術雖然在很多場景下獲得很好的效果，但在計算機內存資源消耗過量時，存在排樣失敗的可能。因此，如何解決二元組塊樹排樣技術因在計算機內存資源消耗過量時，存在排樣失敗的可能的問題，成為現有技術中亟待解決的問題。

發明內容

為了至少解決現有技術存在的上述問題，本發明提供了一種基于二元組塊樹的矩形優化排樣方法及裝置，以克服基于二元組塊樹的排樣技術的不足，減少生成的二元組塊數量，避免因為消耗過多計算機內存資源導致的排樣失敗。

本發明提供的技術方案如下：

一方面，一種基于二元組塊樹的矩形件優化排樣方法，包括：

基于預設映射關系，將目標板材坐標映射為預設分辨率位圖坐標；

根據矩形件集合和預設組合規則，在所述預設分辨率位圖坐標上構造二元組塊樹；

基于所述目標板材坐標，獲取所述二元組塊樹的根節點的實例，確定所述矩形件集合的排樣結果。

可選的，還包括：

基于預設處理方法，對殘留矩形件進行處理。

可選的，所述根據矩形件集合和預設組合規則，在所述預設分辨率位圖坐標上構造二元組塊樹，包括：

確定矩形節點R_i＝(w_i,h_i,PS_i,GS_i)，其中w_i為矩形件寬度，h_i為矩形件高度；PS_i為矩形件集合的子集，包含所有寬度高度為(w_i,h_i)的所有矩形件；GS_i為二元組塊的子集，包含所有寬度高度等于(w_i,h_i)的所有二元組塊集合；

利用xreduce函數或yreduce函數計算每個矩形件Pi在所述預設分辨率位圖坐標上的寬度w’和高度h’；