Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм вычисления площади многоугольника

Автор: Ground 23.3.2009, 10:47

Всем снова привет  Данная тема напрямую связана с http://forum.vingrad.ru/forum/s/402de66db3dbf41a675b6c7971d832c6/topic-252010.html. У нас есть фигура. Сверху ломаная (красная), снизу прямая (синяя). Необходимо вычислить площадь этой фигуры. Точек у ломанной может быть до 10к. Координаты по Х образуют ряд: x0 < x1 < x2 < ... < xn. Попробовал вот такой http://opita.net/node/27, но он, увы, не дает верного результата. Еще и количество точек лимитировано - всего 100. Также пробовал способ, делить на прямоугольные треугольнички и прямоугольники между точками i, i+1, но слишком много описывать в коде. Возможно есть какие либо еще способы вычисления площади?

Автор: Akina 23.3.2009, 11:12

Делишь вертикально на куски, каждый - на 2 прямоугольных треугольника и прямоугольник. Считаешь.

Автор: maxdiver 23.3.2009, 13:11

Так есть же очень простая формула для вычисления площади произвольного многоугольника, в которой к тому же всё будет в целых числах: S = ABS( СУММА по i=1..N   (X[i]-X[i+1]) * (Y[i]+Y[i+1]) )  /  2 Добавлено через 8 минут и 55 секунд Она очень легко получается: возьмём каждый отрезок (P[i], P[i+1]), каждый такой отрезок (вместе с осью ox) ограничивает трапецию ((X[i],Y[i]), (X[i+1],Y[i+1]), (X[i+1],0), (X[i],0)). Заметим, что если мы просуммируем площади всех таких трапеций, беря со знаком минус те из них, в которых X[i+1]<X[i], то в результате вся "лишняя" площадь сократится, и останется только площадь многоугольника, или она со знаком минус (зависит от направления обхода). А знаковую площадь такой трапеции легко получить: это полусумма оснований (Y[i] и Y[i+1]) на высоту с нужным знаком (а это как раз в точности X[i+1]-X[i]). Итак, просуммировав площади таких трапеций, и взяв модуль, мы получим площадь многоугольника.

Автор: Ground 23.3.2009, 13:23

Цитата(maxdiver @  23.3.2009,  20:11 ) S = ABS( СУММА по i=1..N   (X[i]-X[i+1]) * (Y[i]+Y[i+1]) )  /  2 Эта формула справедлива для любого количества вершин многоугольника? Вот http://opita.net/node/27 указано, что эта формула используется только для многоугольников до 100 вершин (хотя они и формулу неверно вывели).

Автор: maxdiver 23.3.2009, 13:48

Цитата Эта формула справедлива для любого количества вершин многоугольника? Да хоть миллион  Ну разве что инты переполнятся

Автор: Ground 23.3.2009, 13:55

Ну тогда вопрос закрываю, всем спасибо за помощь! maxdiver, держи плюсик!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)