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

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

Расположение многоугольника относительно прямой

Дан многоугольник и прямая.
Необходимо определить с какой стороны расположен многоугольник от прямой.

    Подставляем вершины многоугольника в уравнение прямой и в зависимости от полученных знаков выдаём ответ.


Листинг C++

// расположение многоугольника отосительно прямой
//        1 - находится с положительной стороны
//        - 1 - находится с отрицательной стороны
//        0 - прямая пересекает одну из сторон многоугольника (сторону а не вершину)
int polygon_for_line (vector < point > p, line l)
{
    int i, j;
    int s = - 2; // знак
    for (i = 0; i < p.size(); ++ i)
    {
        int t = point_in_line (l, p[i]); // положение вершины относительно прямой
        if (t != 0)        // если точка не принадлежить прямой
            if (s != - 2)     // если s мы вычислили
                if (t != s)        // если знаки различны, то прямая пересекает сторону многоугольника
                    return 0;
                else
                {}
            else
                s = t; // если s мы ещё не вычислили, присваиваем ему вычисленное значение
    }
    if (s == - 2) return 0;
    return s;
}


14:15
22.07.2009