Как найти площадь многоугольника по координатам вершин
Перейти к содержимому

Как найти площадь многоугольника по координатам вершин

  • автор:

Площадь многоугольника

Рассмотрим два самых популярных способа — метод трапеций и суммирование ориентированных площадей треугольников.

Метод трапеций

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

Опустим из каждой вершины перпендикуляр на ось OX. Если рассмотреть сторону (например, $AB$), то ей можно сопоставить прямоугольную трапецию, у которой одна боковая сторона лежит на оси OX, а другая совпадает со стороной многоугольника. Например, для стороны AB будет трапеция $ABHG$.

Двигаясь в порядке обхода по сторонам многоугольника, будем суммировать площади таких трапеций.

Как проводить суммирование: пусть $x[i]$ и $y[i]$ — координаты точки $i$. Прибавляться будет величина $$ \Delta S = \dfrac<(x[i + 1] - x[i]) \cdot (y[i] + y[i + 1])> $$ При движении от точки A по верхней огибающей вправо у нас будет появляться изюбток площади, потому что координаты по $x$ увеличивались (допускаем, что весь многоугольник лежит в верхней полуплоскости). То есть мы будем прибавлять лишнюю площадь под фигурой. Этот избыток будет компенсирован при движении по нижней огибающей от точки $D$ влево. При этом движении $\Delta S < 0$, в чем легко убедиться.

Если смотреть на пример, то площади трапеций $DLJE$, $EJIF$ и $IFAG$ будут идти со знаком > и > лишнюю площадь, добавленную до этого.

Надо не забыть обработать последнее ребро, соединяющее первуюю и последнюю точки. Также в зависимости от порядка обхода и расположения многоугольника площадь может иметь разный знак, поэтому надо брать в конце модуль.

Очевидно, что для вычисления площади достаточно одного прохода по всем точкам, поэтому время работы составит $O(n)$, где $n$ — число вершин в многоугольнике.

Метод треугольников

В целом этот способ похож на предыдущий. Тут нам понадобится знание о векторном произведении векторов и ориентированной площади треугольника. Будем считать, что читателю это уже известно.

Рассмотрим самую левую, а если таких несколько, то самую нижнюю среди таких, точку многоугольника. На рисунке 2 это точка $A$. Теперь в порядке обхода от точки $A$ будем суммировать ориентированные площади треугольников, у которых одна вершина общая — точка $A$, а две другие — вершины $i$ и $i+1$ многоугольника. Прибавлять к общей площади будем: $$ \Delta S = \dfrac<\left[ OP_, OP_ \right]> $$ под квадратными скобками подразумеавем векторное произведение первого вектора на второй.

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

Распишем, какие площади будут суммироваться на примере:

$$ S = \Delta ABC + \Delta ACD — \Delta ADE + \Delta AEF $$ Когда мы прибавили площадь $ACD$, то была прибавлена лишняя площадь, но так как поворот от $AD$ к $AE$ идет в противоположную сторону (по часовой стрелке), то эта площадь вычтется. Но вычтется и немного лишнего — часть треугольника $AEF$, эту его часть уже прибавили на этапе $ACD$, в итоге выши в ноль. Последним шагом прибалвяем весь треугольник $AEF$.

Надо понимать, что на деле (в коде) у нас будет только прибавление площадей, но площади ориентированные, вычитание будет делаться «само по себе».

Несложно заметить, что этот алгоритм тоже линейный. В результате мы опять, возможно, должны будем взять модуль от полученной площади, так как знак зависит от порядка обхода.

Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko

Площадь простого многоульника

Формула площади Гаусса (формула землемера или формула шнурования или алгоритм шнурования) — формула определения площади простого многоугольника, вершины которого заданы декартовыми координатами на плоскости. Пользователь перемножает соответствующие координаты и складывает, чтобы найти область, охватывающую многоугольник, и вычитает его из окружающего многоугольника, чтобы найти площадь многоугольника внутри. Это называется формулой шнурков, так как положительные и отрицательные слагаемые из перемножаемых координат располагаются на бумаге крест-накрест, как при завязке шнурков. Она находит применение в геодезии и лесном хозяйстве, среди других областей.

Формула была описана Мейстером (1724—1788) в 1769 году и Гауссом в 1795. Она может быть проверена путем деления многоугольника на треугольники, но её также можно рассматривать как частный случай теоремы Грина.

Формула определения площади определяется путем взятия каждого ребра многоугольника АВ, и вычисления площади треугольника АВО с вершиной в начале координат О, через координаты вершин. При обходе вокруг многоугольника, образуются треугольники, включающие внутреннюю часть многоугольника и расположенные снаружи его. Разница между суммой этих площадей и есть площадь самого многоугольника. Поэтому формула называется формулой геодезиста, так как «картограф» находится в начале координат; если он обходит участок против часовой стрелки, площадь добавляется если она слева и вычитается если она справа с точки зрения из начала координат.

Формула площади верна для любого самонепересекающегося (простого) многоугольника, который может быть выпуклым или вогнутым.

Многоугольник

Пример

Давайте рассмотрим пример для многоугольника в точках (3, 4), (5, 6), (9, 4), (12, 8), (5, 11).

На примере мы убедились, что формула работает.

Доказательство

Давайте, заметим, что новая формула верна, если точка (0, 0) находится внутри многоугольника:

∑ i = 0 n − 1 S △ ( 0,0 ) ( x i , y i ) ( x i + 1 , y i + 1 ) + S △ ( 0,0 ) ( x n , y n ) ( x 0 , y 0 )

В другом случае мы можем перенести все точки с каким-то неизвестным коэфициентом, чтобы точка (0, 0) лежала внутри многоугольника. При раскрытии скобок коэффициенты переноса сократятся.

Как найти площадь многоугольника по координатам вершин

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code. /code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии «срочно надо», заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray
‘> Алгоритм вычисления площади многоугольника по координатам его углов.

  • Подписаться на тему
  • Сообщить другу
  • Скачать/распечатать тему

Сообщ. #1 , 23.11.08, 19:15

Рейтинг (т): нет

Пусть многоугольник задан координатами своих углов.Можно ли создать алгоритм вычисления его площади?
Понятно , если он выпуклый , это просто , программу можно сделать. А если невыпуклый , то как сделать алгоритм ?(а по нему программу написать можно..)

Сообщ. #2 , 23.11.08, 20:16

Рейтинг (т): 64

имхо, если многоугольник невыпуклый, то только через интегралы(или как частный случай — разбивать на прямоугольники и треугольники и вычислять)

Добавлено 23.11.08, 20:20
вот решение через интегралы на С++
http://opita.net/node/27
первая же ссылка в гугле на запрос «площадь невыпуклого многоугольника»

Сообщ. #3 , 23.11.08, 20:33

Рейтинг (т): нет

Вот , нашёл на Pascal :

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

Содержание
Введение
1 Разработка программной реализации
2 Проверка на контрольных примерах
3 Заключение
Приложение 1. Блок-схема.
Приложение 2. Программа.

Системы, подобные представленной, часто можно встретить в повседневной
жизни.
Данная задача не имеет аналитического решения. В геометрии существуют
формулы, позволяющие вычислять площади правильных многоугольников, но для
произвольных многоугольников таких формул нет. Решение задачи можно
получить численными методами. Рассмотрим два из них.
1. Площадь произвольной фигуры можно вычислить методом Монте-Карло.
Фигура вписывается в другую фигуру с известной площадью. Случайным
образом на последнюю ставятся произвольное количество точек. Площадь
определяется по формуле [pic], где Nф – количество точек попавших в
заданную фигуру, N – общее количество точек. Достоинство данного
метода заключается в простоте реализации, сложность состоит только в
определении попадания точки внутрь заданной фигуры. Очевидно, что
точность вычисленной площади зависит от количества точек. Приемлемая
точность может быть достигнута только при большом их количестве. В
этом заключается один из недостатков метода. Точность также сильно
зависит от качества генератора случайных чисел.
2. Из курса геометрии известно, что любой многоугольник можно разбить
на несколько треугольников, соединяя отрезками несмежные вершины.
Площадь многоугольника при этом будет равна сумме площадей
полученных треугольников. В этом заключается второй метод
определения площади. Площадь треугольника по заданным вершинам легко
определяется по аналитическим формулам, поэтому этот метод позволяет
получить большую точность при меньших затратах вычислительных
ресурсов.

РАЗРАБОТКА ПРОГРАММНОЙ МОДЕЛИ.

Решение задачи будем производить, разбивая одну большую и трудную
задачу на несколько небольших и несложных.
В черновом виде данный алгоритм можно представить в следующем виде:
1. Ввод вершин
2. Предварительная обработка
3. Пока количество вершин больше трех повторяем:
. Найти выпуклую вершин, т.е. вершину, внутренний угол которой меньше
1800. Например на рисунке вершины 1,3,4,5 являются выпуклыми.

. Отрезаем треугольник образованный этой вершиной и двумя смежными.
4. Площадь многоугольника будет равна сумме площадей отрезанных
треугольников и площади оставшегося (при выходе из цикла) треугольника.

Рассмотрим все пункты алгоритма.
1) Ввод данных. Данные будем хранить в текстовом файле ,каждая первая
строка которого содержит количество вершин, а последующие – пары
координат (X,Y), разделенных пробелом. Координаты вершин и внутренние
углы будем хранить в структуре типа:

sd: array[1..100] of
record
x,y: real;
angle: real;
end;

А количество вершин в глобальной переменной n.

Следующая процедура осуществляет ввод данных:

procedure input;
var f: text;
i: integer;

begin
Assign(f,’points.dat’);
reset(f);
readln(f, n);
for i:=1 to n do readln(f, sd[i].x, sd[i].y);
end;

2) Предварительная обработка.
В данном пункте алгоритма осуществляется вычисление внутренних углов
многоугольника.
Рассмотрим часть произвольного многоугольника:

Пусть вектор A образует с ось OX угол (1, а вектор B – угол (2. Тогда
угол между ними (внутренний угол многоугольника) будет равен
180–(1–(2. Здесь нельзя использовать формулу угла между векторами
через скалярное произведение, т.к таким образом вычисляется
минимальный угол. Но при этом возможен такой случай:

Угол будет внешним.
Так вычислим либо все внутренние, либо все внешние углы
многоугольника. Чтобы выяснить какие углы мы нашли, рассмотрим
следующую теорему:

Сумма внешних углов произвольного многоугольника больше суммы
внутренних.

Доказательство проведем по индукции:
1) Очевидно, что теорема справедлива для треугольника
2) Предположим, что теорема справедлива для k-угольника
3) Докажем теперь, что теорема справедлива для (k+1)-угольника.
Пусть сумма внутренних углов k-угольника равна (1, а внешних (2.
Из п.2 следует, что (1 <(2. k–угольник можно сделать (k+1)-
угольником «нарастив» его на один треугольник:

Тогда сумма внутренних узлов (k+1)-угольника – (1+(+(+(, а
внешних (2+(360-()-(-(. Из геометрии известно, что сумма углов
треугольника равна 1800. Тогда:
сумма внутренних углов: (1+180
сумма внешних углов: (2+360-((+(+()=(2+180.
Но из п.2 следует, что (1 <(2. Следовательно, сумма внешних углов
(k+1)-угольника больше суммы внутренних.(k+1)-угольника.
Теорема доказана.

Внутренние углы многоугольника будем вычислять следующим образом:
. для i-той вершины, имеющей координаты (Xi, Yi) найдем координаты
входящих и выходящих векторов:
A – входящий вектор
B – выходящий вектор
. Вычисляем углы, образованные этими векторами с осями координат
[pic]
[pic]
. Вычисляем угол i-той вершины (i=180–(1–(2.
. Находим сумму [pic]
. Находим сумму [pic]
. Если S1 случае внутренние углы равны 180-(i.

В языке Turbo Pascal нет функции Arccos(x), поэтому его вычисляем,
используя следующую формулу [pic]. Но значение этой функции может
изменяться в интервале от –900 до 900, поэтому при вычислении
действительного угла будем учитывать квадрант, в котором лежит
вектор.
Если в процессе отсечения углов произойдет ситуация, что три вершины
подряд окажутся на одной прямой, то необходимо вторую из них удалить,
т.к. она, строго говоря, не является вершиной и не будет влиять на
дальнейшие вычисления. Для определения, лежит ли i-ая вершина на
прямой, соединяющей (i–1)-ую и (i+1)-вершины, аналогично найдем
входящий и выходящий вектора A и B. Затем их нормируем, т.е. делим
каждую координату вектора на модуль этого вектора. Если после этого
вектора окажутся равны, т.е. окажутся равными их координаты, то i-тую
вершину можно удалить.

Учитывая все вышеприведенное, составляем процедуру вычисления
внутренних углов.

procedure Angles;
var
al1,al2,
dx, dy, dxp, dyp,
s_in, s_out, a: real;
i,j: integer;

function ArcCos(a: real): real;
var res: real;
begin
if abs(a) else res:=ArcTan(sqrt(1-a*a)/a);
if dx if dy>=0 then res:=pi+res
else res:=-pi-res
else
if dy ArcCos:=res
end;

begin
dxp:=sd[1].x-sd[n].x;
dyp:=sd[1].y-sd[n].y;
a:=sqrt(dxp*dxp+dyp*dyp);
dxp:=dxp/a;
dyp:=dyp/a;
i:=1;
while i begin
dx:=sd[i+1].x-sd[i].x;
dy:=sd[i+1].y-sd[i].y;
a:=sqrt(dx*dx+dy*dy);
dx:=dx/a;
dy:=dy/a;
if (dx=dxp) and (dy=dyp) then
begin
dec(n);
for j:=i to n do sd[j]:=sd[j+1];
end;
dxp:=dx; dyp:=dy;
inc(i)
end;

dx:=sd[1].x-sd[n].x;
dy:=sd[1].y-sd[n].y;
al1:=ArcCos(dx/sqrt(dx*dx+dy*dy));
for i:=1 to n-1 do
begin
dx:=sd[i+1].x-sd[i].x;
dy:=sd[i+1].y-sd[i].y;
al2:=ArcCos(dx/sqrt(dx*dx+dy*dy));
sd[i].angle:=pi-al1+al2;
if sd[i].angle>2*pi then sd[i].angle:=sd[i].angle-2*pi
else
if sd[i].angle al1:=al2
end;
dx:=sd[1].x-sd[n].x;
dy:=sd[1].y-sd[n].y;
al2:=ArcCos(dx/sqrt(dx*dx+dy*dy));
sd[n].angle:=pi-al1+al2;
if sd[n].angle>2*pi then sd[n].angle:=sd[n].angle-2*pi
else
if sd[n].angle s_in:=0;
s_out:=0;
for i:=1 to n do
begin
if sd[i].angle S_in:=S_in+sd[i].angle;
S_out:=S_out+(2*pi-sd[i].angle);
end;
if S_out for i:=1 to n do sd[i].angle:=2*pi-sd[i].angle;
end;

3) Нахождение выпуклых вершин.
Как было сказано выше, внутренний угол выпуклой вершины меньше 1800.
Но не всякую выпуклую вершину можно «отрезать», т.к. линия «отреза»
может пересекать стороны многоугольника. Например, вершину А
«отрезать» нельзя:

Эта задача сводится к задаче о пересечении двух отрезков. Пусть
отрезки заданы координатами своих концов. Первый отрезок A1(X1A, Y1A)
и
A2(X2A, Y2A). Второй – B1(X1B, Y1B) и B2(X2B, Y2B).
1) Запишем уравнения прямой, проходящей через точки A1 и A2.
[pic]
Преобразуем его в форму вида:
[pic]

Из геометрии известно, что если две точки находятся по одну сторону
от прямой, то при подстановке их координат в полином левой части
получим значения одного знака. Таким образом, если точки B1 и B2
располагаются по разные стороны от прямой, то
(AX1B+BY1B+C)(AX2B+BY2B+C)

Но пересечение прямых не является достаточным для пересечения
отрезков, например:

Эти отрезки не пересекаются.
Для достаточного доказательства пересечения отрезков необходимо
произвести все вышеприведенные операции над точками B1 и B2, т.е.
провести через них прямую и выяснить расположение точек A1 и A2
относительно ее.

Таким образом определяем возможность отсечения вершины
многоугольника с количеством вершин, больше четырех.
Для некоторых видов четырехугольника это условие не несправедливо,
например:

Здесь вершину A отсечь нельзя. Для четырехугольника определяем
расположение отсекаемой вершины и вершины, несмежной с ней (через
оставшиеся проходит «линия отреза»). Если они расположены по одну
сторону, как на рисунке, то отсекать нельзя. Приведенный алгоритм
контроля реализуем в следующей функции:

function cross(c: integer): boolean;
var a, b, i: integer;
AA, BB, CC,
AA1, BB1, CC1: real;

function Mline(x,y: real): real;
begin
Mline:=AA*x+BB*y+CC
end;

function Sline(x,y: real): real;
begin
Sline:=AA1*x+BB1*y+CC1
end;

begin
if c=1 then
begin
a:=n;
b:=2;
end
else if c=n then
begin
a:=n-1;
b:=1;
end
else
begin
a:=c-1;
b:=c+1;
end;
cross:=true;
AA:=sd[b].y-sd[a].y;
BB:=-(sd[b].x-sd[a].x);
CC:=sd[a].y*(sd[b].x-sd[a].x)-sd[a].x*(sd[b].y-sd[a].y);
if n=4 then
begin
for i:=1 to n do
if (Mline(sd[i].x, sd[i].y)*Mline(sd[c].x, sd[c].y)>0) and (i<>c)
then exit;
cross:=false;
exit
end;
for i:=1 to n-1 do
begin
AA1:=sd[i+1].y-sd[i].y;
BB1:=-(sd[i+1].x-sd[i].x);
CC1:=sd[i].y*(sd[i+1].x-sd[i].x)-sd[i].x*(sd[i+1].y-sd[i].y);
if Mline(sd[i].x, sd[i].y)*Mline(sd[i+1].x,sd[i+1].y) if Sline(sd[a].x, sd[a].y)*Sline(sd[b].x,sd[b].y) end;
AA1:=sd[1].y-sd[n].y;
BB1:=-(sd[1].x-sd[n].x);
CC1:=sd[n].y*(sd[1].x-sd[n].x)-sd[n].x*(sd[1].y-sd[n].y);
if Mline(sd[n].x, sd[n].y)*Mline(sd[1].x,sd[1].y) if Sline(sd[a].x, sd[a].y)*Sline(sd[b].x,sd[b].y) cross:=false;
end;

4) Вычисление площадей отсеченных треугольников будем по формуле Герона
[pic]
где [pic].

function St(x1,y1, x2,y2, x3,y3: real): real;
var a, b, c, p: real;
begin
a:=sqrt(sqr(x1-x2)+sqr(y1-y2));
b:=sqrt(sqr(x1-x3)+sqr(y1-y3));
c:=sqrt(sqr(x3-x2)+sqr(y3-y2));
p:=(a+b+c)/2;
St:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

5) Отсечение i-той вершины

dec(n);
for j:=i to n do sd[j]:=sd[j+1];

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

После вычисления площади, выводим ее на экран и ожидаем нажатия любой
клавиши.

Writeln(‘Площадь фигуры: ‘, S:3:3);
Readkey

Полный текст программы приведен в приложении 2.

Проверка на контрольных примерах.

Проверим работу программы на фигурах, площади которых можно вычислить по
формулам.
1) Треугольник

Содержимое файла points.dat
3
0 0
5 0
2 3
Площадь треугольника по формуле: [pic]
Результат работы программы:

Площадь фигуры: 7.500

Содержимое файла points.dat
4
0 0
5 0
5 3
0 3

Площадь прямоугольника по формуле [pic]
Результат работы программы

Площадь фигуры: 15.000

3) Невыпуклая фигура

Содержимое файла points.dat
4
0 0
3 2
2 0
3 -2
Эта фигура симметрична относительно оси OX. Ее площадь будет равна
[pic]
Результат работы программы:

Площадь фигуры: 4.000
Заключение.
Рассмотренный алгоритм является комбинацией аналитического и численного
методов. Поэтому он включает в себя достоинства обоих. Т.к. основной
операцией вычисления площади многоугольника является вычисление площади
элементарного треугольника, то на результат вычисления не будут влиять
методические погрешности, т.е. погрешности вносимые самим алгоритмом. Этим
приведенный алгоритм отличается от метода Монте-Карло, точность которого
зависит от количества точек. Погрешность будет вноситься лишь на этапе
вычислений и будет определяться конкретной ЭВМ, на которой ведется расчет.
Точность зависит от вещественного типа Real, в котором представляются
основные переменные. Данный тип представим в компьютере лишь с определенной
точностью, зависящей от внутреннего формата числа. Для персонального
компьютера типа IBM PC/AT тип Real имеет следующие параметры:
Длинна, байт 6
Количество значащих цифр 11…12
Диапазон десятичного порядка -39…+38
Эта точность вполне удовлетворительна для нашей задачи.

Приложение 2. Текст программы.

Uses Crt;
const max=100;
var
n, i, j: integer;
sd: array[1..100] of
record
x,y: real;
angle: real;
end;
S: real;

procedure Angles;
var
al1,al2,
dx, dy, dxp, dyp,
s_in, s_out, a: real;
i,j: integer;

function ArcCos(a: real): real;
var res: real;
begin
if abs(a) else res:=ArcTan(sqrt(1-a*a)/a);
if dx if dy>=0 then res:=pi+res
else res:=-pi-res
else
if dy ArcCos:=res
end;

begin
dxp:=sd[1].x-sd[n].x;
dyp:=sd[1].y-sd[n].y;
a:=sqrt(dxp*dxp+dyp*dyp);
dxp:=dxp/a;
dyp:=dyp/a;
i:=1;
while i begin
dx:=sd[i+1].x-sd[i].x;
dy:=sd[i+1].y-sd[i].y;
a:=sqrt(dx*dx+dy*dy);
dx:=dx/a;
dy:=dy/a;
if (dx=dxp) and (dy=dyp) then
begin
dec(n);
for j:=i to n do sd[j]:=sd[j+1];
end;
dxp:=dx; dyp:=dy;
inc(i)
end;

dx:=sd[1].x-sd[n].x;
dy:=sd[1].y-sd[n].y;
al1:=ArcCos(dx/sqrt(dx*dx+dy*dy));
for i:=1 to n-1 do
begin
dx:=sd[i+1].x-sd[i].x;
dy:=sd[i+1].y-sd[i].y;
al2:=ArcCos(dx/sqrt(dx*dx+dy*dy));
sd[i].angle:=pi-al1+al2;
if sd[i].angle>2*pi then sd[i].angle:=sd[i].angle-2*pi
else
if sd[i].angle al1:=al2
end;
dx:=sd[1].x-sd[n].x;
dy:=sd[1].y-sd[n].y;
al2:=ArcCos(dx/sqrt(dx*dx+dy*dy));
sd[n].angle:=pi-al1+al2;
if sd[n].angle>2*pi then sd[n].angle:=sd[n].angle-2*pi
else
if sd[n].angle s_in:=0;
s_out:=0;
for i:=1 to n do
begin
if sd[i].angle S_in:=S_in+sd[i].angle;
S_out:=S_out+(2*pi-sd[i].angle);
end;
if S_out for i:=1 to n do sd[i].angle:=2*pi-sd[i].angle;

procedure input;
var f: text;
i: integer;

begin
Assign(f,’points.dat’);
reset(f);
readln(f, n);
for i:=1 to n do readln(f, sd[i].x, sd[i].y);
end;

function St(x1,y1, x2,y2, x3,y3: real): real;
var a, b, c, p: real;
begin
a:=sqrt(sqr(x1-x2)+sqr(y1-y2));
b:=sqrt(sqr(x1-x3)+sqr(y1-y3));
c:=sqrt(sqr(x3-x2)+sqr(y3-y2));
p:=(a+b+c)/2;
St:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

function cross(c: integer): boolean;
var a, b, i: integer;
AA, BB, CC,
AA1, BB1, CC1: real;

function Mline(x,y: real): real;
begin
Mline:=AA*x+BB*y+CC
end;

function Sline(x,y: real): real;
begin
Sline:=AA1*x+BB1*y+CC1
end;

begin
if c=1 then
begin
a:=n;
b:=2;
end
else if c=n then
begin
a:=n-1;
b:=1;
end
else
begin
a:=c-1;
b:=c+1;
end;
cross:=true;
AA:=sd[b].y-sd[a].y;
BB:=-(sd[b].x-sd[a].x);
CC:=sd[a].y*(sd[b].x-sd[a].x)-sd[a].x*(sd[b].y-sd[a].y);
if n=4 then
begin
for i:=1 to n do
if (Mline(sd[i].x, sd[i].y)*Mline(sd[c].x, sd[c].y)>0) and (i<>c)
then exit;
cross:=false;
exit
end;
for i:=1 to n-1 do
begin
AA1:=sd[i+1].y-sd[i].y;
BB1:=-(sd[i+1].x-sd[i].x);
CC1:=sd[i].y*(sd[i+1].x-sd[i].x)-sd[i].x*(sd[i+1].y-sd[i].y);
if Mline(sd[i].x, sd[i].y)*Mline(sd[i+1].x,sd[i+1].y) if Sline(sd[a].x, sd[a].y)*Sline(sd[b].x,sd[b].y) end;
AA1:=sd[1].y-sd[n].y;
BB1:=-(sd[1].x-sd[n].x);
CC1:=sd[n].y*(sd[1].x-sd[n].x)-sd[n].x*(sd[1].y-sd[n].y);
if Mline(sd[n].x, sd[n].y)*Mline(sd[1].x,sd[1].y) if Sline(sd[a].x, sd[a].y)*Sline(sd[b].x,sd[b].y) cross:=false;
end;

begin
ClrScr;
input;
Angles;
S:=0;
while n>3 do
begin
i:=1;
while (sd[i].angle>pi) or (cross(i)) do
inc(i);
if i=1 then
S:=S+St(sd[1].x,sd[1].y, sd[2].x,sd[2].y, sd[n].x,sd[n].y)
else
if i=n then
S:=S+St(sd[n].x,sd[n].y, sd[1].x,sd[1].y, sd[n-1].x,sd[n-
1].y)
else S:=S+St(sd[i].x,sd[i].y, sd[i-1].x,sd[i-1].y,
sd[i+1].x,sd[i+1].y);
dec(n);
for j:=i to n do sd[j]:=sd[j+1];
Angles
end;
S:=S+St(sd[1].x,sd[1].y, sd[2].x,sd[2].y, sd[3].x,sd[3].y);
Writeln(‘Площадь фигуры: ‘, S:3:3);
Readkey
end.

Как думаете ,ошибок здесь нет?
Мне это придётся в Delphi перегнать..

Как найти площадь многоугольника по координатам вершин

60. Площадь многоугольника

Заданы координаты n последовательных вершин многоугольника. Определить его площадь.

Вход. Первая строка содержит количество вершин многоугольника n (3 ≤ n ≤ 50000). В следующих n строках заданы координаты его последовательных вершин xi, yi (-1000 ≤ xi, yi ≤ 1000).

Выход. Вывести площадь многоугольника с тремя десятичными знаками.

Пример входа

Пример выхода

Пусть А1( x1, y1), А2(x2, y2), …, А n (xn, yn) – координаты вершин простого (без самопересечений) многоугольника, заданные в порядке его обхода по или против часовой стрелки. Тогда его площадь вычисляется по формуле трапеций:

где А n +1 ( xn+1, yn+1) = А1( x1, y1). Значение суммы следует брать по модулю, так как оно может быть как положительным, так и отрицательным в зависимости от направления обхода многоугольника.

Площадь трапеции положительна при xi +1 > xi и отрицательна при xi > xi +1 .

Площадь многоугольника ABCDE равна

Площадь многоугольника можно найти по формуле Сюрвейера (Surveyor):

Пусть О(0, 0) – центр координат. Тогда площадь многоугольника равна сумме площадей треугольников OA 1 A 2 , OA 2 A 3 , OA 3 A 4 , … , OAnA 1 . Если треугольник ориентирован против часовой стрелки, то его площадь положительна. Если против – то отрицательна. Площадь треугольника OAiA i +1 равна

Координаты точек храним в векторах x и y. То есть координаты i-ой точки будут содержаться в (x[i], y[ i]).

#define MAX 1002

Функция findArea вычисляет площадь многоугольника по выше приведенной формуле трапеций.

double findArea( int *x, int *y)

for ( int i = 0; i < n; i++)

s += (y[i+1] + y[i]) * (x[i+1] — x[i]) / 2.0;

Основная часть программы. Читаем входные данные.

Вычисляем и выводим площадь многоугольника.

printf( «%.3lf\n» ,findArea(x,y));

Реализация алгоритма – формула Сюрвейера

using namespace std;

double findArea(vector < int >&x, vector < int >&y)

s += y[i+1] * x[i] — y[i] * x[i+1];

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *