For a given convex polygon,finding the bounding parallelograms with minimal area of this convex polygon belongs to the minimum enclosing problem.In the process of reconnaissance in the sea battlefield against the target sea area,if the shape of the target sea area is known,how to determine the early warning and search range of the reconnaissance forces such as early warning aircraft and shipborne helicopters is transformed into the solution process of the problem.Related work and a currently used solution are discussed,which is neither efficient nor able to figure out always correct answer.A more general method is given with time com-plexity of O(n2)for solving the minimum enclosing parallelogram for convex polygons based on geometric principles with an intro-duction to the principles.An optimized algorithm is given with time complexity approximating O(n)in principle.The above algo-rithm is tested with randomly generated convex polygons,the experiments confirm that the algorithm does solve the minimum enve-lope problem in linear time complexity.
关键词
对海侦察区域/最小包围问题/凸多边形/平行四边形/面积最小
Key words
sea reconnaissance area/minimal bounding problems/convex polygon/parallelograms/minimal area
维普
万方数据