二维几何基础

struct Point{
    double x,y;
    Point(double x=0, double y=0):x(x),y(y) {}  //构造函数，方便代码编写 
};

typedef Point Vector; //用别名区分点与向量

//向量+向量=向量， 点+向量=点 
Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); }
//点-点=向量 向量-向量=向量
Vector operator - (Point A, Point B){ return Vector(A.x+B.x, A.y+B.y); }
//向量*数=向量
Vector operator * (Vector A, double p){return Vector(A.x*p, A.y*p); } 
//向量/数=向量
Vector operator / (Vector A, double p){return Vector(A.x/p, A.y/p); }

bool operator < (const Point &a, const Point &b){//重载'<',先排x后排y，亦可以看作以极角排序 
    return a.x < b.x || (a.x==b.x && a.y<b.y);
}  

const double eps = 1e-10;
int dcmp(double x){
    if(fabs(x) < eps) return 0; else return x<0 ? -1:1;
}

bool operator == (const Point &a, const Point &b){
    return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}

1. 两向量垂直（cos = 0），a * b = 0
2. 平面坐标系下，点积等于XaXb + YaYb
3. 代码

   double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }//平面直角坐标系上向量点积 
   double Length(Vector A) {return sqrt(Dot(A,A));} //x方加y方的和的算术平方根为向量的模长 
   double Angle(Vector A, Vector B){ return acos(Dot(A,B) / Length(A) / Length(B)); } //点积除以模长的积等于cos(a,b); 

1. b在a左边时，叉积大于0；在右边时小于0（absin(a,b) 逆时针）
2. 平面直角坐标系上，叉积等于XaYb – XbYa
3. 代码

   double Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; }//平面直角坐标系上两向量外积
   double Area2(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));} 
  

• Vector Normal(Vector A){ //确保不是零向量方可使用 
      double L = Length(A);
      return Vector(-A.y/L, A.x/L);
  }

• t1=cross(w,u)/cross(v,w)
• t2=cross(v,u)/cross(v,w)

• //调用前确保两条直线有唯一交点（方向向量不平行重叠）
  Point Getlineintersection(Point P, Vector v, Point Q, Vector w){
      Vector u = P-Q;
      double t = Cross(w,u) / Cross(v, w);
      return P + v*t;
  }
  

double Distancetoline(Point P, Point A, Point B){
    Vector v1 = B - A, v2 = P - A; //得向量AB，向量PA
    return fabs(Cross(v1, v2)) / Length(v1); 
}

1. 如图，向量AB与AP的点积小于0时，距离为AP的模
2. 如图，向量AB与BP的点积大于0时，距离为BP的模
3. 如图，向量AB在线段正上方时，不满足以上两个条件，距离即为点到直线的距离

4. double distancetosegment(Point P, Point A, Point B){
       if(A==B) return Length(P-A);
       Vector v1 = B-A, v2 = P-A, v3 = P-B;
       if(dcmp(Dot(v1,v2)) < 0) return Length(v2); else if(dcmp(Dot(v1,v3)) > 0) return Length(v3);
       else return fabs(Cross(v1,v2) / Length(v1));
   }

• 将AB写成参数式A+tv(v为向量AB)，设Q的参数为t。， 那么Q=A+vt。，由点积为0可得Dot(v,p-(A+vt。)) = 0,这样就可以解出t。

• Point getlineprojection(Point P, Point A, Point B){
      Vector v = B-A;
      return A+v*(Dot(v,P-A) / Dot(v,v));
  }

• 规范相交：两线段恰好有一个公共点，且不在任何一条线段的端点
• 规范相交的充要条件是：每条线段的两个端点都在另一条线段的两侧（这里的“两侧”是指叉积的符号不同）
• 可以用线段的两点式求出线性规划，代入另外两点
  但鉴于代码风格的统一性，这里还是使用书上使用向量外积进行判断的代码，两种方法本质上是一样的，都是分别以一条边为标准（所以需要判断两次），判断另外两个点是否在该边的两侧。

• bool segmentpropersection(Point a1, Point a2, Point b1, Point b2){
      double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1),
      c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
      return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4) < 0;
  }
  

• 如果允许出现在端点处呢？那就需要再进一步的讨论：
  如果c1，c2都等于0，则两线段共线，有可能部分重叠；若不都为0，则必然只有一种相交情况，即某个端点再另一条线段上，用如下代码进行判断（不含端点，因为端点重合的话可以直接看出来…）：

• bool onsegment(Point P, Point a1, Point a2){
      return dcmp(Cross(a1-P, a2-P)) == 0 && dcmp(Dot(a1-P, a2-P)) < 0;
      //第一个条件用来判断点在直线上，第二个条件用来判断点在被两条垂足为AB端点的直线围成的区域内
      //合在一起用来判断点端在线段上 
  }
  

• https://www.cnblogs.com/xiexinxinlove/p/3708147.html
• 
• 
• 
• 
• 

• double polygonarea(Point *p, int n){
      double area = 0;
      for(int i = 1; i < n-1; i++){
          area += Cross(p[i]-p[0], p[i+1]-p[0]);
      }
      return area/2;
  }