计算几何笔记

admin

1. 向量
2. 常规操作
3. struct Vector {
4.     double x, y;
5.     Vector(double x = 0, double y = 0) : x(x), y(y) {};
6.     Vector operator + (const Vector &A) const {
7.         return Vector(x + A.x, y + A.y);
8.     }//向量的加法
9.     Vector operator - (const Vector &A) const {
10.         return Vector(x - A.x, y - A.y);
11.     }//减法
12.     Vector operator * (const double &A) const {
13.         return Vector(x * A, y * A);
14.     }//数乘
15.     Vector operator / (const double &A) const {
16.         return Vector(x / A, y / A);
17.     }//数除
18.     bool operator == (const Vector &A) const  {
19.         return dcmp(x - A.x) == 0 && dcmp(y - A.y) == 0;
20.     }//相等
21. };
22. 复制
23. 向量的极角
24. 极角：这里指从$x$轴旋转到向量方向的弧度
26. double PolarAngle(Vector A) {
27.     return atan2(A.y, A.x);
28. }//向量的极角
29. 复制
30. 向量的旋转
31. 若向量$(x, y)$旋转角度为$a$，则旋转后的向量为$(xcosa - ysina, y cosa + xsina)$
33. 证明：
35. 设旋转之前的向量的极角为$t$，半径为$r$
37. 那么
39. $$x = rcost$$
41. $$y = rsint$$
43. 旋转时候的向量为
45. $$x' = rcos(t + a) = r(costcosa - sintsina) = xcosa - ysina$$
47. $$y' = rsin(t + a) = r(sintcosa + costsina) = ycosa + xsina$$
49. Vector rotate(Vector &A, double a) {
50.     return A = Vector(A.x * cos(a) - A.y * sin(a), A.x * sin(a) + A.y * cos(a));
51. }//向量旋转，a为弧度
52. 复制
53. 向量的点积
54. $a \cdot b = |a||b|cos<a,b>$
56. 两向量的点积得到的是标量，即一个向量的模长乘另一个向量在该向量上正投影的数量
58. double Dot(Vector A, Vector B) {
59.     return A.x * B.x +  A.y * B.y;
60. }//两向量点积
61. 复制
62. 向量的叉积
63. $a \times b = |a||b| sin<a,b>$
65. 两向量叉积得到的是向量，在二维平面中得到的是三维空间中与这两个向量垂直的向量
67. 在平面中，向量$v$和$w$的叉积等于$v$和$w$组成的三角形的有向面积的两倍
69. 记$cross(v,w)$表示两向量的叉积，若$cross(v,w) > 0 $则说明$w$在$v$的左侧，否则$w$在$v$的右侧
71. double Cross(Vector A, Vector B) {
72.     return A.x * B.y - A.y * B.x;
73. }//两向量叉积
74. 复制
75. 计算三角形面积
76. 直接利用叉积的定义
78. double Area(Point A, Point B, Point C) {
79.     return fabs(Cross(B - A, C - A) / 2);
80. }//计算三角形的面积
81. 复制
82. 计算向量的长度
83. 直接利用点积的定义
85. double Length(Vector A) {
86.     return sqrt(Dot(A, A));
87. }//计算向量的长度
88. 复制
89. 计算向量的夹角
90. 同样直接利用点积的定义
92. double Angle(Vector A, Vector B) {
93.     return acos(Dot(A, B) / Length(A) / Length(B));
94. }//计算向量的夹角
95. 复制
96. 线段
97. 判断两直线的相对位置
98. 判断$P采用1P采用0$与$P采用1P采用2$的相对位置关系，可以转化为判断$P采用1P采用0$与$P采用2P采用0$叉积的正负性
100. int Direction(Vector P1, Vector P2, Vector P0) {
101.     int opt = Cross(P1 - P0, P2 - P0);
102.     return dcmp(opt);
103. }//判断P1-P0,P1-P2的相对位置关系，-1为逆时针，1为顺时针(P1P0顺时针旋转到P1P2)，0为共线
104. 复制
105. 判断两直线的交点
106. 尼玛看不懂
108. Point GetLineIntersection(Point P, Vector V, Point Q, Vector W) {
109.     Vector u = P - Q;
110.     double t = Cross(W, u) / Cross(V, W);
111.     return P + V * t;
112. }//判断两直线(P + tv,Q + tW)的交点(看不懂直接上y = kx + b吧)
113. 复制
114. 计算点到直线的距离
115. 利用叉积算出他们围城的平行四边形的面积，再除以底，高即为距离
117. double DistanceToLine(Point P, Point A, Point B) {
118.     Vector v1 = B - A, v2 = P - A;
119.     return fabs(Cross(v1, v2)) / Length(v1);
120. }//计算点P到直线AB的距离（平行四边形面积 / 底）
121. 复制
122. 计算点到线段的距离
123. 这个要分三种情况讨论
126. double DistanceToSegment(Point P, Point A, Point B) {
127.     if(A == B) return Length(P - A);
128.     if(dcmp(Dot(P - A, B - A)) < 0) return Length(P - A);
129.     if(dcmp(Dot(P - B, A - B)) < 0) return Length(P - B);
130.     return DistanceToLine(P, A, B);
131. }//计算点P到线段AB的距离
132. 复制
133. 多边形
134. 计算多边形的有向面积
135. 将$n$边形拆成三角形
137. double PolygonAread(Point *P, int N) {
138.     double area = 0;
139.     for(int i = 1; i <= N - 1; i++)
140.         area += Cross(P[i] - P[0], P[i + 1] - P[0]);
141.     return area / 2;
142. }//计算多边形的有向面积
143. 复制
144. 判断点是否在多边形内部
145. 基本思想：从点$P$向右做一条射线，判断从无限远处到点$P$，射线穿过了几条边
147. 有两种需要特判的情况
149. 1.射线与某条边重合，该边不统计入答案
151. 2.射线与端点重合
153. 此时，我们钦定边是由编号小的连向编号大的
155. 若边从上到下穿过了射线，包含终点不包含起点
157. 若边从下到上穿过了射线，包含起点不包含重点
159. int isPointInPolygon(Point P, Point Poly[], int N) {
160.     int wn = 0, k, d1, d2;
161.     for(int i = 0; i < N; i++) {
162.         if(!dcmp(DistanceToSegment(P, Poly[i], Poly[(i + 1) % N]))) return -1;
163.     //点在线段的边界上
164.         k = dcmp(Cross(Poly[(i + 1) % N] - Poly[i], P - Poly[i]));
165.         d1 = dcmp(Poly[i].y - P.y);
166.         d2 = dcmp(Poly[(i + 1) % N].y - P.y);
167.         if(k > 0 && d1 <= 0 && d2 > 0) wn++;//点在左，下上穿
168.         if(k > 0 && d2 <= 0 && d1 > 0) wn++;//点在右，上下穿
169.         return wn & 1; // 1：内 2：外   
170.     }   
171. }//判断点是否在多边形内部
172. 复制
173. 对踵点
174. 定义：若点对$(a, b)$均为多边形上的点且存在过$a$点的切线与过$b$点的切线平行，则成$(a, b)$为多边形上的对踵点
176. 计算方法：
178. 设$p采用{ymin}$表示$y$最小的点，$q采用{ymax}$表示$y$最大的点，显然它们是一对对踵点
181. 接下来以相同的角速度逆时针旋转两条射线，当其中的一条穿过多边形的下一个端点$p采用{next}$时，用$p采用{next}$作为新的端点，同时与$q采用{pre}$构成新的对踵点。
183. 在这个算法中，我们快速的找出两条射线究竟是哪条先穿过下一个端点，我们可以用叉积来优化这一过程。
186. 求凸多边形的直径
187. 定义：凸多边形的直径为多边形的上最远的点对的距离
189. 很显然，直径一定是在对踵点处取得，直接枚举对踵点即可
191. double RotatingCaliper采用diameter(Point Poly[], int N) {
192.     int p = 0, q = N - 1, fl;
193.     double ret = 0;
194.     for(int i = 0; i < N; i++) {
195.         if(Poly[i].y > Poly[q].y) q = i;
196.         if(Poly[i].y < Poly[p].y) p = i;
197.     }
198.     for(int i = 0; i < N * 3; i++) {
199.         ret = max(ret, Length(Poly[p % N] - Poly[q % N]));
200.         fl = dcmp(Cross(Poly[(p + 1) % N] - Poly[p % N], Poly[q % N] - Poly[(q + 1) % N]));
201.         if(!fl) {
202.             ret = max(ret, Length(Poly[p % N] - Poly[(q + 1) % N]));
203.             ret = max(ret, Length(Poly[q % N] - Poly[(p + 1) % N]));
204.             p++, q++;
205.         } else {
206.             if(fl > 0) p++;
207.             else q++;
208.         }
209.     }
210. }//计算多边形直径
211. 复制
212. 凸多边形的宽度
213. 凸多边形最小面积外接矩形
214. 凸包-Andrew算法
215. 首先按照$x$为第一关键字，$y$为第二关键字从小到大排序，并删除重复的点
217. 用栈维护凸包内的点
219. 1、把$p采用1, p采用2$放入栈中
221. 2、若$p采用{i{(i > 3)}}$在直线$p采用{i - 1}, p采用{i - 2}$的右侧，则不断的弹出栈顶，直到该点在直线左侧
223. 3、此时我们已经得到了下凸包，那么反过来从$p采用n$再做一次即可得到下凸包
225. 题目链接
227. // luogu-judger-enable-o2
228. #include<cstdio>
229. #include<cmath>
230. #include<algorithm>
231. using namespace std;
232. const int eps = 1e-10;
233. int dcmp(double x) {
234.     if(fabs(x) < eps) return 0;
235.     return x < 0 ? -1 : 1;
236. }
237. #define Point Vector
238. struct Vector {
239.     double x, y;
240.     Vector(double x = 0, double y = 0) : x(x), y(y) {};
241.     bool operator < (const Vector &rhs) const {
242.         return dcmp(x - rhs.x) == 0 ? y < rhs.y : x < rhs.x;
243.     }
244.     Vector operator - (const Vector &rhs) const {
245.         return Vector(x - rhs.x, y - rhs.y);
246.     }
247. };
248. double Cross(Vector A, Vector B) {
249.     return A.x * B.y - A.y * B.x;
250. }
251. double dis(Point a, Point b) {
252.     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
253. }
254. int N;
255. Point p[10001], q[10001];
256. int top;
257. void Push(Point p) {
258.     while(Cross(q[top] - q[top - 1], p - q[top - 1]) < 0) top--;
259.     q[++top] = p;
260. }
261. void Andrew() {
262.     q[0] = q[top = 1] = p[1];
263.     for(int i = 2; i <= N; i++) Push(p[i]);
264.     for(int i = N - 1; i; --i)  Push(p[i]);
265. }
266. int main() {   
267.     scanf("%d", &N);
268.     for(int i = 1; i <= N; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
269.     sort(p + 1, p + N + 1);
270.     Andrew();
271.     double ans = 0;
272.     for(int i = 1; i < top; i++)
273.         ans += dis(q[i], q[i + 1]);
274.     printf("%.2lf", ans);
275.     return 0;
276. }
277. 复制
278. 要做的题
279. POJ 2187 凸多边形直径
281. #include<cstdio>
282. #include<cmath>
283. using namespace std;
284. const int eps = 1e-10;
285. int dcmp(double x) {
286.     if(fabs(x) < eps) return 0;
287.     return x < 0 ? -1 : 1;
288. }
289. #define Point Vector
290. struct Vector {
291.     double x, y;
292.     Vector(double x = 0, double y = 0) : x(x), y(y) {};
293.     Vector operator + (const Vector &A) const {
294.         return Vector(x + A.x, y + A.y);
295.     }//向量的加法
296.     Vector operator - (const Vector &A) const {
297.         return Vector(x - A.x, y - A.y);
298.     }//减法
299.     Vector operator * (const double &A) const {
300.         return Vector(x * A, y * A);
301.     }//数乘
302.     Vector operator / (const double &A) const {
303.         return Vector(x / A, y / A);
304.     }//数除
305.     bool operator == (const Vector &A) const  {
306.         return dcmp(x - A.x) == 0 && dcmp(y - A.y) == 0;
307.     }//相等
308. };
309. double PolarAngle(Vector A) {
310.     return atan2(A.y, A.x);
311. }//向量的极角
312. Vector rotate(Vector &A, double a) {
313.     return A = Vector(A.x * cos(a) - A.y * sin(a), A.x * sin(a) + A.y * cos(a));
314. }//向量旋转，a为弧度
315. double Dot(Vector A, Vector B) {
316.     return A.x * B.x +  A.y * B.y;
317. }//两向量点积
318. double Cross(Vector A, Vector B) {
319.     return A.x * B.y - A.y * B.x;
320. }//两向量叉积
321. double Area(Point A, Point B, Point C) {
322.     return fabs(Cross(B - A, C - A) / 2);
323. }//计算三角形的面积
324. double Length(Vector A) {
325.     return sqrt(Dot(A, A));
326. }//计算向量的长度
327. double Angle(Vector A, Vector B) {
328.     return acos(Dot(A, B) / Length(A) / Length(B));
329. }//计算向量的夹角
330. int Direction(Vector P1, Vector P2, Vector P0) {
331.     int opt = Cross(P1 - P0, P2 - P0);
332.     return dcmp(opt);
333. }//判断P1-P0,P1-P2的相对位置关系，-1为逆时针，1为顺时针(P1P0顺时针旋转到P1P2)，0为共线
334. Point GetLineIntersection(Point P, Vector V, Point Q, Vector W) {
335.     Vector u = P - Q;
336.     double t = Cross(W, u) / Cross(V, W);
337.     return P + V * t;
338. }//判断两直线(P + tv,Q + tW)的交点(看不懂直接上y = kx + b吧)
339. double DistanceToLine(Point P, Point A, Point B) {
340.     Vector v1 = B - A, v2 = P - A;
341.     return fabs(Cross(v1, v2)) / Length(v1);
342. }//计算点P到直线AB的距离（平行四边形面积 / 底）
343. double DistanceToSegment(Point P, Point A, Point B) {
344.     if(A == B) return Length(P - A);
345.     if(dcmp(Dot(P - A, B - A)) < 0) return Length(P - A);
346.     if(dcmp(Dot(P - B, A - B)) < 0) return Length(P - B);
347.     return DistanceToLine(P, A, B);
348. }//计算点P到线段AB的距离
349. double PolygonAread(Point *P, int N) {
350.     double area = 0;
351.     for(int i = 1; i <= N - 1; i++)
352.         area += Cross(P[i] - P[0], P[i + 1] - P[0]);
353.     return area / 2;
354. }//计算多边形的有向面积
355. int isPointInPolygon(Point P, Point Poly[], int N) {
356.     int wn = 0, k, d1, d2;
357.     for(int i = 0; i < N; i++) {
358.         if(!dcmp(DistanceToSegment(P, Poly[i], Poly[(i + 1) % N]))) return -1;
359.     //点在线段的边界上
360.         k = dcmp(Cross(Poly[(i + 1) % N] - Poly[i], P - Poly[i]));
361.         d1 = dcmp(Poly[i].y - P.y);
362.         d2 = dcmp(Poly[(i + 1) % N].y - P.y);
363.         if(k > 0 && d1 <= 0 && d2 > 0) wn++;//点在左，下上穿
364.         if(k > 0 && d2 <= 0 && d1 > 0) wn++;//点在右，上下穿
365.         return wn & 1; // 1：内 2：外   
366.     }   
367. }//判断点是否在多边形内部
369. int main() {   
370.         
371.     return 0;
372. }
375. https://cloud.tencent.com/developer/article/1172724?areaId=106001

复制代码