# 凸壳算法

## Convex hull algorithms

Posted by Jerry on May 4, 2017

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

## 凸壳算法（二维的）

#### 解决实际算法题

leetcode的求给定点集合的边界

There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

public class Solution {
public List<Point> outerTrees(Point[] points) {
Point first = points[0];
int firstIndex = 0;
// Find the leftmost point
for (int i = 0; i < points.length; i++) {
Point point = points[i];
if (point.x < first.x) {
first = point;
firstIndex = i;
}
}

Point cur = first;
int curIndex = firstIndex;

do {
Point next = points[0];
int nextIndex = 0;
for (int i = 1; i < points.length; i++) {
if (i == curIndex) continue;
Point p = points[i];
int cross = crossProductLength(p, cur, next);
if (nextIndex == curIndex || cross > 0 ||
// Handle multi points in a line
(cross == 0 && distance(p, cur) > distance(next, cur))) {
next = p;
nextIndex = i;
}
}
// Handle multi points in a line
for (int i = 0; i < points.length; i++) {
Point p = points[i];
int cross = crossProductLength(p, cur, next);
if (i != curIndex && cross == 0) {
}
}

cur = next;
curIndex = nextIndex;
} while (curIndex != firstIndex);

}

private int crossProductLength(Point A, Point B, Point C) {
// Get the vectors' coordinates.
int BAx = A.x - B.x;
int BAy = A.y - B.y;
int BCx = C.x - B.x;
int BCy = C.y - B.y;

// Calculate the Z coordinate of the cross product.
return (BAx * BCy - BAy * BCx);
}

private int distance(Point p1, Point p2) {
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
}


#### 判断一个多边形是否为凸多边形

public class Solution {
public boolean isConvex(List<List<Integer>> points) {
// For each set of three adjacent points A, B, C, find the cross product AB · BC. If the sign of
// all the cross products is the same, the angles are all positive or negative (depending on the
// order in which we visit them) so the polygon is convex.
boolean gotNegative = false;
boolean gotPositive = false;
int numPoints = points.size();
int B, C;
for (int A = 0; A < numPoints; A++) {
// Trick to calc the last 3 points: n - 1, 0 and 1.
B = (A + 1) % numPoints;
C = (B + 1) % numPoints;

int crossProduct =
crossProductLength(
points.get(A).get(0), points.get(A).get(1),
points.get(B).get(0), points.get(B).get(1),
points.get(C).get(0), points.get(C).get(1));
if (crossProduct < 0) {
gotNegative = true;
}
else if (crossProduct > 0) {
gotPositive = true;
}
if (gotNegative && gotPositive) return false;
}

// If we got this far, the polygon is convex.
return true;
}

// Return the cross product AB x BC.
// The cross product is a vector perpendicular to AB and BC having length |AB| * |BC| * Sin(theta) and
// with direction given by the right-hand rule. For two vectors in the X-Y plane, the result is a
// vector with X and Y components 0 so the Z component gives the vector's length and direction.
private int crossProductLength(int Ax, int Ay, int Bx, int By, int Cx, int Cy)
{
// Get the vectors' coordinates.
int BAx = Ax - Bx;
int BAy = Ay - By;
int BCx = Cx - Bx;
int BCy = Cy - By;

// Calculate the Z coordinate of the cross product.
return (BAx * BCy - BAy * BCx);
}
}