Луч, не пересекающий ни одну из заданных окружностей

Дана точка и множество окружностей.
Необходимо найти точку, лежащую на луче (не равную исходной точке), такую, чтобы луч, выходящий из исходной точки и проходящий через заданную точку, не пересекал ни одну из заданных окружностей.

    Такого луча не может быть в том и только в том случае, когда окружности образуют "забор для света" вокруг данной точки. Чтобы проверить так это или нет, упорядочим окружности вокруг исходной точки по полярному углу. После этого будем строить касательные от исходной точки к окружностям, если сдвинуть касательные на очень маленький градус вбок от окружности, то получатся два луча, не пересекающие эту окружность. Если такой луч не пересекает больше никакие окружности, то этот луч является искомым в нашей задаче.
    Для проверки пересекает луч какую-либо окружность или нет, необходимо проверить его пересечение с соседними окружностями той, от которой мы его построили. Замечу, что нас интересуют не просто соседние окружности по полярному углу, а те, которые к тому же не лежат внутри нашей окружности.

Асимптотика O (NlogN).

Листинг C++

class less_of_polar_angle
{
public :
    bool operator () (circle c1, circle c2)
    {
        return c1.alpha < c2.alpha;
    }
};
bool ray_nocross_for_circset (point p, vector < circle > v, point &t)
{
    int n = v.size();
    int i, j, k;

    // для каждой окружности находим её полярный угол
    for (i = 0; i < n; ++ i)
        v[i].alpha = polar_angle (point (v[i].c.x - p.x, v[i].c.y - p.y));

    // сортируем все окружности по полярному углу одной из точек
    sort (v.begin (), v.end (), less_of_polar_angle ());

    // находим окружность с максимальным радиусом
    k = 0;
    for (i = 1; i < n; ++ i)
        if (v[i].r > v[k].r)
            k = i;

    // рассматриваем все окружности по очереди, начиная с k
    i = k; // текущая окружность
    do
    {
        point p1, p2;
        int flag = contact_points (p, v[i], p1, p2);
        double alpha = polar_angle (point (p1.x - p.x, p1.y - p.y));
        double betta = polar_angle (point (p2.x - p.x, p2.y - p.y));

        // находим левую точку касания - t
        if (abs (alpha - betta) >= pi)
            if (alpha < betta)
                t = p1;
            else
                t = p2;
        else
            if (alpha < betta)
                t = p2;
            else
                t = p1;

        // отодвигаем её на 0.001 по перпендикуляру влево
        double d = 0.001 / dist (v[i].c, t);
        t = add_vector (t, v[i].c, t, d);

        // ищем первую окружность, которая пересекает луч (p, t)
        bool flag_cross = false;
        j = (i + 1) % n;
        do
        {
            if (cross_ray_circle (p, t, v[j], p1, p2) != 0)
            {
                flag_cross = true;
                i = j;
                break;
            }
            j = (j + 1) % n;
        }
        while (j != k);

        // если все окружности не пересекают этот луч
        if (flag_cross == false)    return true;
    }
    while (i != k);

    return false;
}

15:36
20.07.2009

По всем вопросам обращаться: rumterg@gmail.com