×

The irregular nesting problem: a new approach for nofit polygon calculation. (English) Zbl 1136.65029

Summary: This paper presents a new approach for generating the no-fit 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.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
52A39 Mixed volumes and related topics in convex geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

TOPOS
PDFBibTeX XMLCite
Full Text: DOI