模板 计算几何

发表于 | 分类于 |
字数统计: 527 字

计算几何基本模板。

判断符号

计算几何中有大量的浮点数运算，因此需要手写函数以判断一个数是否为0。

1
2
3
4
5
double eps;
int cmp(double x){
    if(fabs(x) < eps) return 0;
    return (x > 0 ? 1: -1);
}

平面点类

平面中大多数对象都能通过点来表示。下面给出一份涉及大部分点相关运算的模板。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Point{
    double x, y;
    Point(){}
    Point(double _x, double _y){
        x = _x, y = _y;
    }  
    void input(){
        scanf("%lf%lf", &x, &y);
    }
    void output(){
        printf("%.3lf %.3lf\n", x, y);
    }
    friend bool operator == (const Point &pa, const Point &pb) {
        return cmp(pa.x - pb.x) == 0 && cmp(pa.y - pb.y) == 0;
    }
    friend bool operator < (const Point &pa, const Point &pb) {
        return cmp(pa.x - pb.x) == 0 ? cmp(pa.y - pb.y) < 0: pa.x < pb.x;
    }
    friend Point operator + (const Point &pa, const Point &pb) {
        return Point(pa.x + pb.x, pa.y + pb.y);
    }
    friend Point operator - (const Point &pa, const Point &pb) {
        return Point(pa.x - pb.x, pa.y - pb.y);
    }
    friend Point operator * (const Point &pa, const double &rat) {
        return Point(pa.x * rat, pa.y * rat);
    }
    friend Point operator / (const Point &pa, const double &rat) {
        return Point(pa.x / rat, pa.y / rat);
    }
    friend Point operator << (const Point &pa, const double &rat) {
        double sine = sin(rat), cosi = cos(rat);
        return Point(pa.x * cosi - pa.y * sine, pa.x * sine + pa.y * cosi);
    }
    friend Point operator >> (const Point &pa, const double &rat) {
        double sine = sin(rat), cosi = cos(rat);
        return Point(pa.x * cosi + pa.y * sine, pa.y * cosi - pa.x * sine);
    }
    double norm() const{
        return hypot(x, y);
    }
    double sqr() const{
        return x * x + y * y;
    }
};
double dot(const Point &pa, const Point &pb) {
    return pa.x * pb.x + pa.y * pb.y;
}
double cross(const Point &pa, const Point &pb) {
    return pa.x * pb.y - pa.y * pb.x;
}
double dist(const Point &pa, const Point &pb) {
    return hypot(pa.x - pb.x, pa.y - pb.y);
}
double rad(const Point &pa, const Point &pb){
    return acos(dot(pa, pb) / (pa.norm() * pb.norm()));
}
double rad(const Point &pa, const Point &pb, const Point &pc){
    return acos(dot(pa - pc, pb - pc) / ((pa - pc).norm() * (pb - pc).norm()));
}

平面线段/直线

平面线段或者直线一般用两个端点来表示。为了方便，一般用有向线段的方式存储线段。

1
2