Computational geometry (4.17)

Computational geometry

1. Pre knowledge ：

   1. pi = acos(-1)
      

   2. Cosine theorem ：$c^2=a^2+b^2-2abcos(t)$

2. Floating point comparison .

   const double eps = 1e-8;
   int sign(double x){
         
       if(fabs(x)<eps)return 0;
       if(x<0)return -1;
       return 1;
   }
   

   int cmp(double x,double y){
         
       if(fabs(x-y)<eps)return 0;
       if(x<y)return -1;
       return 1;
   }
   

3. vector

   1. The addition, subtraction and multiplication of vectors .

   2. Inner product （ Dot product ） $A\cdot B=|A||B|cos(C)$

      Geometric meaning ： vector A In vector B The projection multiplication vector on B The length of .

      double dot(Point a,Point b){
              
          return a.x*b.x+a.y*b.y;
      }
      

   3. Exoproduct （ Cross product ）$A\times B=|A||B|sin(C)$ （ Determinant push ）

      Geometric meaning ： vector A and B The area of a parallelogram ( Directed area ) Half of . The direction follows the rule .

      double cross(Point a,Point b){
              
          return a.x*b.y-a.y*b.x
      }
      

4. Common functions extended from dot product and cross product .

   1. Find the length of the vector .

      double get_length(Point a){
              
          return sqrt(dot(a,a));
      }
      

   2. Calculate the included angle of the vector

      double get_angle(Point a,Point b){
              
          return acos(dot(a,b)/get_length(a)/get_length(b));
      }
      

   3. Calculate the area of parallelogram

      double get_area(Point a,Point b,Point c){
              
      	return cross(a-b,c-b);
      }
      

   4. Rotate a vector by an angle .

      take $(x,y)$ Rotate one clockwise $\theta$ horn .
      $$\left[\begin{array}{c}x,y\end{array}\right]\left[\begin{array}{cc}cos(\theta )& -sin(\theta )\\ sin(\theta )& cos(\theta )\end{array}\right]=[xcos(\theta )+ysin(\theta ),-xsin(\theta )+ycos(\theta )]$$

5. Points and lines

   1. Straight line theorem .

      1. General style $ax+by+c=0$
      2. Pointwise ( Most used )$p_0(renIt\; meansOneindividualspot)+\overline{v}(too{p}_{0}OfNot0towardsThe\; amount)\ast t$
      3. Oblique section type $y = kx+b

   2. Judge whether the point is on a straight line .

      $A\times B=0$ Express $aspotandtowardsThe\; amountBOnOfsomeindividualspotGroupbecomeOftowardsThe\; amountAandBthearoundbecomeOf3、\; ...\; andhornshapeOfNoodlesproductyes0$ , Indicates that the point is on a straight line .

   3. Two straight lines intersect , Find the intersection .

      $cross(v,w)==0$ It is specially judged that two straight lines are parallel or coincide .( Used similarity to prove )

      Point get_intersection(Point p,Vector v,Point q,Vector w){
              
          Vector u = p-q;
          double t = cross(w,u)/cross(v,w);
          return p+v*t;
      }
      

   4. The distance between a point and a line .

      double distance_to_line(Point a,Point b,Point c){
              
          Vector v1 = b-a;
          Vector v2 = c-a;
          return fabs(cross(v1,v2))/getlength(v1);// The area divided by the length of the bottom side is the height .
      }
      

   5. The distance between a point and a line segment . Two special cases are specially judged .

      double distance_to_segment(Point p,Point a,Point b){
              
          if(a==b)return get_length(p-a);
          Vector v1 = b-a,v2=p-a,v3=p-b;
          if(sign(dot(v1,v2))<0)return get_length(v2);
      	if(sign(dot(v1,v3))>0)return get_length(v3);
          return distance_to_line(p,a,b);
      }
      

   6. Projection from point to line .

      Point get_line_projection(Point P,Point a,Point b){
              
      	Vector v = b-a;
          return a+v*(dot(v,p-a)/dot(v,v));
      }
      

   7. Whether the point is on the line segment .

      bool on_segment(Point p,Point a,Point b){
              
          //  Line segment is a->b, Judge p Whether it is on the line segment . Satisfy p On line segments , And p stay [a,b] middle .
          return sign(cross(p-a),cross(p-b)) == 0 && sign(dot(p-a,p-b))<=0;
      }
      

   8. Judge whether two line segments intersect （ Straddle experiment ）

      bool segment_intersection(Point a1,Point a2,Point b1,Point b2){
              
          double c1 = cross(a2-a1,b1-a1);
          double c2 = cross(a2-a1,b2-a1);
          double c3 = cross(b2-b1,a2-b1);
          double c4 = cross(b2-b1,a1-b1);
          return sign(c1)*sign(c2)<=0 && sign(c3)*sign(c4)<=0;
      }
      

6. polygon .

   1. The four centers of a triangle .

      1. Outside the heart ： The center of a triangle circumscribed circle , The intersection of the vertical lines on three sides , The distance to the three vertices of the triangle is equal .
      2. inner ： The center of the inscribed circle , Intersection of angular bisectors , Equal distance to three sides .
      3. orthocenter ： The intersection of three perpendicular feet .
      4. Focus ： The intersection of the three central lines .（ The point where the sum of squares of the distances to the three vertices of a triangle is the smallest , The point where the product of the distance from the triangle to the three sides is the largest ）.

   2. Definition ： In the same plane , Not in the same straight line , A figure in which multiple line segments are connected sequentially from beginning to end and do not intersect .

   3. Simple polygon ： Except adjacent edges , Other edges do not intersect .

   4. Convex polygon ：

      Make a straight line across any edge of the polygon , If all the other vertices are on one side of this edge , It's a convex polygon .

      1. The sum of the outer corners of an arbitrary convex polygon is 360 degree .
      2. The sum of the interior angles of an arbitrary convex polygon is $(n-2)\ast 180$ degree .

   5. Common functions ：

      1. Find the area of an arbitrary polygon .

         You can triangulate polygons , Divide into $n-2$ Triangles , Reverse all edges , Or sort in order .

      2. You can choose any point on the plane , In order of edges , Traverse every edge , By finding the cross product of two vectors , Get the area sum of the polygon .（ Using the property that the cross product area has positive and negative , Very clever ）

         double polygon_area(Point p[],int n){
                   
             //  When taking any point , Generally, take the first point of the polygon p[0]
             double s=0;
             for(int i=1;i<n-1;i++){
                   
                 s += cross(p[i]-p[0],p[i+1]-p[i]);
             }
             return s/2;
         }
         

      3. Determine whether a point is within a polygon （ It can be arbitrary polygon ）

         Ray method or Corner method

         Ray method ： From this point, make an arbitrary ray that is not parallel to all edges , The number of intersections is even , The point is outside the polygon , Otherwise in the polygon .

      4. Judge whether a point is Convex polygon Inside （ Convex polygons are stored counterclockwise ）

         Judge whether the point is on the left side of the convex polygon .（ Cross product ）

   6. Pike theorem

      ​ requirement ： All points of the polygon must be on the grid .

      ​ $s=a+\frac{b}{2}-1$ .

      ​ $a：$ The number of whole points inside the polygon .

      ​ $b:$ The number of whole points on the edge of the polygon .