| 一个求解多边形最小面积外接矩形的算法 |
| |
| 引用本文： | 程鹏飞,闫浩文,韩振辉.一个求解多边形最小面积外接矩形的算法[J].工程图学学报,2008,29(1):122-126. |
| |
| 作者姓名： | 程鹏飞 闫浩文 韩振辉 |
| |
| 作者单位： | 兰州交通大学数理与软件工程学院,甘肃,兰州,730070 |
| |
| 摘 要： | 多边形最小面积外接矩形是地理信息系统和图形学领域一个极其有用的工具,但是其精确求解过程比较困难.首先证明了一个多边形的最小面积外接矩形必定过该多边形凸包的一条边,然后基于该思想提出了一个计算多边形最小面积外接矩形的算法,并对算法的效率进行了分析.最后给出了算法的实验算例,进一步说明了算法的可行性与可靠性.
|
| 关 键 词： | 计算机应用 地理信息系统 多边形最小面积外接矩形 外接矩形算法 求解过程 多边形 最小面积 外接矩形 算法 Polygon Area Minimum Computing 算例 实验 分析 效率 计算 思想 凸包 比较 图形学 信息系统 地理 |
| 文章编号： | 1003-0158（2008）01-0122-05 |
| 收稿时间： | 2006-11-01 |
| 修稿时间： | 2006年11月1日 |
An Algorithm for Computing the Minimum Area Bounding Rectangle of an Arbitrary Polygon |
| |
| CHENG Peng-fei,YAN Hao-wen,HAN Zhen-hui.An Algorithm for Computing the Minimum Area Bounding Rectangle of an Arbitrary Polygon[J].Journal of Engineering Graphics,2008,29(1):122-126. |
| |
| Authors: | CHENG Peng-fei YAN Hao-wen HAN Zhen-hui |
| |
| Abstract: | The minimum area bounding rectangle(MABR) of an arbitrary polygon is an important tool in the geographic information systems and computer graphics,but how to precisely calculate it is of great difficulty.Firstly,the MABR of an arbitrary polygon shares a common edge with the convex hull of the polygon is proved.Secondly,an algorithm for computing MABR based on this idea is presented and the efficiency of the algorithm is discussed.Finally,some experiments are given to show the feasibility and reliability of the algorithm. |
| |
| Keywords: | computer application geographic information systems minimum area bounding rectangle of an arbitrary polygon bounding rectangle algorithms |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
