旋转卡壳求点集的最小面积外接矩形

Date 2017-03-12(星期日) 21:56 By Ming In 几何算法 Tags 几何算法，算法,

旋转卡壳算法的历史

先转摘一段网上关于旋转卡壳算法的历史

1978年， M.I. Shamos's Ph.D. 的论文"Computational Geometry"标志着计算机科学的这一领域的诞生。 当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法， 即根据多边形的一对点距离的最大值来确定。 后来直径演化为由一对对踵点对来确定。 Shamos提出了一个简单的 O(n) 时间的算法来确定一个凸 ...

阅读全文 »

Graham扫描法求凸包

Date 2017-03-11(星期六) 18:42 By Ming In 几何算法 Tags 几何算法，算法,

凸包用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。

如下图(图片来看网络)：

算法的主要方法是先排序，然后扫描。

点集排序

1. 选取基点。选择所有点中y坐标最小的点，如果多个点都是最小值，选x坐标最小的点。
2. 剩下的点按与基点构成的向量进行排序。计算向量与x轴的夹角大小来排序，可以使用两个向量叉积来判断第二个向量在第一个向量的左边还是右边。只求向量z轴上的值来判断方向即可。

代码如下

/* 
 *        Name:  getdist ...

阅读全文 »