Advertisement
andrercruz

Untitled

Nov 17th, 2017
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.56 KB | None | 0 0
  1. #ifndef POINTS_VECTOR_LINES_H
  2. #define POINTS_VECTOR_LINES_H
  3.  
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. //altere precisao das constantes, caso necessario
  9. const double EPS = 1e-9;
  10. const double PI = atan(1)*4;
  11.  
  12. /**************************/
  13. /* Ponto: (x, y) \in R */
  14. /**************************/
  15.  
  16. struct point
  17. {
  18.     double x, y;
  19.  
  20.     //inicializa com (x, y) = (0,0)
  21.     point():x(0),y(0){}
  22.  
  23.     //inicializa com (x, y) = (_x,_y)
  24.     point(const double &_x, const double &_y):x(_x),y(_y){}
  25.  
  26.     //para o caso de uma ordenacao crescente em x e depois em y (caso empate em x)
  27.     bool operator < (const point &other) const
  28.     {
  29.         if(abs(x - other.x) > EPS) return x < other.x;
  30.         else return y < other.y;
  31.     }
  32.  
  33.     //para testar igualdade com precisao EPS
  34.     bool operator == (const point &other) const
  35.     {
  36.         return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
  37.     }
  38. };
  39.  
  40. //distancia euclidiana ao quadrado
  41. double dist2(const point &p1, const point &p2)
  42. {
  43.     double dx = p1.x - p2.x, dy = p1.y - p2.y;
  44.     return dx*dx + dy*dy;
  45. }
  46.  
  47. //distancia euclidiana
  48. double dist(const point &p1, const point &p2)
  49. {
  50.     //vejam hypot em http://www.cplusplus.com/reference/cmath/hypot/
  51.     return hypot(p1.x - p2.x, p1.y - p2.y);
  52. }
  53.  
  54. //converte grau para radiano
  55. double deg2rad(double theta)
  56. {
  57.     return theta*(PI/180.0);
  58. }
  59.  
  60. //rotaciona um ponto em sentido anti-horario em relacao a (0,0) por um angulo theta
  61. point rotate_ccw(const point &p, const double theta)
  62. {
  63.     double rad = deg2rad(theta);
  64.     return point(p.x*cos(rad) - p.y*sin(rad), p.x*sin(rad) + p.y*cos(rad));
  65. }
  66.  
  67. /**************************/
  68. /* Linha: ax + by + c = 0 */
  69. /**************************/
  70.  
  71. struct line
  72. {
  73.     double a, b, c;
  74. };
  75.  
  76. //dados 2 pontos, constroi-se uma linha
  77. line points2line(const point &p1, const point &p2)
  78. {
  79.     line l;
  80.  
  81.     //linha vertical?
  82.     if(abs(p1.x - p2.x) < EPS)
  83.     {
  84.         l.a = 1.0; l.b = 0.0; l.c = -p1.x;
  85.     }
  86.     else
  87.     {
  88.         l.a = -(p1.y - p2.y)/(p1.x - p2.x);
  89.         l.b = 1.0; //fixa b em 1
  90.         l.c = -(l.a*p1.x) - p1.y;
  91.     }
  92.  
  93.     return l;
  94. }
  95.  
  96. //verifica se duas linhas sao paralelas
  97. bool are_parallel_lines(const line &l1, const line &l2)
  98. {
  99.     return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS);
  100. }
  101.  
  102. //verifica se duas linhas sao iguais
  103. bool are_same_lines(const line &l1, const line &l2)
  104. {
  105.     return are_parallel_lines(l1, l2) && (abs(l1.c - l2.c) < EPS);
  106. }
  107.  
  108. //calcula o ponto de intersecao de duas linhas, caso nao sao paralelas
  109. //retorna verdadeiro, caso a intersecao exista (solucao do sistema linear l1 e l2)
  110. bool line_intersection(const line &l1, const line &l2, point &p)
  111. {
  112.     if(are_parallel_lines(l1, l2)) return false;
  113.  
  114.     //soluciona sistema linear de 2 equacoes e 2 variaveis
  115.     p.x = (l2.b*l1.c - l1.b*l2.c)/(l2.a*l1.b - l1.a*l2.b);
  116.  
  117.     //testa por linha vertical e evita divisao por 0
  118.     if(abs(l1.b) > EPS)
  119.         p.y = -(l1.a*p.x + l1.c);
  120.     else
  121.         p.y = -(l2.a*p.x + l2.c);
  122.  
  123.     return true;
  124. }
  125.  
  126. /****************************/
  127. /* Vetor: v = p1 - p2       */
  128. /* Possui direcao e sentido */
  129. /****************************/
  130.  
  131. struct dvector
  132. {
  133.     double x, y;
  134.  
  135.     dvector(double _x, double _y):x(_x),y(_y) {}
  136. };
  137.  
  138. //2 pontos para vetor
  139. dvector points2dvector(const point &p1, const point &p2)
  140. {
  141.     return dvector(p2.x-p1.x, p2.y-p1.y);
  142. }
  143.  
  144. //aplica escala no vetor
  145. dvector scale_dvector(const dvector &v, double s)
  146. {
  147.     return dvector(v.x*s, v.y*s);
  148. }
  149.  
  150. //translada ponto por um vetor
  151. point translate_point(const point &p, const dvector &v)
  152. {
  153.     return point(p.x+v.x, p.y+v.y);
  154. }
  155.  
  156. //produto interno (escalar)
  157. double dot_product(const dvector &u, const dvector &v)
  158. {
  159.     return u.x*v.x + u.y*v.y;
  160. }
  161.  
  162. //norma Euclidiana do vetor ao quadrado
  163. double norm2(const dvector &v)
  164. {
  165.     return v.x*v.x + v.y*v.y;
  166. }
  167.  
  168. //distancia do ponto p ate a linha definida pelos pontos a e b (a != b)
  169. //o ponto de intersecao e saira em referencia c
  170. double dist2line(const point &p, const point &a, const point &b, point &c)
  171. {
  172.     dvector ap = points2dvector(a, p), ab = points2dvector(a, b);
  173.     double u = dot_product(ap, ab)/norm2(ab);
  174.     c = translate_point(a, scale_dvector(ab, u));
  175.     return dist(p, c);
  176. }
  177.  
  178. //distancia do ponto p ate o segmento definido pelos pontos a e b (a != b)
  179. //o ponto de intersecao e saira em referencia c
  180. double dist2segment(const point &p, const point &a, const point &b, point &c)
  181. {
  182.     dvector ap = points2dvector(a, p), ab = points2dvector(a, b);
  183.     double u = dot_product(ap, ab)/norm2(ab);
  184.  
  185.     if(u < 0.0)
  186.     {
  187.         c = point(a.x, a.y);
  188.         return dist(p, a);
  189.     }
  190.     else if(u > 1.0)
  191.     {
  192.         c = point(b.x, b.y);
  193.         return dist(p, b);
  194.     }
  195.     else
  196.         return dist2line(p, a, b, c);
  197. }
  198.  
  199. //angulo formado pelos pontos aob
  200. double angle3points(const point &a, const point &o, const point &b)
  201. {
  202.     dvector oa = points2dvector(o, a), ob = points2dvector(o, b);
  203.     return acos(dot_product(oa, ob)/sqrt(norm2(oa)*norm2(ob)));
  204. }
  205.  
  206. //produto vetorial de 2 vetores 2d
  207. double vecprod(const dvector &u, const dvector &v)
  208. {
  209.     return u.x*v.y - u.y*v.x;
  210. }
  211.  
  212. //testa se o ponto r esta na esquerda (anti-horario) da linha definida por p e q
  213. bool is_ccw(const point &p, const point &q, const point &r)
  214. {
  215.     return vecprod(points2dvector(p, q), points2dvector(p, r)) > 0.0;
  216. }
  217.  
  218. //testa se o ponto r e colinear com os pontos p e q
  219. bool is_collinear(const point &p, const point &q, const point &r)
  220. {
  221.     return abs(vecprod(points2dvector(p, q), points2dvector(p, r))) < EPS;
  222. }
  223.  
  224. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement