数据结构|凸包问题-Graham 算法 java|开发语言|算法

这里我只是想记录一下凸包问题，我发现如果要把他讲解非常清楚，需要画比较复杂的集合图形，而我不会。所以，这篇文章可能只能帮你梳理一下算法步骤或者参考一下代码。
什么是凸包问题
【数据结构|凸包问题-Graham 算法】找一条线，能够将二维平面上的所有的点围起来，返回这条线上的所有的点，解决凸包的算法很多，比如
Jarvis 算法、Graham 算法、Andrew 算法。
我这里主要记录Graham 算法的过程
步骤

我们需要找到P0点，P0点的特征是，y最小，如果有多个，那么去取最右边的，也就是x最大的，然后我们将P0点放在首位
以P0为原点，将剩余点排序，排序规则是以P0为原点，和该点形成的幅度，幅度越小排在越前面
如果出现2个点共线，这距离P0越近得排在越前面
将最后一条共线的所有点进行翻转，比如一共0个点，而 p5,p6,p7又共线，则换成p0,p1,p2,p3,p4,p7,p6,p5
先将p0,p1,p2放入栈中，然后去P3过来，如果p1 - p2 - p3的走向是顺时针，则弹出p2，否则加入p3;
不断的重复5的步骤，直到所有的点

代码

import sun.plugin.javascript.navig.Link; import java.util.*; public class Solution {//计算距离，这个是真是距离的平方 public int distance(int[] p, int[] q) { return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]); }/* p:是原点如果pq,比pr的角度大，这返回正数共线，返回0 否则返回负数 */ public int cross(int[] p, int[] q, int[] r) { return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]); }//将P0移动到头部 private void movePoTOZero(int[][] trees){ int pIndex = 0; for (int i = 0; i < trees.length; i++) { if(trees[i][1] < trees[pIndex][1]){ pIndex = i; } if(trees[i][1] == trees[pIndex][1] && trees[i][0] > trees[pIndex][0]){ pIndex = i; } } int[] temp = trees[pIndex]; trees[pIndex] = trees[0]; trees[0] = temp; }/* 初始化数据,将trees按照角度大小进行排列,P0除外如果角度大小一样（corss返回0），则距离近得排在前面查找和最后一个点共享的点，然后，从新排列，按照距离远的排在前面*/ private void init(int[][] trees){ Arrays.sort(trees,1,trees.length, new Comparator() { @Override public int compare(int[] o1, int[] o2) { int cross = cross(trees[0],o2,o1); // 这里为了让02比o1小的时候，返回正数 if(cross == 0){ return distance(o1,trees[0]) - distance(o2,trees[0]); // 如果01距离更远，则返回正数，o1则排在前面 } else { return cross; // 正数的话，说明o1的角度，大于02的角度 } } }); int left = trees.length - 2; // 查找和尾巴点共线的点 while (cross(trees[0],trees[trees.length-1],trees[left]) == 0){ left--; } left++; int right = trees.length -1; while (left < right){ //让距离反着来 int[] temp = trees[right]; trees[right] = trees[left]; trees[left] = temp; left++; right--; }}// 1. 查找P点 // 2. 初始化数据 // 3. 将数据往LinkList中放，如果数据出现顺时针的点，则弹出，否则就加入 public int[][] outerTrees(int[][] trees) { if(trees.length < 4){ return trees; } movePoTOZero(trees); init(trees); for (int i = 0; i < trees.length; i++) { System.out.print(trees[i][0] + ":" + trees[i][1] + ""); }System.out.println("===================================="); int index = 3; Deque linked = new ArrayDeque(); //这里面存的下标 // 先存入3个：P0 p1,p2 linked.offerLast(0); linked.offerLast(1); linked.offerLast(2); while (index < trees.length){ if(linked.size() == 1){ linked.offerLast(index); continue; } int p2 = linked.pollLast(); int p1 = linked.peekLast(); int p3 = index; if(isLeftTriangle( trees[p1][0],trees[p1][1] ,trees[p2][0],trees[p2][1] ,trees[p3][0],trees[p3][1])){ linked.offerLast(p2); linked.offerLast(p3); index++; } else { System.out.println("弹出了=" + trees[p2][0] + trees[p2][1]); } } int[][] ret = new int[linked.size()][2]; index = 0; while (!linked.isEmpty()){ int cur = linked.pollFirst(); ret[index] = trees[cur]; index++; } return ret; }private boolean isLeftTriangle(double x1,double y1,double x2,double y2,double x3,double y3){ double ret = x1 * y2 + x2 * y3 + x3 * y1 - y1 * x2 - y2 * x3 - y3 * x1; return ret >= 0; } }