ACM►计算几何

基础计算几何小结

前言

说是小结，其实这里只是备忘下，记录下几何题的工具函数。

向量和点

这里简单定义了一个点类，实现数乘，加减。说是点其实大部分时候是当做向量来用的，计算几何中为了方便经常会用向量来描述几何图形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Point {
    double x, y;

    Point(double x = 0, double y = 0) : x(x), y(y) {}

    Point operator*(const double t) {
        return Point(x * t, y * t);
    }

    Point operator-(const Point t) {
        return Point(x - t.x, y - t.y);
    }

    Point operator+(const Point t) {
        return Point(x + t.x, y + t.y);
    }

    bool operator<(const Point t) {
        return dcmp(x - t.x) < 0 || dcmp(x - t.x) == 0 && dcmp(y - t.y) < 0;
    }
};

向量的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//点积
double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}
//叉积
double cross(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}
//向量的长度
double length(Point a) {
    return sqrt(dot(a, a));
}
//两个向量的夹角
double angle(Point a, Point b) {
    return acos(dot(a, b) / length(a) / length(b));
}
//将向量以起点为中心旋转，rad 为旋转的角度，弧度制
Point rotate(Point a, double rad) {
    return Point(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}

点与直线的关系

1
2
3
4
5
6
7
8
//点 q 是否在线段 p1、p2 上，这里包含了在端点的情况，如果不包含后面的点乘改成小于，如果考虑直线的话就不需要后面的点乘了
bool on_seg(Point p1, Point p2, Point q) {
    return dcmp(cross((p1 - q), (p2 - q))) == 0 && dcmp(dot((p1 - q), (p2 - q))) <= 0;
}
//求 p1、p2 和 q1、q2 两条直线的交点，注意两条直线（向量）叉乘不能等于 0，即先要判断平行
Point intersection(Point p1, Point p2, Point q1, Point q2) {
    return p1 + (p2 - p1) * (cross(q2 - q1, q1 - p1) / cross(q2 - q1, p2 - p1));
}

多边形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//求多边形面积，要保证点的顺序是顺时针或者逆时针
double polygon_area(vector<Point> data) {
    double area = 0;
    for (int i = 1; i < data.size() - 1; i++) {
        area += cross(data[i] - data[0], data[i + 1] - data[0]);
    }
    return area / 2;
}
//求凸包，并以顺时针的顺序返回凸包上的点
vector<Point> convex_hull(vector<Point> &data) {
    sort(data.begin(), data.end());
    vector<Point> rst;
    int m = 0;
    for (int i = 0; i < data.size(); i++) {
        while (m > 1 && dcmp(cross(rst[m - 1] - rst[m - 2], data[i] - rst[m - 2])) <= 0) rst.pop_back(), m--;
        rst.push_back(data[i]), m++;
    }
    int k = m;
    for (int i = data.size() - 2; i >= 0; i--) {
        while (m > k && dcmp(cross(rst[m - 1] - rst[m - 2], data[i] - rst[m - 2])) <= 0) rst.pop_back(), m--;
        rst.push_back(data[i]), m++;
    }
    rst.pop_back();
    return rst;
}