Разрезание выпуклого многоугольника прямой

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

    Найдём точки пересечения прямой с многоугольником. Добавим их в список вершин. Теперь нужныо всего лишь разделить многоугольник на две части вдоль, лежащие с разных сторон от диагонали.

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

Листинг C++

// разрезание выпуклого многоугольника по прямой
//        функция возвращает два многоугольника
//        первый многоугольник лежит с положительной стороны от прямой
//        второй - с отрицательной
void cut_convex_for_line (vector < point > p, line l, vector < point > &v1,
           vector < point > &v2, point &p1, point &p2)
{
    int n = p.size();
    int i, j;

    // находим точки пересечение прямой с многоугольником и вставляем их в многоугольник
    int c = 0; // счётчик пересечений многоугольника с прямой
    list < point > s (p.begin(), p.end()); // представляем многоугольник как список вершин
    list < point > :: iterator it, jt; // итераторы обходы
    list < point > :: iterator i1, i2; // итераторы вставленных точек

    for (it = s.begin(); it != s.end(); ++ it)
    {
        jt = it;
        ++ jt;
        if (jt == s.end()) jt = s.begin();

        // пересекаем прямую со стороной
        point t;
        int flag = cross_segment_line (*it, *jt, l, t);
        // если прямая проходит по стороне
        if (flag == 2)
        {
            if (polygon_for_line (p, l) > 0)    v1 = p;
            else    v2 = p;
            return;
        }
        // если прямая и сторона не пересекаются
        if (flag == 0) continue;

        // если прямая проходит через вершину многоугольника
        if (abs (t.x - (*it).x) <= eps && abs (t.y - (*it).y) <= eps)
        {
            if (c == 0) i1 = it;
            else i2 = it;
            ++ c;
            continue;
        }
        if (abs (t.x - (*jt).x) <= eps && abs (t.y - (*jt).y) <= eps) continue;

        // иначе прямая пересекает сторону, вставляем точку пересечения в многоугольник
        ++ it;
        it = s.insert (it, t);

        // увеличиваем счётчик пересечений многоугольника с прямой
        if (c == 0) i1 = it;
        else i2 = it;
        ++ c;
    }

    // если прямая не пересекает многоугольник
    if (c != 2)
    {
        if (polygon_for_line (p, l) > 0)    v1 = p;
        else    v2 = p;
        return;
    }

    // представляем многоугольник массивом точек
    n = s.size ();
    vector < point > all (s.begin(), s.end());
    int j1, j2;
    for (it = s.begin(), i = 0; it != s.end(); ++ i, ++ it)
    {
        if (it == i1) j1 = i;
        if (it == i2) j2 = i;
    }

    // режем многоугольник
    p1 = all[j1];
    p2 = all[j2];
    cut_polygon_for_edge (all, j1, j2, v1, v2);

    // если многоугольники имеют не то расположение которое нам требуется - меняем их местами
    if (polygon_for_line (v1, l) < 0)
        swap (v1, v2);
}

12:49
22.07.2009

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