1 Тема от Pasha

  • Pasha
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-25
  • Сообщений: 2

Тема: Четыре касательные к двум окружностям

Привет,
работаем в обычной прямоугольной (декартова) система координат.
на входе у нас две окружности (x1,y1,r1) и (x2,y2,r2)
на выходе 4 уравнения касательных, конечно если они есть.

Поможет кто нибудь с этой задачкой (C/C++ код) ? она уже и
не так сложная. В роде у меня как то работает, но некрасиво,
и неуниверсально. Куча разных тестов (в какой четверти какая
окружность, ...)

Спасибо, Паша

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Четыре касательные к двум окружностям

Моя реализация:

const double EPS = 1E-9;
double sqr (double x)  { return x * x; }

struct pt {
    double x, y;
};
struct circle : public pt {
    double r;
};
struct line {
    double a, b, c;
};

void tangents (pt c, double r1, double r2, vector<line> & ans) {
    double r = r2 - r1;
    double z = sqr(c.x) + sqr(c.y);
    double d = z - sqr(r);
    if (d < -EPS)  return;
    d = sqrt (abs (d));
    line l;
    l.a = (c.x * r + c.y * d) / z;
    l.b = (c.y * r - c.x * d) / z;
    l.c = r1;
    ans.push_back (l);
    l.a = (c.x * r - c.y * d) / z;
    l.b = (c.y * r + c.x * d) / z;
    l.c = r1;
    ans.push_back (l);
}

vector<line> tangents (circle a, circle b) {
    vector<line> ans;
    for (int i=-1; i<=1; i+=2)
        for (int j=-1; j<=1; j+=2)
            tangents (b-a, a.r*i, b.r*j, ans);
    for (size_t i=0; i<ans.size(); ++i)
        ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
    return ans;
}

Только прямых вернётся не 4, а 8 - там повторяющиеся будут, но лучше уж так, чем недосчитаться их wink

Сайтe-maxx

3 Ответ от Pasha

  • Pasha
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-25
  • Сообщений: 2

Re: Четыре касательные к двум окружностям

Спасибо за ответ !
Пока четко не смотрел, однако отсутствует определение розницы двух  struct "circle".

Кроме того, боюсь, что будет тоже самая проблема связана с положением центра окружности circle
в зависимости от его положения в разных четвертях.

Да, и можно пожалуйста сделать рабочий примерь кода:

circle a (x = 1.0, y = 5.0, r = 1.0)
circle b (x = 6.0, y = 7.0, r = 2.0)

4 уравнения (у меня уравнение прямой с угловым коэффициентом: y = kx + b)

k[0] =  0.19619, b[0] =  3.78475
k[1] =  0.63715, b[1] =  5.54858
k[2] =  1.46353, b[2] =  1.76393
k[3] = -0.21353, b[3] =  6.23607

и второй пример:

circle a (x =  1.0, y = 5.0, r = 1.0)
circle b (x = -6.0, y = 7.0, r = 2.0)
k[0] = -0.44190, b[0] =  2.16204
k[1] = -0.14144, b[1] =  8.17129
k[2] =  0.14749, b[2] =  9.90660
k[3] = -0.84749, b[3] = -0.70660

Спасибо, Паша

4 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Четыре касательные к двум окружностям

Ну как раз, только operator- у pt и не хватает. Но это же максимальная халява:

pt operator- (pt p) {
   pt res = { x-p.x, y-p.y };
   return res;
}

Никаких проблем с четвертями не будет, это общее геометрическое решение.

С первым примером у меня числа сходятся (хотя прямые выводятся в другом формате - в виде коэффициентов уравнения ax+by+c=0), а со вторым - нет, но там как будто где-то минус забыт: например, b[0] =  2.16204 не может быть, потому что обе окружности находятся выше 2.16204.

Сайтe-maxx