【模板】二维向量的实现

  |  

摘要: 本文介绍一个向量的代码模板,解决几何问题是会频繁使用

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


各位好,本文介绍一个向量的代码模板,解决几何问题是会频繁使用,在文章 几何题汇总 中,我们汇总了力扣上 2000 以内的计算几何的题目,解决这些题目的代码中使用这个向量的代码模板很方便。

在代码模板中,有一些计算几何中常见的代码实现时的问题,汇总在了前面。然后给出 C++ 的二维向量的代码模板,支持的功能如下:

  • 两个向量的比较
  • 向量的加法和减法
  • 向量的数乘
  • 向量的模
  • 方向相同的单位向量
  • 从 x 轴正方向转到当前向量的角度
  • 向量的内积
  • 当前向量映射到另一向量的结果
  • 两个向量的夹角
  • 判断两个两个向量是否垂直
  • 平行四边形面积
  • 三角形面积
  • 判定两个向量的方向

计算几何 Tips

浮点数的判定

1
2
3
a < 0:  a < -EPS
a <= 0: a < EPS
a == 0: fabs(a) < EPS

Corner Case 以及退化情况

  • 同一直线上三个以上的点
  • 互相平行或重叠的线段
  • 面积为 0 的多边形
  • 多边形的边互相重叠的情况

acos 和 asin 的定义域

acos 和 asin 只接受 [-1, 1],如果传递了 x = 1 + 1e-7 这种值,会返回 NaN,办法 max(-1.0, min(1.0, x))


代码模板 (C++):二维向量类 Vector2

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// 二维向量
const double PI = 2.0 * acos(0.0);
const double EPS = 1e-10;

struct Vector2
{
double x, y;
explicit Vector2(double x_=0, double y_=0):x(x_),y(y_){}

// 比较两个向量
bool operator==(const Vector2& vec) const
{
return fabs(x - vec.x) < EPS && fabs(y - vec.y) < EPS;
}
bool operator<(const Vector2& vec) const
{
if(fabs(x - vec.x) < EPS)
return y < vec.y;
return x < vec.x;
}

// 向量的加法和减法
Vector2 operator+(const Vector2& vec) const
{
return Vector2(x + vec.x, y + vec.y);
}
Vector2 operator-(const Vector2& vec) const
{
return Vector2(x - vec.x, y - vec.y);
}

// 向量的数乘
Vector2 operator*(double a) const
{
return Vector2(x * a, y * a);
}

// 向量的模
double norm() const
{
return hypot(x, y);
}

// 返回方向相同的单位向量
// 零向量不可调用
Vector2 normalize() const
{
return Vector2(x / norm(), y / norm());
}

// 从 x 轴正方向转到当前向量的角度
double polar() const
{
// atan2 返回 (-PI, PI],修正为 [0,2PI)
// fmod 求两个实数相除的余数
return fmod(atan2(y, x) + 2 * PI, 2 * PI);
}

// 内积
double dot(const Vector2& vec) const
{
return x * vec.x + y * vec.y;
}
double cross(const Vector2& vec) const
{
return x * vec.y - y * vec.x;
}

// 当前向量映射到另一向量的结果
// vec的长度需要大于0
Vector2 project(const Vector2& vec) const
{
Vector2 r = vec.normalize();
return r * r.dot(*this);
}

// 两个向量的夹角
// 两个向量长度均需要大于 0
double insersection_angle(const Vector2& vec) const
{
return acos(dot(vec) / norm() * vec.norm());
}

// 判断两个向量是否垂直
// 两个向量长度均需要大于 0
bool perpendicular(const Vector2& vec) const
{
return fabs(dot(vec)) < EPS;
}

// 平行四边形面积
double parallelogram_area(const Vector2& vec) const
{
return fabs(cross(vec));
}

// 三角形面积,可以扩找到多边形
double triangle_area(const Vector2& vec) const
{
return fabs(cross(vec)) / 2;
}
};

// 判定两个向量的方向
// ccw: counter clock wise
double ccw(const Vector2& a, const Vector2& b)
{
// 正数: b 在 a 的逆时针 180 度内
// 负数: b 在 a 的顺时针 180 度内
// 0: 平行
return a.cross(b);
}
double ccw(const Vector2& p, const Vector2& a, const Vector2& b)
{
// 正数: 以 p 为基准点时,b 在 a 的逆时针 180 度内
// 负数: 以 p 为基准点时,b 在 a 的顺时针 180 度内
return ccw(a - p, b - p);
}

Share