The irregular nesting problem: a new approach for nofit polygon calculation

L Huyao (), H Yuanjun () and J A Bennell
Additional contact information
L Huyao: Shanghai Jiaotong University
H Yuanjun: Shanghai Jiaotong University
J A Bennell: University of Southampton

Journal of the Operational Research Society, 2007, vol. 58, issue 9, 1235-1245

Abstract: Abstract This paper presents a new approach for generating the nofit polygon (NFP) that is simple, intuitive and computationally efficient. The NFP has in recent years become an important tool for handling the geometric calculations for two-dimensional irregular shape nesting problems. Its value lies in reducing the computational complexity of detecting whether two polygons overlap. The proposed NFP generator is based on the novel concept of trace line segments that are derived from the interaction of the two-component polygons. The complete set of the trace line segments contain all the boundary edges of the NFP and some internal points that need to be discarded. Algorithms for deriving the trace line segments, efficiently determining those segments that form the boundary of the NFP and the identification of holes and degenerate cases are described.

Keywords: cutting stock problem; nesting; nofit polygon; trace line segment; index algorithm (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602255 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:58:y:2007:i:9:d:10.1057_palgrave.jors.2602255

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602255

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().