Разрезание выпуклого многоугольника в отношении площадей частей 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