三角形是隨機的，大小，形狀沒有任何規律。
三角形不能分割，縮放，切變。可以旋轉，平移甚至反轉。
三角形數量已知。
平鋪的矩形理論上可以無限延申。
把三角形平鋪到矩形里面。如何使矩形最小化
原帖：https://bbs.csdn.net/topics/392391959。
我覺得原帖的問題不太好。所以另外再發一貼。
uj5u.com熱心網友回復：
排料問題大牛:http://www2.stetson.edu/~efriedma/packing.html
從這個鏈接的內容可以看出，最優解是不可能僅通過計算得出的。
uj5u.com熱心網友回復：
我又沒有說不能用回圈。
如果使用暴力列舉的話，時間復雜度有太厲害
如果角度精確到 0.1度的話 時間復雜度O( (N * 3600) ^ 2 )
1W個三角形就算使用顯卡去計算的話也要很久吧，而且不太精確
uj5u.com熱心網友回復：
關鍵是用暴利列舉和計算的大方向就是錯誤的。
uj5u.com熱心網友回復：
暴力
uj5u.com熱心網友回復：
我理解為應該按最小的面積，逐漸x y依次增加一像素到達最優
比如有三個三角形，先按最大的三角形設定一個矩形，然后看其他另個在該矩形剩余空間內是否可以放下(假設長寬為x y)，不能的話，先X方向增加一像素,那么矩形大小為x+1,y，不行的話，X方向不增加,y方向增加一像素(x, y+1)，然后還不行的話(x+1,y+1)依次類推
uj5u.com熱心網友回復：
性能不達標？并行計算？
uj5u.com熱心網友回復：
之前做了一個，比手工排的結果要好。效率在一秒以內。玻璃切割的。
uj5u.com熱心網友回復：
計算這條路就是錯的！我覺得。
uj5u.com熱心網友回復：
一秒？！數量很多？
uj5u.com熱心網友回復：
那只能說明你手工排的時候所用人腦的智商不夠高。
有本事你用程式排哪怕一個比我發的那個排料問題大牛鏈接中更好的，我就水土不服，就服你！
uj5u.com熱心網友回復：
你那個圖形太簡單了。玻璃表面有一些瑕疵，有的是一片，有的一個點。這些都需要避開。
uj5u.com熱心網友回復：
在同樣的排版時間內，比人工排要好。
網上有一個裁切布料的。好象很牛。你可以試試。就目前我知道，在裁布料的里面，機器的排版比人工排還要底很多。
uj5u.com熱心網友回復：
有專門研究排版演算法的。好象進展不大。不知道AI可不可以。市場前景還是相當大的。比如布料，皮革，每提升一個點的使用率，那是多大的市場啊。
uj5u.com熱心網友回復：
哇偶，你就排一個更好的看看唄
uj5u.com熱心網友回復：
如果顏色確定的話可以用顏色找。
假如影像是100*100的，背景是白色，三角是其他色
從第0行開始往下找，第一個行里有其他色的是矩形的第一個邊
從第99行開始往上找，第一個行里有其他色的是矩形的第二個邊
從第0列往右找，第一個列里有其他色的是矩形的第三個邊
從第99列往左找，第一個列里有其他色的是矩形的第四個邊
uj5u.com熱心網友回復：
我是沒那個本事了。
如果這方面比較優秀的。可以把演算法賣給 gerber cutter 。要價可以高些（可以考慮一千萬
）。
uj5u.com熱心網友回復：
1千萬，這東西有那么值錢么。學過圖論什么的應該寫出來不難吧。
用暴力法也是能搞出來的
uj5u.com熱心網友回復：
這是現實中的皮革的。圖左邊是牛皮，牛皮很多洞，（洞的形成比較蟲咬，破皮，乳頭，打架等）
圖右邊是現實中汽車皮革要裁切的形裁。比如一輛寶馬。遠不止，這么多。這些形材中間有需要會有各種洞的需要。
目前世界最先近的gerber cutter的計算機自動排版在78%左右吧。人工的在85%左右，利用率。gerber cutter中檔的一臺設備的價格在40萬美金吧。
uj5u.com熱心網友回復：
上面的我畫的圖是你可以試下。
uj5u.com熱心網友回復：
趙老師，有空試試上面我畫的圖
uj5u.com熱心網友回復：
反正我堅信，用演算法（包括用所謂BIGDATA＋ML＋AI號稱能超越人腦的演算法）計算出來的結果，永遠無法和真正人類專家根據多年從業經驗手動排出的結果相媲美。
uj5u.com熱心網友回復：
不能分割，縮放，切變。可以旋轉，平移甚至反轉
uj5u.com熱心網友回復：
我覺得這題讓小度機器人團隊來做應該會好一點
uj5u.com熱心網友回復：
感覺聞到了遺傳演算法的味道。不過難點是交叉模型不好選擇。
若把所有三角形的坐標作為引數，矩形面積作為輸出，用梯度下降法進行搜索。可變引數太多了。
uj5u.com熱心網友回復：
現在搞成這樣，還需要修改
uj5u.com熱心網友回復：
剛剛發現了BUG，修改了一下，挺符合預期的
uj5u.com熱心網友回復：
又修改了一下
uj5u.com熱心網友回復：
沒看到 “矩形最小化 “ 了 ！
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/67049.html
標籤：圖形處理/算法
上一篇：求助—在使用vs2013創建的工程里添加資源檔案出現未知錯誤
下一篇：基于opencv人臉檢測，檢測視頻中的人臉如何減少發生的錯誤，漏檢問題。
