asyan.org
добавить свой файл
1 2
Визначення площі довільного многокутника

За заданими координатами вершин многокутника визначити його площу.

Для обчислення площі можна використати формулу:



Обґрунтування:

1) Для трикутника:




(x1,y1)

(x2,y2)

(x3,y3)


Координати векторів (x2- x1,y2-y1), (x3- x1,y3-y1).

Модуль векторного добутку рівний площі паралелограма, а ½ модуля векторного добутку - площі трикутника.


2) Структуру формули можна зрозуміти на прикладі трикутника.
3

Справді, а наприклад, площа трапеції дорівнює

Зазначимо, площа фігури, заданої точками А1, … , Аn, n³4, залежить від порядку, в якому задано вершини. Наприклад, якщо вершини розміщені на площині так, як показано на малюнку, то дістанемо фігуру, яка називається чотиривершинником (його площа заштрихована).

2
3) Структуру формули можна зрозуміти на прикладі многокутника.

Нехай потрібно визначити площу многокутника A1, A2, A3, A4, A5 з координатами вершин x1,y1; x2,y2; x3,y3; x4,y4; x5,y5. Площа многокутника S можна преставити трапеціями, у яких абсциси є основними, а різниця ординат сусідніх точок висотами.
http://algolist.manual.ru/maths/geom/polygon/gif/polsquare.gif
S = a1A1A2a2 + a2A2A3a3 + a3A3A4a4 - a5A5A4a4 - a1A1A5a5.
2S = (x1 + x2)(y2 - y1) + (x2 + x3)(y3 - y2) + (x3 + x4)(y4 - y3) +

+(x4 + x5) (y5 - y4) + (x5 + x1)(y1 - y5).    

Після розкриття дужок і приведення подібних членів отримаємо

2S = x1y2 - x2y1 + x2y3- x3y2 + x3y4 - x4y3 + x4y5 - x5y4 + x5y1 - x1y5

Після винесення за дужки x1, x2, x3, x4, x5 будемо мати

2S = x1(y2-y5) + x2(y3-y1) + x3(y4-y2) + x4(y5-y3) + x5(y1-y4)

а якщо з винести за дужки y1, y2, y3, y4, y5. то будемо мати

2S = y1(x5-x2) + y2(x1-x3) + y3(x2-x4) + y4(x3-x5) + y5(x4-x1).

В скороченому вигляді ці формули можна записати так:

http://algolist.manual.ru/maths/geom/polygon/gif/s1.gif
http://algolist.manual.ru/maths/geom/polygon/gif/s2.gif

Після перетворення отримаємо формулу в її нормальному вигляді.

http://algolist.manual.ru/maths/geom/polygon/gif/sall.gif

, де X0,Y0 = Xn+1,Yn+1

У програмі використовуються змінні:

n – кількість вершин;

s – площа многокутника:

x[1..n+1], y[1..n+1] – масиви координати вершин;

і - змінна циклу.

На n+1 позицію заносимо координати першої вершини.

Програмний код:

Program Prog 3;

var x,y:array[1..100] of real;

i,n:integer;

s:real;

begin

write('n=');

readln(n);

for i:=1 to n do

readln(x[i],y[i]);

x[n+1]:=x[1];

y[n+1]:=y[1];

s:=0;

for i:=1 to n do

s:=s+(x[i]*y[i+1]-x[i+1]*y[i]);

s:=1/2*abs(s);

writeln('s=',s:2:2);

end.
Побудова опуклої оболонки для множини з N точок площини.

Опуклою оболонкою деякої заданої множини точок називається перетин всіх опуклих множин, що містять задану множину. Для скінченої множини точок опуклою оболонкою буде завжди опуклий багатокутник, всі вершини якого є точками заданої множини.

Задача полягає в тому, щоб для заданої скінченої множини точок знайти вершини опуклої оболонки цієї множини. Будемо перераховувати вершини в порядку перегляду проти годинникової стрілки. Для ефективного розв’язування цієї задачі існує декілька різних алгоритмів. Наведемо найбільш просту реалізацію одного з них – алгоритму Джарвіса. Цей алгоритм інколи називають «загортання подарунка» (див. мал. 18).



Мал. 18

Перерахунок точок шуканої межі опуклого багатокутника почнемо з правої нижньої точки Р1, яка належить межі опуклої оболонки. Позначимо її координати 1, у1). Наступною при заданому обході буде точка Р22, у2). Вона має таку властивість, яку мають всі інші точки , що лежать зліва від вектора , тобто орієнтований кут між векторами і невід’ємний для будь-якої іншої точки М нашої множини. Для претендента на роль точки Р2 перевіримо виконання умови [, ] ? 0 зі всіма точками М. Якщо точок, що задовольняють цю умову, декілька, то вершиною шуканого багатокутника буде та з них, для якої довжина вектора =(х21, у21) максимальна.

Аналогічно будемо шукати інші вершини. Припустимо, що вже знайдена і-та вершина Ріі, уі) опуклої оболонки. Для наступної точки Рі+1і+1, уі+1) косі добутки [] невід’ємні для всіх точок М. Якщо таких точок декілька, то вибираємо ту, для якої вектор має найбільшу довжину. Пошук такої точки можна здійснювати так: спочатку ми можемо вважати наступною, (і+1)-шою, будь-яку точку. Потім знаходимо значення [], де М- всі інші точки. Якщо для однієї з них даний вираз буде менше нуля, то вважатимемо її наступною і продовжимо перевірку інших точок (аналогічно алгоритму пошуку мінімального елемента в масиві). Якщо значення виразу дорівнює нулю, то порівнюємо квадрати довжин векторів. В результаті за О(N) операцію ми знайдемо наступну вершину опуклої оболонки. Продовжуючи процес далі, ми повернемося до точки Р1. А це означає, що опукла оболонка побудована.

При розв’язуванні даної задачі у випадку цілочисельних координат ми повністю можемо уникнути використання дійсної арифметики, а тому, уникнути від втрати точності обчислень. В противному випадку в розв’язках можуть бути отримані «лишні» точки, близькі до межі опуклої оболонки , або не враховані деякі з «потрібних» точок. Складність даного алгоритму О(kN), де k – кількість точок опуклої оболонки, в гіршому випадку дорівнює N.

Наведемо варіант реалізації даного алгоритму. Множина даних точок знаходиться в масиві, а всі точки, що належать опуклій оболонці, будемо записувати в масив b.

type vv=record

x, y: longint;

end;

var a, b: array [1..100] of vv;

min, m, i, j, k, n: integer;

function vect (a1, a2, b1,b2: vv): longint;

{косий добуток векторів a1a2 і b1b2}

begin

vect:=(a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y)

end;

function dist2(a1, a2: vv): longint;

{квадрат довжини вектора a1a2}

begin

dist2:=sqr(a2.x-a1.x)+sqr(a2.y-a1.y)

end;

begin {Main}

readln (n); {кількість точок}

for i:=1 to n do

read (a[i].x, a[i].y);

{шукаємо праву нижню точку}

m:=1;

for i:=2 to n do

if a[i].ythen m:=i else

if (a[i].y=a[m].y) and (a[i].y>a[m].y) then m:=i;

{запишемо її в масив опуклої оболонки b і переставимо на перше місце в масиві a}

b[1]:=a[m];

a[m]:=a[1];

a[1]:=b[1];

k:=1;

min:=2;

repeat

{шукаємо наступну вершину опуклої оболонки}

for j:=2 to n do

if (vect(b[k], a[min], b[k],a[j])<0 or ((vect(b[k], a[min], b[k],a[j])=0) and

(dist2(b[k], a[min])< (dist2(b[k], a[j])))

then min:=j;

k:=k+1;

{записана наступна вершина}

b[k]:=a[min];

min:=1;

until (b[k].x=b[1].x) and (b[k].y=b[1].y);

{поки ламана не замкнеться}

for j:=1 to k-1 do {друк результатів}

writeln (b[j].x,’’,b[j].y)

end.

Існує інший алгоритм розв’язання цієї задачі (алгоритм Грехема) з обчислювальною складністю О(NlogN), оснований на попередньому сортуванні точок даної множини за значенням кута в полярній системі координат з центром в одній із точок опуклої оболонки. Тобто найбільш складним буде сортування заданих точок. Сортування точок можна виконувати за знаком косого добутку [], де Р1будь-яка вершина опуклої оболонки (наприклад, права нижня точка). У відсортованому масиві точок всі дані добутки повинні бути невід’ємними. Точки з рівними кутами ([]=0) розміщуються в порядку збільшення довжин відповідних векторів (мал. 19).


Мал.19. Вершини опуклої оболонки множини точок {Pi}: P1, P4, P5, P6, P9, P12. Номери всіх точок відповідають сортуванню за полярним кутом.
Далі перегляд Грехема використовує стек, в якому зберігаються точки, що є претендентами в опуклу оболонку. Спочатку в стек заносять першу з відсортованих точок. Потім – сусідню з нею вершину опуклої оболонки. Якщо на першому із променів точок декілька, то ця точка променя Pi, найбільш віддалена від P1. Третя – точка Pі+1. Нехай на вершині стека знаходиться точка Pk. Розглянемо наступну в порядку збільшення полярного кута точку заданої множини Pi. Поки частина ламаної Pk-1, Pk, Pi не є опуклим (див. задачу 4.2.), із стеку вилучається наступна точка Pk. Потім Pi заноситься до стеку. В момент закінчення перегляду всіх точок в стеці будуть знаходитись всі вершини опуклої оболонки. Так як будь-яка точка заноситься в стек не більше одного разу, тому час перегляду складає О(N).

Наведемо приклад реалізації саме цього перегляду. Для наочності сортування зробимо методом «бульбашки». В якості стека використовується масив b. Описи змінних і функцій співпадають з наведеними вище.



следующая страница >>