Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Пересечение прямой с окружностью

Дано прямая и окружность
Найти точки пересечения окружности и прямой
Идея заключается в повороте окружности и прямой, чтоб прямая совпала с осью абцисс.
Находим точки пересечения окружности и оси абцисс, а потом поворачиваем их обратно.

Листинг C++

int cross_line_circle (line l, circle c, point &p1, point &p2)
{
    // проекция центра окружности на прямую
    point p = closest_point (l, c.c);
    // сколько всего решений?
    int flag = 0;
    double d = dist (c.c, p);
    if (abs (d - c.r) <= eps) flag = 1;
    else
        if (c.r > d) flag = 2;
        else return 0;

    // находим расстояние от проекции до точек пересечения
    double k = sqrt (c.r * c.r - d * d);
    double t = dist (point (0, 0), point (l.b, - l.a));
    // добавляем к проекции векторы направленные к точкам пеерсечения
    p1 = add_vector (p, point (0, 0), point (- l.b, l.a), k / t);
    p2 = add_vector (p, point (0, 0), point (l.b, - l.a), k / t);

    return flag;
}

27.06.2007, 13:59