matbensch

Computational Geometry C++

Feb 9th, 2023
1,077
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. double EPS = 1e-9;
  9.  
  10. struct point
  11. {
  12.     double x,y;
  13.     point(){x=y=0;};
  14.    
  15.     point(int x, int y)
  16.     {
  17.         this->x = x;
  18.         this->y = y;
  19.     }
  20.  
  21.     bool operator == (const point& other) const
  22.     {
  23.         return (fabs(x-other.x) < EPS) && (fabs(y - other.y) < EPS);
  24.     }
  25.  
  26.     bool operator < (point other) const
  27.     {
  28.         if(fabs(x-other.x)>EPS) return x < other.x;
  29.         return y<other.y;
  30.     }
  31.  
  32. };
  33.  
  34. double dist(const point& p1, const point& p2)
  35. {
  36.     return hypot(p1.x-p2.x, p1.y-p2.y);
  37. }
  38.  
  39. struct line{ double a,b,c; };
  40.  
  41. void pointsToLine(const point& p1, const point& p2, line& l)
  42. {
  43.     if(fabs(p1.x-p2.x) < EPS)
  44.         l = {1, 0, -p1.x};
  45.     else
  46.         l = {
  47.             -(p2.y-p1.y) / (p2.x-p1.x),
  48.             1,
  49.             (p2.y-p1.y) / (p2.x-p1.x)*p1.x - p1.y
  50.         };
  51. }
  52.  
  53. void pointSlopeToLine(point p, double m, line& l)
  54. {
  55.     l.a = -m;
  56.     l.b = 1.0;
  57.     l.c = -((l.a*p.x) + (l.b*p.y));
  58. }
  59.  
  60. bool areParallel(line l1, line l2)
  61. {
  62.     return (fabs(l1.a - l2.a) < EPS) && (fabs(l1.b - l2.b) < EPS);
  63. }
  64.  
  65. bool areSame(line l1, line l2)
  66. {
  67.     return areParallel(l1,l2) && (fabs(l1.c - l2.c) < EPS);
  68. }
  69.  
  70. bool areIntersect(line l1, line l2, point& p)
  71. {
  72.     if(areParallel(l1,l2)) return false;
  73.  
  74.     p.x = (l2.b*l1.c - l1.b*l2.c) / (l2.a*l1.b - l1.a * l2.b);
  75.  
  76.     if(fabs(l1.b)>EPS)  p.y = -(l1.a*p.x + l1.c);
  77.     else                p.y = -(l2.a*p.x + l2.c);
  78.    
  79.     return true;
  80. }
  81.  
  82. struct vec
  83. {
  84.     double x,y;
  85.     vec(double x, double y)
  86.     {
  87.         this->x = x;
  88.         this->y = y;
  89.     }
  90. };
  91.  
  92. // return the vector from point a to point b
  93. vec toVec(const point& a, const point& b)
  94. {
  95.     return vec(b.x-a.x, b.y-a.y);
  96. }
  97.  
  98. // scale the vector v by a factor of scalar s
  99. vec scale(const vec& v, double s)
  100. {
  101.     return vec(s*v.x, s*v.y);
  102. }
  103.  
  104. // translate the point p according to vector v
  105. point translate(const point& p, const vec& v)
  106. {
  107.     return point(p.x+v.x, p.y+v.y);
  108. }
  109.  
  110. double dot(vec a, vec b) { return a.x*b.x + a.y*b.y; }
  111. double norm_sq(vec v) { return v.x*v.x + v.y*v.y; }
  112.  
  113. double angle(const point& a, const point& o, const point& b)
  114. {
  115.     vec oa = toVec(o, a), ob = toVec(o, b);
  116.     return acos(dot(oa, ob) / sqrt( norm_sq(oa) * norm_sq(ob) ) );
  117. }
  118.  
  119. double cross(vec a, vec b){ return a.x*b.y - a.y*b.x; }
  120. bool ccw(point p, point q, point r){ return cross(toVec(p,q), toVec(p,r)) > EPS; }
  121. bool collinear(point p, point q, point r){ return fabs(cross(toVec(p,q), toVec(p,r))) < EPS; }
  122.  
  123. double perimeter(const vector<point>& P)
  124. {
  125.     double ans = 0;
  126.    
  127.     for(int i=0; i < P.size()-1; i++)
  128.         ans += dist(P[i], P[i+1]);
  129.    
  130.     return ans;
  131. }
  132.  
  133. double area(const vector<point>& P)
  134. {
  135.     double ans = 0;
  136.    
  137.     for(int i=0;i<P.size()-1;i++)
  138.         ans += (P[i].x*P[i+1].y - P[i+1].x*P[i].y);
  139.    
  140.     return fabs(ans)/2.0;
  141. }
  142.  
  143. // returns 1 if pt inside, 0 if pt on, and -1 if pt outside P
  144. int insidePolygon(point pt, const vector<point>& P)
  145. {
  146.     int n = P.size();
  147.     if(n<=3) return -1;
  148.     for(int i=0;i<n-1;i++)
  149.         if(fabs( dist(P[i], pt) + dist(pt, P[i+1]) - dist(P[i],P[i+1]) ) < EPS )
  150.             return 0;
  151.    
  152.     double sum = 0;
  153.     for(int i=0;i<n-1;i++)
  154.     {
  155.         if(ccw(pt, P[i], P[i+1]))
  156.             sum += angle(P[i], pt, P[i+1]);
  157.         else
  158.             sum -= angle(P[i], pt, P[i+1]);
  159.     }
  160.  
  161.     return fabs(sum) > 3.14 ? 1 : -1;
  162.  
  163. }
  164.  
  165. // O(n log n)
  166. vector<point> CH_Graham(vector<point>& Pts)
  167. {
  168.     vector<point> P(Pts);
  169.     int n = (int)P.size();
  170.     if(n<=3)
  171.     {
  172.         if(!(P[0]==P[n-1])) P.push_back(P[0]);
  173.         return P;
  174.     }
  175.  
  176.     int P0 = min_element(P.begin(), P.end()) - P.begin();
  177.     swap(P[0], P[P0]);
  178.  
  179.     sort(++P.begin(), P.end(), [&](point a, point b) {
  180.         return ccw(P[0],a,b);
  181.     });
  182.  
  183.     vector<point> S({P[n-1], P[0], P[1]});
  184.     int i = 2;
  185.     while(i<n)
  186.     {
  187.         int j = S.size()-1;
  188.         if(ccw(S[j-1], S[j], P[i])) S.push_back(P[i++]);
  189.         else S.pop_back();
  190.     }
  191.  
  192.     return S;
  193.  
  194. }
  195.  
  196. int main()
  197. {
  198.     vector<point> P;
  199.  
  200.     P.emplace_back(0,0);
  201.     P.emplace_back(0,4);
  202.     P.emplace_back(-4,0);
  203.     P.emplace_back(5,0);
  204.     P.emplace_back(0,-6);
  205.     P.emplace_back(1,0);
  206.  
  207.     vector<point> S = CH_Graham(P);
  208.  
  209.     for(point p:S) cout << '(' << p.x << ", " << p.y << ")\n";
  210.  
  211. }
Advertisement
Add Comment
Please, Sign In to add comment