Java 使用 Graham 扫描的凸包（Convex Hull using Graham Scan）

先决条件：

如何检查两个给定的线段是否相交？

c++ https://blog.csdn.net/hefeng_aspnet/article/details/141713655
java https://blog.csdn.net/hefeng_aspnet/article/details/141713762
python https://blog.csdn.net/hefeng_aspnet/article/details/141714389
C# https://blog.csdn.net/hefeng_aspnet/article/details/141714420
Javascript https://blog.csdn.net/hefeng_aspnet/article/details/141714442 

贾维斯算法

 c++ https://blog.csdn.net/hefeng_aspnet/article/details/141716082
java https://blog.csdn.net/hefeng_aspnet/article/details/141716363
python https://blog.csdn.net/hefeng_aspnet/article/details/141716444
C# https://blog.csdn.net/hefeng_aspnet/article/details/141716403
Javascript https://blog.csdn.net/hefeng_aspnet/article/details/141716421 

        凸包是包含给定点集的最小凸多边形。它是计算几何学中一个有用的概念，在计算机图形学、图像处理和碰撞检测等各个领域都有应用。

凸多边形是所有内角都小于180度的多边形。可以为任意点集构造凸包，无论这些点如何排列。

格雷厄姆扫描算法：
        格雷厄姆扫描算法是一种简单而有效的算法，用于计算一组点的凸包。它的工作原理是迭代地将点添加到凸包中，直到所有点都添加完毕。

        该算法首先找到 y 坐标最小的点。该点始终位于凸包上。然后，该算法根据剩余点相对于起点的极角对它们进行排序。

        然后，算法会迭代地将点添加到凸包中。在每个步骤中，算法都会检查添加到凸包中的最后两个点是否形成右转。如果是，则将最后一个点从凸包中移除。否则，将排序列表中的下一个点添加到凸包中。

当所有点都被添加到凸包时，算法终止。

Graham Scan的实现：

第一阶段（排序点）：
        实现格雷厄姆扫描算法的第一步是按照点相对于起点的极角对点进行排序。
        一旦点排序完毕，起点就会添加到凸包中。一旦点排序完毕，它们就会形成一条简单的闭合路径（见下图）。 

第二阶段（接受或拒绝点）：

    一旦我们有了闭合路径，下一步就是遍历该路径并移除该路径上的凹点。如何决定移除哪个点以及保留哪个点？同样，方向在这里有帮助。排序数组中的前两个点始终是凸包的一部分。对于剩余的点，我们跟踪最近的三个点，并找到它们形成的角度。让这三个点分别为prev(p)、curr(c)和next(n)。如果这些点的方向（按相同顺序考虑它们）不是逆时针的，我们丢弃 c，否则我们保留它。下图显示了此阶段的分步过程。
 

下面是上述算法的实现：

// Java equivalent of the above code 
import java.util.*; 
  
// A Java program to find convex hull of a set of points. Refer

 //c++ C++ 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//java Java 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//python Python 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//C# C# 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客
//Javascript javascript 3 个有序点的方向（Orientation of 3 ordered points）-CSDN博客  
// for explanation of orientation()  
public class ConvexHull 
{ 
    // Define Infinite (Using INT_MAX  
    // caused overflow problems) 
    static final int INF = 10000; 
  
    // To find orientation of ordered triplet (p, q, r). 
    // The function returns following values 
    // 0 --> p, q and r are colinear 
    // 1 --> Clockwise 
    // 2 --> Counterclockwise 
    static int orientation(Point p, Point q, Point r) 
    { 
        // See https://www.geeksforgeeks.org/orientation-3-ordered-points/ 
        // for details of below formula. 
        int val = (q.y - p.y) * (r.x - q.x) - 
                  (q.x - p.x) * (r.y - q.y); 
  
        if (val == 0) return 0;  // colinear 
  
        return (val > 0)? 1: 2; // clock or counterclock wise 
    } 
  
    // Prints convex hull of a set of n points. 
    static void convexHull(Point points[], int n) 
    { 
        // There must be at least 3 points 
        if (n < 3) return; 
  
        // Initialize Result 
        Vector<Point> hull = new Vector<Point>(); 
  
        // Find the leftmost point 
        int l = 0; 
        for (int i = 1; i < n; i++) 
            if (points[i].x < points[l].x) 
                l = i; 
  
        // Start from leftmost point, keep moving  
        // counterclockwise until reach the start point 
        // again. This loop runs O(h) times where h is 
        // number of points in result or output. 
        int p = l, q; 
        do
        { 
            // Add current point to result 
            hull.add(points[p]); 
  
            // Search for a point 'q' such that  
            // orientation(p, x, q) is counterclockwise  
            // for all points 'x'. The idea is to keep  
            // track of last visited most counterclock- 
            // wise point in q. If any point 'i' is more  
            // counterclock-wise than q, then update q. 
            q = (p + 1) % n; 
              
            for (int i = 0; i < n; i++) 
            { 
               // If i is more counterclockwise than  
               // current q, then update q 
               if (orientation(points[p], points[i], points[q]) 
                                                   == 2) 
                   q = i; 
            } 
  
            // Now q is the most counterclockwise with 
            // respect to p. Set p as q for next iteration,  
            // so that q is added to result 'hull' 
            p = q; 
  
        } while (p != l);  // While we don't come to first  
                           // point 
  
        // Print Result 
        for (int i = 0; i < hull.size(); i++) 
            System.out.println("(" + hull.get(i).x + ", " +  
                               hull.get(i).y + ")"); 
    } 
  
    // Driver program to test above function 
    public static void main(String[] args)  
    { 
        Point points[] = new Point[8]; 
        points[0] = new Point(0, 3); 
        points[1] = new Point(1, 1); 
        points[2] = new Point(2, 2); 
        points[3] = new Point(4, 4); 
        points[4] = new Point(0, 0); 
        points[5] = new Point(1, 2); 
        points[6] = new Point(3, 1); 
        points[7] = new Point(3, 3); 
  
        int n = points.length; 
        convexHull(points, n); 
    } 
} 

//Point class to store points 
class Point  
{ 
    int x, y; 
    Point() 
    { 
        x = 0; 
        y = 0; 
    } 
    Point(int a, int b) 
    { 
        x = a; 
        y = b; 
    } 
};

输出： 

（0，3）
（4，4）
（3，1）
（0，0）

时间复杂度： O(nLogn)，其中 n 为输入点的数量。

    第一步（找到最底部的点）需要 O(n) 时间。第二步（对点进行排序）需要 O(nLogn) 时间。第三步需要 O(n) 时间。在第三步中，每个元素最多被推送和弹出一次。因此，第六步逐个处理点需要 O(n) 时间，假设堆栈操作需要 O(1) 时间。总体复杂度为 O(n) + O(nLogn) + O(n) + O(n)，即 O(nLogn)。

辅助空间： O（n），因为使用了显式堆栈，所以没有占用额外的空间。

凸包的应用：

    凸包的应用范围很广，包括：

    碰撞检测：凸包可用于快速确定两个物体是否发生碰撞。这在计算机图形学和物理模拟中很有用。

    图像处理：凸包可用于分割图像中的对象。这对于诸如对象识别和跟踪之类的任务很有用。

    计算几何：凸包用于各种计算几何算法，例如查找最近的点对和计算一组点的直径。