An improved method for calculating the no-fit polygon

An improved method for calculating the no-fit polygon

0.00 Avg rating0 Votes
Article ID: iaor20071867
Country: United Kingdom
Volume: 33
Issue: 6
Start Page Number: 1521
End Page Number: 1539
Publication Date: Jun 2006
Journal: Computers and Operations Research
Authors: , ,
Keywords: packing, robots
Abstract:

The no-fit polygon (NFP) is the set of feasible locations that one polygon may take with respect to another polygon, such that the polygons do not overlap. Feasible locations are required for most of the solutions to two-dimensional packing problems, and also for other problems such as robot motion planning. Efficient methods to calculate the NFP of two convex polygons, or one convex and one non-convex polygon have been developed by other researchers. However, when both polygons are non-convex, the current methods of calculation are inefficient or difficult to implement. This paper presents an extension of Ghosh's NFP algorithm, and uses manipulation of sorted lists of polygon edges to find the NFP efficiently.

Reviews

Required fields are marked *. Your email address will not be published.