Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef POINTS_VECTOR_LINES_H
- #define POINTS_VECTOR_LINES_H
- #include <cmath>
- using namespace std;
- //altere precisao das constantes, caso necessario
- const double EPS = 1e-9;
- const double PI = atan(1)*4;
- /**************************/
- /* Ponto: (x, y) \in R */
- /**************************/
- struct point
- {
- double x, y;
- //inicializa com (x, y) = (0,0)
- point():x(0),y(0){}
- //inicializa com (x, y) = (_x,_y)
- point(const double &_x, const double &_y):x(_x),y(_y){}
- //para o caso de uma ordenacao crescente em x e depois em y (caso empate em x)
- bool operator < (const point &other) const
- {
- if(abs(x - other.x) > EPS) return x < other.x;
- else return y < other.y;
- }
- //para testar igualdade com precisao EPS
- bool operator == (const point &other) const
- {
- return abs(x - other.x) < EPS && abs(y - other.y) < EPS;
- }
- };
- //distancia euclidiana ao quadrado
- double dist2(const point &p1, const point &p2)
- {
- double dx = p1.x - p2.x, dy = p1.y - p2.y;
- return dx*dx + dy*dy;
- }
- //distancia euclidiana
- double dist(const point &p1, const point &p2)
- {
- //vejam hypot em http://www.cplusplus.com/reference/cmath/hypot/
- return hypot(p1.x - p2.x, p1.y - p2.y);
- }
- //converte grau para radiano
- double deg2rad(double theta)
- {
- return theta*(PI/180.0);
- }
- //rotaciona um ponto em sentido anti-horario em relacao a (0,0) por um angulo theta
- point rotate_ccw(const point &p, const double theta)
- {
- double rad = deg2rad(theta);
- return point(p.x*cos(rad) - p.y*sin(rad), p.x*sin(rad) + p.y*cos(rad));
- }
- /**************************/
- /* Linha: ax + by + c = 0 */
- /**************************/
- struct line
- {
- double a, b, c;
- };
- //dados 2 pontos, constroi-se uma linha
- line points2line(const point &p1, const point &p2)
- {
- line l;
- //linha vertical?
- if(abs(p1.x - p2.x) < EPS)
- {
- l.a = 1.0; l.b = 0.0; l.c = -p1.x;
- }
- else
- {
- l.a = -(p1.y - p2.y)/(p1.x - p2.x);
- l.b = 1.0; //fixa b em 1
- l.c = -(l.a*p1.x) - p1.y;
- }
- return l;
- }
- //verifica se duas linhas sao paralelas
- bool are_parallel_lines(const line &l1, const line &l2)
- {
- return (abs(l1.a - l2.a) < EPS) && (abs(l1.b - l2.b) < EPS);
- }
- //verifica se duas linhas sao iguais
- bool are_same_lines(const line &l1, const line &l2)
- {
- return are_parallel_lines(l1, l2) && (abs(l1.c - l2.c) < EPS);
- }
- //calcula o ponto de intersecao de duas linhas, caso nao sao paralelas
- //retorna verdadeiro, caso a intersecao exista (solucao do sistema linear l1 e l2)
- bool line_intersection(const line &l1, const line &l2, point &p)
- {
- if(are_parallel_lines(l1, l2)) return false;
- //soluciona sistema linear de 2 equacoes e 2 variaveis
- p.x = (l2.b*l1.c - l1.b*l2.c)/(l2.a*l1.b - l1.a*l2.b);
- //testa por linha vertical e evita divisao por 0
- if(abs(l1.b) > EPS)
- p.y = -(l1.a*p.x + l1.c);
- else
- p.y = -(l2.a*p.x + l2.c);
- return true;
- }
- /****************************/
- /* Vetor: v = p1 - p2 */
- /* Possui direcao e sentido */
- /****************************/
- struct dvector
- {
- double x, y;
- dvector(double _x, double _y):x(_x),y(_y) {}
- };
- //2 pontos para vetor
- dvector points2dvector(const point &p1, const point &p2)
- {
- return dvector(p2.x-p1.x, p2.y-p1.y);
- }
- //aplica escala no vetor
- dvector scale_dvector(const dvector &v, double s)
- {
- return dvector(v.x*s, v.y*s);
- }
- //translada ponto por um vetor
- point translate_point(const point &p, const dvector &v)
- {
- return point(p.x+v.x, p.y+v.y);
- }
- //produto interno (escalar)
- double dot_product(const dvector &u, const dvector &v)
- {
- return u.x*v.x + u.y*v.y;
- }
- //norma Euclidiana do vetor ao quadrado
- double norm2(const dvector &v)
- {
- return v.x*v.x + v.y*v.y;
- }
- //distancia do ponto p ate a linha definida pelos pontos a e b (a != b)
- //o ponto de intersecao e saira em referencia c
- double dist2line(const point &p, const point &a, const point &b, point &c)
- {
- dvector ap = points2dvector(a, p), ab = points2dvector(a, b);
- double u = dot_product(ap, ab)/norm2(ab);
- c = translate_point(a, scale_dvector(ab, u));
- return dist(p, c);
- }
- //distancia do ponto p ate o segmento definido pelos pontos a e b (a != b)
- //o ponto de intersecao e saira em referencia c
- double dist2segment(const point &p, const point &a, const point &b, point &c)
- {
- dvector ap = points2dvector(a, p), ab = points2dvector(a, b);
- double u = dot_product(ap, ab)/norm2(ab);
- if(u < 0.0)
- {
- c = point(a.x, a.y);
- return dist(p, a);
- }
- else if(u > 1.0)
- {
- c = point(b.x, b.y);
- return dist(p, b);
- }
- else
- return dist2line(p, a, b, c);
- }
- //angulo formado pelos pontos aob
- double angle3points(const point &a, const point &o, const point &b)
- {
- dvector oa = points2dvector(o, a), ob = points2dvector(o, b);
- return acos(dot_product(oa, ob)/sqrt(norm2(oa)*norm2(ob)));
- }
- //produto vetorial de 2 vetores 2d
- double vecprod(const dvector &u, const dvector &v)
- {
- return u.x*v.y - u.y*v.x;
- }
- //testa se o ponto r esta na esquerda (anti-horario) da linha definida por p e q
- bool is_ccw(const point &p, const point &q, const point &r)
- {
- return vecprod(points2dvector(p, q), points2dvector(p, r)) > 0.0;
- }
- //testa se o ponto r e colinear com os pontos p e q
- bool is_collinear(const point &p, const point &q, const point &r)
- {
- return abs(vecprod(points2dvector(p, q), points2dvector(p, r))) < EPS;
- }
- #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement