MAXimal | |
добавлено: 11 Jun 2008 10:23 Содержание [скрыть] Нахождение площади простого многоугольникаПусть дан простой многоугольник (т.е. без самопересечений, но не обязательно выпуклый), заданный координатами своих вершин в порядке обхода по или против часовой стрелки. Требуется найти его площадь. Способ 1Это легко сделать, если перебрать все рёбра и сложить площади трапеций, ограниченных каждым ребром. Площадь нужно брать с тем знаком, с каким она получится (именно благодаря знаку вся "лишняя" площадь сократится). Т.е. формула такова: S += (X2 - X1) * (Y1 + Y2) / 2 Код: double sq (const vector<point> & fig) { double res = 0; for (unsigned i=0; i<fig.size(); i++) { point p1 = i ? fig[i-1] : fig.back(), p2 = fig[i]; res += (p1.x - p2.x) * (p1.y + p2.y); } return fabs (res) / 2; } Способ 2Можно поступить другим образом. Выберем произвольно точку O, переберём все рёбра, прибавляя к ответу ориентированную площадь треугольника, образованного ребром и точкой O (см. Ориентированная площадь треугольника). Опять же, благодаря знаку, вся лишняя площадь сократится, и останется только ответ. Этот способ хорош тем, что его проще обобщить на более сложные случаи (например, когда некоторые стороны - не прямые, а дуги окружности).
|