Разрезание выпуклого многоугольника в отношении площадей частей m:n

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

    Есть много путей решения. В этом и заключается особенность геометрических задач. Рассмотрим здесь решение, основанное на следующей теореме:
Проведём в треугольнике отрезок соединяющий одну из вершин с противоположной стороной. Пусть этот отрезок разобьёт треугольник на две части с отношением площадей m:n, тогда отрезки, являющиеся основаниями полученных частей и образующие основание всего треугольника, так же относятся как m к n.
    Как мы можем этим воспользоваться? Перед нами выпуклый многоугольник, значит мы можем его разделить на треугольники, проведя из первой вершины диагонали к остальным вершинам. Вычислим, чему должны быть равны площади искомых подмногоугольников. Будем теперь складывать площади наших треугольников по порядку (допусти по часовой стрелке) пока сумма меньше, чем площадь первой части. В итоге мы остановимся на одном из треугольников, который нужно будет разделить в некотором отношении, чтобы в итоге весь многоугольник распался на два искомых многоугольника.

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

Листинг C++

point part_convex (vector < point > v, double m, double n)
{
    double area = abs (area_polygon (v)) / (m + n) * m;
    double a = 0;
    int i;
    for (i = 1; i < v.size () - 1; ++ i)
    {
        double s = abs (area_triangle (v[0], v[i], v[i + 1]));
        if (a + s <= area)
            a += s;
        else break;
    }
    if (abs (a - area) <= eps) return v[i];
    return part_segment (v[i], v[i + 1], area - a,
                        abs (area_triangle (v[0], v[i], v[i + 1]) - area + a));
}

14:40
22.07.2009

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