一種基于Ghosh斜率圖法的改進的臨界多邊形生成算法

排樣問題就是在給定的布局空間內，按最優化組合的方式將待排物體按照一定的約束條件合理地放置在布局空間中，并使原材料利用率達到最高。此問題普遍存在于船舶、服裝、皮革等行業生產過程中。多邊形的最優靠接位置的求解問題以及重疊判斷問題，是排樣問題中需要重復計算的最關鍵問題。現有的許多算法中采用繁復的線一線判交、求各頂點碰撞距離、確定碰撞區域等步驟來解決，但因其繁瑣冗余，使得算法的速度無法得到突破。而臨界多邊形的計算和應用，可以避免大量重復的判交、碰撞步驟，使得此問題得到高效地解決。快速求解NfP，已成為排樣算法中最關鍵的問題，其算法的效率、快速性將對整個排樣優化算法起著重要的影響。因此，研究NPP的求解具有重要的學術理論價值和實踐意義。