MAXimal

добавлено: 11 Jun 2008 10:23
редактировано: 11 Jun 2008 10:24

Нахождение площади простого многоугольника

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

Способ 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 (см. Ориентированная площадь треугольника). Опять же, благодаря знаку, вся лишняя площадь сократится, и останется только ответ.

Этот способ хорош тем, что его проще обобщить на более сложные случаи (например, когда некоторые стороны - не прямые, а дуги окружности).