New Algorithm for No Fit Polygon Calculation

In this paper,the problem of calculating movement of piece is simplified to the problem of finding track line segments between vertices and edges,hence the time complexity is much reduced,and special cases such as inner cavity and inner NFP （no fit polygon） can also be tackled.The main principles of this new approach are：1） Find out the track line segments for vertices of one polygon to another polygon’s edges；2） Get the enclosing polygon and internal clockwise loops that was formed by the track line segments,finally the result polygons are the final NFPs.This new approach adopts a grid-based line index algorithm which can facilitate the calculation of intersection points for lines,hence the speed of calculating NFP is significantly increased.