点,线,向量,多边形,凸包,圆 --- 计算几何模板

74 阅读 0 评论 49 点赞

我是靠谱客的博主淡淡路灯，最近开发中收集的这篇文章主要介绍点,线,向量,多边形,凸包,圆 --- 计算几何模板，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

计算几何模板

全是纯干货,方法理解可查阅算法入门到进阶一书 !

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);//高精度圆周率
const double eps = 1e-8;//偏差值
const int maxp = 1010;//点的数量
//判断是否等于零，返回0为等于零，返回-1为小于，1为大于
int sgn(double x) {
if (fabs(x) < eps)return 0;
else return x < 0 ? -1 : 1;
}
//判断是否相等，返回0为相等，返回-1为小于，1为大于
int dcmp(double x, double y) {
if (fabs(x - y) < eps)return 0;
else return x < y ? -1 : 1;
}
//---------平面几何：点和线--------------
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator+(Point B) { return Point(x + B.x, y + B.y); }
Point operator-(Point B) { return Point(x - B.x, y - B.y); }
Point operator*(double k) { return Point(x * k, y * k); }//放大k倍
Point operator/(double k) { return Point(x / k, y / k); }//缩小k倍
bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
bool operator<(Point B) {return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0); }//用于对顶点的排序
friend bool operator < (Point a,Point b){
return sgn(a.x - b.x) < 0 || (sgn(a.x - b.x) == 0 && sgn(a.y - b.y) < 0);
}
};
bool cmpxy(Point A,Point B){ //先对x排序再对y排序
return sgn(A.x - B.x) < 0 || (sgn(A.x - B.x) == 0 && sgn(A.y - B.y) < 0);
}
bool cmpy(Point A, Point B) { return sgn(A.y - B.y) < 0; } //只对y坐标排序
//两点距离
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y);}
//二维向量
typedef Point Vector;
//向量点积
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y;}
//向量长度
double vector_length(Vector A) { return sqrt(Dot(A, A));}
//向量长度平方
double vector_length_square(Vector A) { return Dot(A, A);}
//向量夹角
double Angle(Vector A, Vector B) {
return acos(Dot(A, B) / vector_length(A) / vector_length(B));
}
//向量叉积；大于0，B在A逆时针方向；等于0，A、B重合
double Cross(Vector A, Vector B) {
return A.x * B.y - A.y * B.x;
}
//三点构成平行四边形面积(A为公共点)
double Area(Point A, Point B, Point C) {
return Cross(B - A, C - A);
}
//向量逆时针旋转
Vector Rotate(Vector A, double rad) {
return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
//向量顺时针旋转
Point rotate(Point a, double angle){
return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) * cos(angle));
}
//逆时针旋转90度 : rotate(A, pi /2),返回 vector(-A.y, A.x);
//顺时针旋转90度 : rotate(A, - pi /2),返回 vector(A.y, - A.x);
//单位法向量
Vector Normal(Vector A) {
return Vector(-A.y / vector_length(A), A.x / vector_length(A));
}
//检查向量平行或重合
bool Parallel(Vector A, Vector B) {
return sgn(Cross(A, B)) == 0;
}
//ToLeftTest
//判断折线bc是不是向ab的逆时针方向（左边）转向凸包构造时将会频繁用到此公式
bool ToLeftTest(Point a, Point b, Point c){
return Cross(b - a, c - b) > 0;
}
//直线
//点向式(根据参数t来控制)
struct Line {
Point v, p;
Line(Point v, Point p) : v(v), p(p) {}
Point point(double t){
return v + (p - v) * t;
}
};
struct Line {
Point p1, p2;
Line() {}
//根据端点确定直线
Line(Point p1, Point p2) : p1(p1), p2(p2) {}
//根据一个点和倾斜角angel确定直线，0 <= angel < pi
Line(Point p, double angel) {
p1 = p;
if (sgn(angel - pi / 2) == 0)p2 = (p1 + Point(0, 1));
else p2 = p1 + Point(1, tan(angel));
}
//ax + by + c = 0
Line(double a, double b, double c) {
if (sgn(a) == 0) {
p1 = Point(0, -c / b);
p2 = Point(1, -c / b);
} else if (sgn(b) == 0) {
p1 = Point(-c / a, 0);
p2 = Point(-c / a, 1);
} else {
p1 = Point(0, -c / b);
p2 = Point(1, (-c - a) / b);
}
}
};
//线段，p1起点，p2终点
typedef Line Segment;
//点和直线关系:1 在左侧;2 在右侧;0 在直线上。根据视线从p1向p2看的左右
int Point_line_relation(Point p, Line v) {
int c = sgn(Cross(p - v.p1, v.p2 - v.p1));
if (c < 0)return 1;
//1：p在v的左边
if (c > 0)return 2;
//2：p在v的右边
return 0;
//0：p在v上
}
// 点和线段的关系：0 点p不在线段v上；1 点p在线段v上。
bool on_segment(Point p, Point a, Point b) {
return sgn(Cross(p - a, p - b)) == 0 && sgn(Dot(p - a, p - b)) <= 0;
}
bool Point_on_seg(Point p, Line v) {
return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(Dot(p - v.p1, p - v.p2)) <= 0;
}
//点到直线的距离
double Dis_point_line(Point p, Line v) {
return fabs(Cross(p - v.p1, v.p2 - v.p1)/ Distance(v.p1, v.p2));
}
//点在直线上的投影
Point Point_line_proj(Point p, Line v) {
double k = Dot(v.p2 - v.p1, p - v.p1) / vector_length_square(v.p2 - v.p1);
return v.p1 + (v.p2 - v.p1) * k;
}
//点p对直线v的对称点
Point Point_line_symmetry(Point p, Line v) {
Point q = Point_line_proj(p, v);
return Point(2 * q.x - p.x, 2 * q.y - p.y);
}
//点到线段的距离
double Dis_point_seg(Point p, Segment v) {
if (sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0) //点的投影不在线段上
return min(Distance(p, v.p1), Distance(p, v.p2));
return Dis_point_line(p, v); //点的投影在线段上
}
//两直线关系:0 平行,1 重合,2 相交
int Line_relation(Line v1, Line v2) {
if (sgn(Cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
if (Point_line_relation(v1.p1, v2) == 0) return 1;//1 重合
else return 0;//0 平行
}
return 2; //2 相交
}
//求两直线ab和cd的交点
//调用前要保证两直线不平行或重合
//叉积为零则平行或重合
Point Cross_point(Point a, Point b, Point c, Point d) { //Line1:ab,
Line2:cd
double s1 = Cross(b - a, c - a);
double s2 = Cross(b - a, d - a);
//叉积有正负
return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}
//两线段是否相交：1 相交，0不相交
bool Cross_segment(Point a, Point b, Point c, Point d) {//Line1:ab,
Line2:cd
double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a);
double d1 = Cross(d - c, a - c), d2 = Cross(d - c, b - c);
return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;//注意交点是端点的情况不算在内
}
//---------------平面几何：多边形----------------
struct Polygon {
int n;
//多边形的顶点数
Point p[maxp];
//多边形的点
Line v[maxp];
//多边形的边
};
//判断点和任意多边形的关系: 3 点上; 2 边上; 1 内部; 0 外部
int Point_in_polygon(Point pt, Point *p, int n) { //点pt，多边形Point *p
for (int i = 0; i < n; i++) {
//点在多边形的顶点上
if (p[i] == pt)return 3;
}
for (int i = 0; i < n; i++) {//点在多边形的边上
Line v = Line(p[i], p[(i + 1) % n]);
if (Point_on_seg(pt, v)) return 2;
}
int num = 0;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
int c = sgn(Cross(pt - p[j], p[i] - p[j]));
int u = sgn(p[i].y - pt.y);
int v = sgn(p[j].y - pt.y);
if (c > 0 && u < 0 && v >= 0) num++;
if (c < 0 && u >= 0 && v < 0) num--;
}
return num != 0; //1 内部; 0 外部
}
int pointin(Point p,Point* a,int n) {
int wn = 0;
for (int i = 0;i < n;i ++) {
if (sgn(on_segment(p, a[i], a[(i+1)%n]))==0)
return -1;//判断点是否在多边形的边界上
int k = sgn(Cross(a[(i+1-1)%n+1]-a[i], p-a[i]));
int d1 = sgn(a[i].y-p.y);
int d2 = sgn(a[(i+1-1)%n+1].y-p.y);
if (k>0 && d1<=0 && d2>0)
wn++;
if (k<0 && d2<=0 && d1>0)
wn--;
}
if (wn)
return 1;
else return 0;
}
//多边形面积
double Polygon_area(Point *p, int n) { //Point *p表示多边形。从原点开始划分三角形
double area = 0;
for (int i = 0; i < n; i++)
area += Cross(p[i], p[(i + 1) % n]);
return area / 2;
//面积有正负，不能简单地取绝对值
}
double PolyArea(vector<Point> p){
int n=p.size();
double ans=0;
for(int i=1;i<n-1;i++)
ans+=Cross(p[i]-p[0],p[i+1]-p[0]);
return fabs(ans)/2;
}
//多边形重心
//将多边形三角剖分，算出每个三角形重心（三角形重心是3点坐标平均值）
//对每个三角形有向面积求加权平均值
Point Polygon_center(Point *p, int n) { //求多边形重心。Point *p表示多边形。
Point ans(0, 0);
if (Polygon_area(p, n) == 0) return ans;
for (int i = 0; i < n; i++)
ans = ans + (p[i] + p[(i + 1) % n]) * Cross(p[i], p[(i + 1) % n]); //面积有正负
return ans / Polygon_area(p, n) / 6.;
}
//凸包
int Convex_hull(Point *p,int n,Point *ch){
sort(p, p + n);//对点排序
n = unique(p, p + n) - p;//去重
int v = 0;
//求下凸包,如果p[i]是右拐弯,这个点不在凸包上往回退
for (int i = 0; i < n;i ++){
while(v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2],p[i] - ch[v - 2])) <= 0)
v--;
ch[v++] = p[i];
}
int j = v;
//求上凸包
for (int i = n - 2; i >= 0;i --){
while(v > j && sgn(Cross(ch[v - 1] - ch[v - 2],p[i] - ch[v - 2])) <= 0)
v--;
ch[v++] = p[i];
}
if(n > 1) v--;
return v; //返回凸包顶点数
}
//---------------平面几何：圆----------------
struct Circle{
Point c;
double r;
Circle(){};
Circle(Point c, double r) : c(c), r(r){};
Circle(double x, double y, double _r) { c = Point(x, y); r = _r;}
};
//点和圆的关系根据点到圆心的距离判断
int Point_circle_relation(Point p,Circle C){
double dst = Distance(p, C.c);
if(sgn(dst - C.r) < 0) return 0; //点在园内
if(sgn(dst - C.r) == 0) return 1; //点在圆上
return 2; //点在圆外
}
//直线和圆的关系根据圆心到直线的距离判断
int Line_circle_relation(Line v,Circle C){
double dst = Dis_point_line(C.c, v);
if(sgn(dst - C.r) < 0) return 0; //直线与圆相交
if (sgn(dst - C.r) == 0) return 1; //直线与圆相切
return 2; //直线在圆外
}
//线段和圆的关系根据圆心到线段的距离判断
int Seg_circle_relation(Segment v,Circle C){
double dst = Dis_point_seg(C.c, v);
if(sgn(dst - C.r) < 0) return 0; //线段在园内
if(sgn(dst - C.r) == 0) return 1; //线段在圆上
return 2; //线段在圆外
}
//直线和圆的交点pa,pb是交点,返回值是交点个数
//先求圆心c在直线上的投影q.再求距离d,然后根据r和d求出长度k,最后求出两个交点pa = q + n*k,pb = q - n * k;其中n是直线的单位向量
int Line_cross_circle(Line v,Circle C,Point &pa,Point &pb){
if(Line_circle_relation(v,C) == 2) return 0;
Point q = Point_line_proj(C.c, v);
double d = Dis_point_line(C.c, v);
double k = sqrt(C.r * C.r - d * d);
if(sgn(k) == 0){
pa = q;pb = q;return 1;
}
Point n = (v.p2 - v.p1) / vector_length(v.p2 - v.p1);
pa = q + n * k;
pb = q - n * k;
return 2;
}
//
int main() {
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
return 0;
}