⒈、对于一个集合D，D中任意有限个点的凸组合的全体称为D的凸包。
⒉、对于一个集合D，所有包含D的凸集之交称为D的凸包。
简言之，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。
例如：
2.凸包的应用1、避免碰撞（Collision avoidance）:如果汽车的凸包不会碰撞到障碍物，那么汽车也可以避免碰撞到障碍物。由于凸包的避碰路径的计算比较容易，因此常用于路径规划。
2、最小框（Smallest box）:一个多边形的最小面积矩形至少有一边与该多边形的凸包齐平，因此在最小矩形算法中，首先应该计算凸包。同样，寻找物体周围最小的三维盒子取决于三维凸包。
3、形状分析（Shape analysis）:凸包可以用于计算形状的“凸缺陷树”（convex deficiency trees），通过凸缺陷树可以对形状进行分析分类。
二、算法实现 一、Point类JAVA实现的具体代码如下：
public class Point {
private final double x;
private final double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public double x() {
return x;
}
public double y() {
return y;
}
}
二、计算偏转角度的calculateBearingToPoint方法
该方法用于计算从A(currentX,currentY)到B(targetX,targetY)时，向量OA到向量OB的向量偏转角度，其中currentBearing为出OA与y轴的夹角。
JAVA实现的具体代码如下：
public static double calculateBearingToPoint(double currentBearing, int currentX, int currentY, int targetX, int targetY) {
//分别计算两点间距离在x轴y轴上的投影
double deltaX = targetX - currentX;
double deltaY = targetY - currentY;
double turn, atan;
//对特殊情况进行处理
if (deltaY == 0.0) {
if (deltaX == 0.0) {
return 0.0;
} else if (deltaX < 0.0) {
return (640.0 - currentBearing) % 360;
} else {
return (450.0 - currentBearing) % 360;
}
} else {//求tan，再求arctan，最后得到偏转角turn
double tan = deltaX / deltaY;
atan = Math.toDegrees(Math.atan(tan));
if (deltaY > 0) {
turn = (720.0 + atan - currentBearing) % 360;
} else {
turn = (540.0 + atan - currentBearing) % 360;
}
}
return turn;
}
三、计算凸包的convexHull方法
1、当点集中点的个数小于等于3时，凸包即为该点集本身。
2、求点集中横坐标最小的点A，将A点加入resultList，并设置为current点。
3、遍历点集，求current点偏转角最小能到达的next点，若存在偏转角相同的点，则将距离current远的点设置为next点。
4、将next点设置为current点，重复步骤3，直至next点已经在resultList中。
JAVA实现的具体代码如下：
public static Set convexHull(Set points) {
List pointList = new ArrayList<>(points);//将Set转为List，便于后续遍历
//若points的个数小于等于3个，则凸包为其本身
if (pointList.size() >= 0 && pointList.size() <= 3) {
return points;
}
List resultList = new ArrayList<>();//结果，resultList
Point first = pointList.get(0);//current用与记录当前点
Point next = pointList.get(1);//next用于记录到达的下一个点
//先找出points中x最小的点first
for (int i = 1; i < pointList.size(); i++) {
if (pointList.get(i).x() < first.x()) {
first = pointList.get(i);
next = pointList.get(i + 1);
}
}
//将first加入resultList
resultList.add(first);
Point current = first;
double face = 0.0;//face用于记录当前朝向(与y轴夹角)
boolean notFirstLoop = false;//对第一次循环特殊处理
//当所选择的next点不在resultList中，说明凸包仍未闭合，应继续循环
while (!resultList.contains(next)) {
//将next加入resultList中，并更新朝向face以及当前所在点current
if (notFirstLoop) {
resultList.add(next);
face = (face + calculateBearingToPoint(face, (int) current.x(), (int) current.y(), (int) next.x(), (int) next.y())) % 360;
current = next;
}
notFirstLoop = true;
double minAngle = 0xfffffff;//用于记录两点间最小偏转角度
double maxDistance = 0.0;//用于记录两点之间最大距离，用于偏转角相同的情况
//遍历每一个点
for (int i = 0; i < pointList.size(); i++) {
//除自身之外
if (pointList.get(i) != current) {
double tmpAngle = calculateBearingToPoint(face, (int) current.x(), (int) current.y(), (int) pointList.get(i).x(), (int) pointList.get(i).y());
double tmpDistance = Math.pow(current.x() - pointList.get(i).x(), 2) + Math.pow(current.y() - pointList.get(i).y(), 2);
//若当前偏转角小于最小偏转角，则更新
if (tmpAngle < minAngle) {
minAngle = tmpAngle;
maxDistance = tmpDistance;
next = pointList.get(i);
} else if (tmpAngle == minAngle) {//当前偏转角与最小偏转角相同时，需比较两点之间距离，取距离更大点
if (tmpDistance > maxDistance) {
minAngle = tmpAngle;
maxDistance = tmpDistance;
next = pointList.get(i);
}
}
}
}
}
//将resultList转换为目标Set返回
Set resultSet = new HashSet<>(resultList);
return resultSet;
}
