分类: 计算几何

7 篇文章

第一节 计算几何点类
norm() 计算向量的模长 db det(const pt &a, const pt &b) 计算两个向量的叉积 db dot(const pt &a, const pt &b) 计算两个向量的点积 db dist(const pt &a, const pt &b) 计算两个点的距离 pt rota…
第二节 计算几何线类
db dis_pt_seg(const pt p, const pt s, const pt t) 求点 p 到线段 st 的距离 pt pt_projline(const pt p, const pt s, const pt t) 求点 p 到线段 st 的垂足 bool pt_on_seg(pt p, pt s, pt t) 判断点 p 是否在…
第三节 计算几何多边形类
db cir() 计算多边形周长 db dir_area() 计算多边形有向面积 db area() 计算多边形面积 void fix() 如果点是以顺时针顺序存储,则改为逆时针 int poly::point_in(pt t) 判断点和多边形的关系:0 在外面,1 在内部,2 在边上 int poly::Border_pt_num() 计算多边形…
第四节 凸包
凸包类 conv get_convex(vector<pt> a) 用点集求出凸包(逆时针保存) bool isconvex(const vector<pt> &a) 对给定的点集(顺逆时针均可),判断是否构成凸包 bool containOn(const conv &a, const pt &b) …
第五节 半平面交
conv cut(conv &a) 用此半平面切割凸包,返回新的凸包 conv core(poly &a) 返回多边形 a 的核(站在核中的点,可以看到多边形内的任意一点) conv conv_inter(vector<poly> &a) 返回 $n$ 个多边形的交(多边形需要逆时针存储) 例题:P4196【模板…
第六节 圆
圆类 Circle getCircle(pt A, pt B, pt C) 三点确定一个圆 Circle minCover(vector<pt> &p) 求点集 p 的最小圆覆盖 db SPICA(Circle C, vector<pt> &p) 求圆 C 和多边形 p 的面积交 struct Circle …
第七节 其他
三维计算几何 Point_3 rotate(Point_3 a, Vec_3 b, db angle) 向量 oa 以向量 b 为轴逆时针旋转 angle 度 #include <bits/stdc++.h> using namespace std; typedef double db; const db eps = 1e-8; inl…