Research for Generating Min-Area Convex Quadrangle Encasing Box for Closed Contour Based on Genetic Algorithm

摘要

In many engineering applications, it is necessary to calculate the min-area encasing box of a closed contour. The problem about encasing box is one of the basic problems in computing geometry. It is widely used in many engineering applications such as image processing, pattern recognition, VLSI and CAD. Currently, the encasing box adopted in designing path, collision detection and real-roaming is rectangle encasing boxes such as AABB(Axis Aligned Bounding Boxes) and OBB(Oriented Bounding Boxes). How to construct the min-area quadrangle encasing box is always the research hotspot in the research relating encasing box. Based on GA(genetic algorithm), an algorithm for generating the min-area convex quadrangle encasing box for arbitrary closed contour is investigated and hence put forward in this paper. Moreover, the algorithm is convergent in probability. The encasing boxes based on the three algorithms are compared in the paper. The encasing box generated by GA is better than those constructed by AABB and OBB. Practical application suggests its usefulness and efficiency.