An Algorithm for Rectangle's Feasible Region Calculation

For the packing problem, the paper presents a novel algorithm for calculating rectangle's feasible region. Firstly, according to vertices' configuration in the layout region and the current rectangle size, the offset polygon can be obtained by calculating every vertex's coordinates. Then, the algorithm tours each edge of the offset polygon to find out and mark all the intersections. Lastly, on the basis of boundary search in the directions of each edge, all the vertices on the feasible region can be directly attained. The algorithm avoids dealing with the complex cases in which several edges intersect with each other by searching the boundary polygon. Analysis and illustrations indicate that the algorithm is simple and efficient.