实验一java凸包算法理解

简介
软件构造的实验一要求实现一个凸包算法，这啥呢，大概就是平面上有一堆点，然后要求找到一个集合，这个集合里面的点围成的多边形包围了所有的点。

解析
那么如何解决呢，以下是最简单暴力的方式，类似于手上有一捆筷子，而你要用一根绳子把所有的筷子捆成一把，那么你抓着绳子缠绕一圈，那么绳子接触到的肯定是最外面的筷子，这些筷子便是我们需要找的。
而现在要做的是怎么去找，我们捆筷子时，绳子每次碰到的肯定是最靠近前一根筷子，而且旋转绳子角度最小的那根，也就是说，每次我们都需要去找一个下一个最外面的点，怎么找呢，类似于下图


现在我们已经找到了1号点和2号点（如何找一号点和二号点后面说）， 那么 1->2就会与y轴形成一个夹角A，那么接下来如何到达3号点呢，只需要以当前与y轴的角度作为角度，以2号点为圆心，顺时针旋转，那么第一个碰到的肯定就是3号点，也就是说旋转角度最小的那个点。到这里如果明白了寻找点的本质，那么实现算法就非常简单了。

步骤
1.找到1号点，这个可以随个人喜好，不过为了看着方便，一般选择最下面的点，也就是纵坐标最小，然后设置其与y轴夹角为-180，也就是和y轴相反，或者与y轴垂直也可。

2.找到二号点，与解析中知道1,2号点相似，旋转一个最小的角度找到2号点，这里的旋转最简单的就是遍历集合中的除了点本身之外的所有其他点，Java的math中提供了许多计算夹角的函数，可以用来计算两个点的矢量与y轴夹角，注意这里只是选择y轴作为参考来计算角度，而且方便使用库函数。也就是计算1->2 的夹角A，2->3的夹角B，然后B-A就是旋转的角度。
3.找到其他的所有点，与2步骤类似，遍历集合中的所有点，计算所有的夹角，找到旋转角度最小的加入集合中即可，直到下一个点为初始点时结束算法。

总结
由于实现并不难，网上应该也有很多代码，这里只分享理解。
当然这样每次遍历一个点集合的效率是低下的（n方），可以有选择性的排除一些点，避免计算与每个点的角度，当然对于少数的点时间相差无几，只有到点集合十分庞大时，这样的筛选才有意义。