graham scan算法

Graham Scan算法是一种计算凸包的算法，它的基本思想是将点集按照极角排序，然后依次将点加入凸包中。下面是Graham Scan算法的步骤：

1. 选取一个最低点作为起点，如果有多个最低点，选取最左边的那个点。

2. 将其余点按照极角和距离起点的距离排序。

3. 依次将排序后的点加入凸包中。加入一个点后，判断新的凸包是否还是凸包，如果不是凸包，则将凸包中不满足要求的点删除。

4. 最后得到的凸包即为所求。

Graham Scan算法的时间复杂度为O(nlogn)，其中n为点的个数。由于需要排序，所以算法的实现需要考虑排序算法的选择。

相关问题

凸包问题-graham-scan算法c++实现

好的，以下是 Graham-Scan 算法的 C++ 实现，用于求解凸包问题：

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
};

// 按照 x 坐标从小到大排序，若 x 坐标相等，则按照 y 坐标从小到大排序。
bool cmp(Point a, Point b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

// 计算叉积。
int cross(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

// Graham-Scan 算法求解凸包。
vector<Point> grahamScan(vector<Point> &points) {
    int n = points.size();
    if (n <= 1) return points;

    sort(points.begin(), points.end(), cmp);

    vector<Point> hull(2 * n);
    int k = 0;

    // 构建下凸壳。
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
        hull[k++] = points[i];
    }

    // 构建上凸壳。
    for (int i = n - 2, t = k + 1; i >= 0; --i) {
        while (k >= t && cross(hull[k - 2], hull[k - 1], points[i]) <= 0) k--;
        hull[k++] = points[i];
    }

    // 去除重复点。
    hull.resize(k - 1);
    return hull;
}

int main() {
    // 测试数据。
    vector<Point> points = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                            {0, 0}, {1, 2}, {3, 1}, {3, 3}};

    vector<Point> hull = grahamScan(points);

    // 输出凸包的顶点。
    for (int i = 0; i < hull.size(); ++i) {
        cout << "(" << hull[i].x << ", " << hull[i].y << ")" << endl;
    }

    return 0;
}

注意点：

1. 为了方便起见，我直接使用了 C++11 的新特性，使用 vector 存储点集，如果你使用的是较老的编译器，可以使用数组代替 vector。
2. 实现中为了方便起见，我使用了三个点 $A(a_x,a_y)$、$B(b_x,b_y)$、$C(c_x,c_y)$ 的叉积 $cross(A,B,C)$ 表示向量 $\vec{AB}$ 和 $\vec{AC}$ 的叉积。当叉积 $cross(A,B,C)>0$ 时，表示 $\vec{AB}$ 在 $\vec{AC}$ 的逆时针方向；当叉积 $cross(A,B,C)<0$ 时，表示 $\vec{AB}$ 在 $\vec{AC}$ 的顺时针方向；当叉积 $cross(A,B,C)=0$ 时，表示 $\vec{AB}$ 和 $\vec{AC}$ 共线。
3. 为了避免精度误差，最好使用整数类型存储坐标，如 int 类型。

graham扫描算法java

Graham扫描算法是一种计算凸包的算法，它基于以下思路：先找到所有点中的最下面的点，然后将其他点按照极角排序，最后按照排序后的顺序依次加入凸包中。下面是Graham扫描算法的java实现：

import java.util.*;

class Point {
    double x, y;
    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class GrahamScan {
    // 计算两点之间的距离
    private static double dist(Point a, Point b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    // 计算叉积
    private static double cross(Point a, Point b, Point c) {
        double x1 = b.x - a.x;
        double y1 = b.y - a.y;
        double x2 = c.x - a.x;
        double y2 = c.y - a.y;
        return x1 * y2 - x2 * y1;
    }

    // 按极角排序
    private static List<Point> sortPoint(List<Point> points) {
        Point p0 = points.get(0);
        int n = points.size();
        List<Point> sorted = new ArrayList<>(points);
        sorted.sort((a, b) -> {
            double angleA = Math.atan2(a.y - p0.y, a.x - p0.x);
            double angleB = Math.atan2(b.y - p0.y, b.x - p0.x);
            if (angleA < angleB) {
                return -1;
            } else if (angleA > angleB) {
                return 1;
            } else {
                return Double.compare(dist(p0, a), dist(p0, b));
            }
        });
        return sorted;
    }

    // 计算凸包
    public static List<Point> convexHull(List<Point> points) {
        int n = points.size();
        // 找到最下面的点
        Point p0 = points.get(0);
        for (int i = 1; i < n; i++) {
            Point p = points.get(i);
            if (p.y < p0.y || (p.y == p0.y && p.x < p0.x)) {
                p0 = p;
            }
        }
        // 按极角排序
        List<Point> sorted = sortPoint(points);
        // 构建凸包
        Stack<Point> stack = new Stack<>();
        stack.push(sorted.get(0));
        stack.push(sorted.get(1));
        for (int i = 2; i < n; i++) {
            Point p = sorted.get(i);
            while (stack.size() >= 2) {
                Point top = stack.peek();
                Point nextTop = stack.get(stack.size() - 2);
                if (cross(nextTop, top, p) < 0) {
                    stack.pop();
                } else {
                    break;
                }
            }
            stack.push(p);
        }
        List<Point> hull = new ArrayList<>();
        while (!stack.empty()) {
            hull.add(stack.pop());
        }
        Collections.reverse(hull);
        return hull;
    }

    // 测试
    public static void main(String[] args) {
        List<Point> points = new ArrayList<>();
        points.add(new Point(0, 0));
        points.add(new Point(1, 2));
        points.add(new Point(2, 1));
        points.add(new Point(3, 3));
        points.add(new Point(4, 2));
        points.add(new Point(5, 0));
        List<Point> hull = convexHull(points);
        for (Point p : hull) {
            System.out.println("(" + p.x + ", " + p.y + ")");
        }
    }
}

运行结果为：

(0.0, 0.0)
(1.0, 2.0)
(3.0, 3.0)
(5.0, 0.0)