Círculos
Um círculo é o conjunto de pontos equidistantes de um ponto C. A distância de um ponto do círculo ao seu centro C é denominada raio r do círculo.
Conforme sua definição, um círculo pode ser representado através de um ponto C e um raio r.
// Definição da classe Point
class Circle {
public:
Point C;
double r;
Circle(const Point& Cv = Point(0, 0), double rv = 1.0) : C(Cv), r(rv) {}
};
A equação do círculo pode ser deduzida a partir da expressão d(P, C) = r, onde P = (x, y) é um ponto do círculo, C = (x0, y0) é o centro do círculo e r é o raio. A equação final é dada a seguir.
Esta equação é útil para resolver vários problemas envolvendo círculos, como o problema de determinar se um ponto está dentro, fora ou sobre um círculo, como veremos a seguir.
Dado um ponto P e um círculo de centro C e raio r, uma (e apenas uma) das três afirmações abaixo será verdadeira:
- P está dentro do círculo;
- P está sobre o círculo;
- P está fora do círculo.
Para determinar qual é a relação válida, basta computar a distância entre o ponto P e o centro C do círculo: caso esta distância seja menor, igual ou maior que r, P estará dentro, sobre e fora do círculo, respectivamente.
// Definição da classe Point
class Circle {
public:
// Membros e construtores
typedef enum { IN, OUT, ON } PointPosition;
PointPosition position(const Point& P) const
{
auto d = P.distance(C);
return equals(d, r) ? ON : (d < r ? IN : OUT);
}
};Tanto o cálculo do perímetro quanto da área de um círculo envolvem o uso da constante PI. Caso o problema não informe o valor a ser utilizado, há duas maneira de proceder para determinar o valor desta constante. A primeira é utilizar o valor definido na linguagem Python, que pode ser obtido com o script abaixo.
from math import *
print piO valor resultante, 3.141592653589793, está correto nas suas 15 casas decimais.
Outra forma é utilizar a função acos da biblioteca de matemática padrão do
C/C++.
#include <cmath>
const double PI = 2.0 * acos(0.0);O valor obtido coincide com aquele fornecido pelo script Python.
O perímetro (circunferência) é o comprimento do contorno do círculo, e é igual a PI vezes o seu diâmetro, sendo o diâmetro o dobro do raio do círculo.
// Definição do valor de PI
class Circle {
public:
// Membros e construtores
double perimeter() const
{
return 2.0 * PI * r;
}
};O valor da área delimitada pelo círculo é igual a PI vezes o quadrado do raio do círculo.
// Definição do valor de PI
class Circle {
public:
// Membros e construtores
double area() const
{
return PI * r * r;
}
};Um arco de um círculo corresponde a uma seção conectada da circunferência. O comprimento do arco pode ser determinado através do ângulo central a (definido pela união dos dois pontos extremos do arco entre si e com o centro do círculo) através do produto do perímetro P e a razão entre a e 2PI (caso a esteja em radianos). A simplificação desta razão nos leva a a*r.
// Definição do valor de PI
class Circle {
public:
// Membros e construtores
// Perímetro e área
double arc(double a) const
{
return a * r;
}
};Uma corda corresponde a qualquer segmento de reta cujos pontos extremos estão sob o círculo. O diâmetro é a maior dentre todas as cordas possíveis de um círculo. Conhecidos o raio r e o ângulo central a do arco definido pela corda, o comprimento L da corda pode ser determinado através da Lei dos Cossenos (L = sqrt(2 * r * r * (1 - cos(a)) ou pela Trigonometria (L = 2 * r * sin(a/2)).
// Definição do valor de PI
class Circle {
public:
// Membros e construtores
// Perímetro e área
double chord(double a) const
{
return 2 * r * sin(a/2);
}
};Um setor de um círculo é a área delimitada por um arco. Assim como no caso do arco, a área do setor será a fração da área total correspondente ao ângulo central a do arco que delimita o setor. A simplificação desta fração nos leva a ar²/2.
// Definição do valor de PI
class Circle {
public:
// Membros e construtores
// Perímetro e área
double sector(double a) const
{
return a * r * r / 2.0;
}
};Um segmento de um círculo, associado a um ângulo central a, corresponde à área resultante da diferença entre o setor delimitado por a e do triângulo resultante do segmentos de reta que unem os extremos dos arcos ao centro do círculo e os extremos entre si (a corda). A área deste triângulo pode ser determinada pela Fórmula de Heron (semiperímetro).
class Circle {
public:
// Membros e construtores
// Setor e corda
double segment(double a) const
{
auto c = chord(a);
auto s = (r + r + c)/2.0; // Semiperímetro
auto T = sqrt(s*(s - r)*(s - r)*(s - c)); // Área do triângulo
return sector(a) - T;
}
};Considerando que T é um triângulo com base igual a corda e altura igual a rcos(a/2), chegamos a expressão fechada para o segmento: ar²(a - sen a)/2.
class Circle {
public:
// Membros e construtores
// Setor e corda
double segment(double a) const
{
return r*r*(a - sin(a))/2.0;
}
};É possível identificar o(s) círculo(s) que interceptam um conjunto de N pontos dados.
No caso de N = 1, existem infinitos círculos (com infinitos raios possíveis) que passam por um ponto. O caso N = 2 se torna mais interessante se o raio r também for dado de antemão. Dados dois pontos P e Q e o um raio r, os cenários possíveis são:
- P = Q: esta situação é idêntica ao caso N = 1;
- dist(P, Q) = 2r: se a distância entre os dois pontos dados é igual ao diâmetro do círculo, existe um único círculo de raio r que passa por P e Q. O centro deste círculo será o ponto médio do segmento PQ;
- dist(P, Q) > 2r: neste caso, nenhum círculo de r pode passar por ambos pontos simultaneamente
- dist(P, Q) < 2r: neste caso, exatamente dois círculos passam por P e Q com raio r. O código abaixo, adaptado do livro Competitive Programming 3, permite identificar um destes círculos. O outro pode ser encontrado invertendo os parâmetros (passar Q como primeiro e P como segundo parâmetro).
// Definição da class Point
class Circle {
public:
// Membros e construtores
static bool
from2PointsAndRadius(const Point& P, const Point& Q, double r, Circle& c)
{
double d2 = (P.x - Q.x) * (P.x - Q.x) + (P.y - Q.y) * (P.y - Q.y);
double det = r * r / d2 - 0.25;
if (det < 0.0)
return false;
double h = sqrt(det);
auto x = (P.x + Q.x) * 0.5 + (P.y - Q.y) * h;
auto y = (P.y + Q.y) * 0.5 + (Q.x - P.x) * h;
c = Circle(Point(x, y), r);
return true;
}
}O método retorna falso se a distância entre os pontos é menor que o diâmetro. Nos demais casos, o círculo c, passado por referência, contém o centro e o raio de um círculo que intercepta ambos P e Q.
Para o caso N = 3 há uma interessante relação: se os pontos P, Q, R não são colineares, a equação do círculo que passa por estes três pontos pode ser expressa pelo determinante abaixo.
Este determinante também pode ser utilizado para determinar se 4 pontos são cocirculares, substituindo as coordenadas do quarto ponto nas variáveis da primeira linha.
Contudo, a implementação desta determinante não é trivial, uma vez que é preciso recorrer a cofatores, e o resultado final não fica na forma canônica, de onde são extraídas as informações sobre o raio e o centro.
Uma outra abordagem é observar que a distância entre os três pontos e o centro do círculo são iguais e, das relações d(P, C) = d(Q, C), d(P, C) = d(R, C), encontrar um sistema linear em relação as coordenadas do centro. Determinado o centro, o raio será a distância entre qualquer um dos pontos e o centro.
// Definição da classe Point e Circle
Circle circle_from_3_points(const Point& P, const Point& Q, const Point& R)
{
auto a = 2*(Q.x - P.x);
auto b = 2*(Q.y - P.y);
auto c = 2*(R.x - P.x);
auto d = 2*(R.y - P.y);
auto det = a*d - b*c;
// Pontos colineares
if (equals(det, 0))
return Circle();
auto k1 = (Q.x*Q.x + Q.y*Q.y) - (P.x*P.x + P.y*P.y);
auto k2 = (R.x*R.x + R.y*R.y) - (P.x*P.x + P.y*P.y);
auto cx = (k1*d - k2*b)/det;
auto cy = (a*k2 - c*k1)/det;
Point C(cx, cy);
auto r = C.distance(P);
return Circle(C, r);
}Dados dois círculos com centros C1, C2 e raios r1, r2, existem cinco cenários possíveis para suas interseções. Seja d a distância entre os pontos C1 e C2. Então
- se d > r1 + r2, então os círculos não se interceptam;
- se d < |r1 - r2|, então também não há interseção, pois um dos círculos (o de menor raio) está contido no outro (o de maior raio);
- se d == 0 e r1 == r2, então os círculos são idênticos: há infinitos pontos de interseção;
- se d == r1 + r2, os círculos se interceptam em um único ponto;
- nos demais casos, há dois pontos na interseção entre os círculos.
Se C1 = (x1, y1) e C2 = (x2, y2), então as coordenadas dos pontos de interseção P1 e P2 são dadas pelas expressões abaixo.
// Definição das classes Point e Circle
#define INF -1
using pp = pair<Point, Point>;
using ipp = pair<int, pp>;
ipp intersection(const Circle& c1, const Circle& c2)
{
double d = c1.C.distance(c2.C);
if (d > c1.r + c2.r or d < fabs(c1.r - c2.r))
return ipp(0, pp(Point(), Point()));
if (equals(d, 0) and equals(c1.r, c2.r))
return ipp(INF, pp(Point(), Point()));
auto a = (c1.r * c1.r - c2.r * c2.r + d * d)/(2 * d);
auto h = sqrt(c1.r * c1.r - a * a);
auto x = c1.C.x + (a/d)*(c2.C.x - c1.C.x);
auto y = c1.C.y + (a/d)*(c2.C.y - c1.C.y);
auto P = Point(x, y);
x = P.x + (h/d)*(c2.C.y - c1.C.y);
y = P.y - (h/d)*(c2.C.x - c1.C.x);
auto P1 = Point(x, y);
x = P.x - (h/d)*(c2.C.y - c1.C.y);
y = P.y + (h/d)*(c2.C.x - c1.C.x);
auto P2 = Point(x, y);
return ipp(equals(d, c1.r + c2.r) ? 1 : 2, pp(P1, P2));
}Uma reta que passa pelos pontos P1 e P2 pode ser representada, na forma paramétrica, pela expressão vetorial P = P1 + u(P2 - P1), onde u é uma variável real. Assim, a coordenada x de P é dada por x = x1 + u(x2 - x1); de forma semelhante, a coordenada y de P é dada por y = y1 + u(y2 - y1).
Se estas coordenadas forem levadas para a equação do círculo de centro C e raio r (isto é, (x - Cx)² + (y - Cy)² = r²), obtemos o polinômio quadrático au² + bu + c = 0, onde
O discriminante D (delta) desta equação caracteriza as possíveis interseções:
- se D < 0, não há interseção entre o círculo e a reta;
- se D == 0, há um único ponto de interseção (a reta é tangente ao círculo);
- se D > 0, há dois pontos distintos de interseção.
// Definição das classes Point e Circle
// Interseção entre o círculo c e a reta que passa por P e Q
ipp intersection(const Circle& c, const Point& P, const Point& Q)
{
auto a = pow(Q.x - P.x, 2.0) + pow(Q.y - P.y, 2.0);
auto b = 2*((Q.x - P.x) * (P.x - c.C.x) + (Q.y - P.y) * (P.y - c.C.y));
auto d = pow(c.C.x, 2.0) + pow(c.C.y, 2.0) + pow(P.x, 2.0) + pow(P.y, 2.0)
+ 2*(c.C.x * P.x + c.C.y * P.y);
auto D = b * b - 4 * a * d;
if (D < 0)
return ipp(0, pp(Point(), Point()));
else if (equals(D, 0))
{
auto u = -b/(2*a);
auto x = P.x + u*(Q.x - P.x);
auto y = P.y + u*(Q.y - P.y);
return ipp(1, pp(Point(x, y), Point()));
}
auto u = (-b + sqrt(D))/(2*a);
auto x = P.x + u*(Q.x - P.x);
auto y = P.y + u*(Q.y - P.y);
auto P1 = Point(x, y);
u = (-b - sqrt(D))/(2*a);
x = P.x + u*(Q.x - P.x);
y = P.y + u*(Q.y - P.y);
auto P2 = Point(x, y);
return ipp(2, pp(P1, P2));
}- Codeforces
- UVA
HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.
BOURKE, Paul. Intersection of two circles. Acesso em 06/08/2016.
QC.EDU.HK. Equation of circle passing through 3 givem points. Acesso em 18/08/2016.
Stack Exchange. Mathematics: Get the equation of a circle when given 3 points. Acesso em 18/08/2016.