ст.
Вступ ………………………………………………………
1. Визначення площі многокутника …………………
Задача 1. Визначення довжини відрізка …………...
Задача 2. Визначення площі трикутника (формула Герона) ……………………………………………….
Задача 3. Визначення площі трикутника за заданими координатами вершин …………………
Задача 4. Визначення площі опуклого многокутника ……………………………………….
Задача 5. Визначення площі довільного многокутника ……………………………………….

2. Визначення положення точки відносно
n-кутника:
Задача 1. Перевірка належності точки прямій ……
Задача 2. Перевірка належності точки відрізку …..
Задача 3. Перевірка належності точки трикутнику
Задача 4. Перевірка належності точки многокутнику ………………………………………..

3. Визначення опуклої оболонки ………………………
4. Задачі на обчислювальну геометрію ……………….

Література ……………………………………………….
4
7
7

8

9

10

11

16
16
16
18

20

26
30

45

Вступ
На початку 70-х років Н.Вірт розробив мову програмування Паскаль, призначену для початкового навчання структурному програмуванню. Вона була створена на базі мови Алго-60. Поява надійних трансляторів з мови Паскаль, що займають невеликий обсяг пам’яті, привела до поширення її серед різних категорій користувачів.
У багатьох навчальних закладах навчання програмуванню починається з мови Паскаль. Це зумовлюється такими особливостями мови:
1. Простота і природність мови.
2. Побудова мови за принципами структурного програмування та структурованої організації даних.
3. Здійснення розробки трансляторів з мови Паскаль за допомогою доступних і добре опрацьованих методик.
4. Транслятор дозволяє оптимізувати програми.
5. Конструкції навчальної алгоритмічної мови аналогічні до відповідних операторів Паскаль.
Популярність мови особливо зросла після створення трансляторів для персональних комп’ютерів. Виникли численні версії мови. Найпоширішеною є діалект мови, розроблений фірмою Borland International, Inc під назвою Turbo Pascal. Ця версія сумісна з міжнародним стандартом ISO Pascal Standart 1982. Вона була поширена на 8 і 16 – розрядних персональних комп’ютерах. Для 32-розрядних нових комп’ютерів використовуються новіші версії Borland Pascal, Free Pascal, Delphi (в основі лежить Object Pascal).
Посібник містить опис алгоритмів та програм, що реалізовують математичні методи обчислювальної геометрії. Так як згідно Програми для загальноосвітніх навчальних закладів (Навчальні програми для профільного навчання, Програми факультативів, спецкурсів, пропедевтичних
курсів, гуртків, Програми для загальноосвітніх навчальних закладів, спеціалізованих шкіл, гімназій, ліцеїв,
Інформатика та програмування 8-11 класи (Автори: Голубніча Н.В., Караванова Т.П., Костюков В.П.) пропонується викладати теми: Методи складання алгоритмів та їх аналіз, яка містить наступні розділи:
1. Методика побудови алгоритмів, оцінка їх ефективності.
2. Структури даних.
3. Пошукові алгоритми.
4. Методи сортування.
5. Обчислювальна геометрія та числові методи.
6. Застосування комбінаторики для розв’язання задач.
7. Основи теорії графів.
8. Основи лінійного програмування.
9. Основи динамічного програмування.
10. “Жадібні” алгоритми.

При вивченні теми «Обчислювальна геометрія та числові методи» учні повинні знати:
- сутність векторного добутку та напрямку повороту;
- сутність умов перетину відрізків;
- алгоритми визначення площі простого многокутника, положення точки відносно простого многокутника, опуклої оболонки, пари найближчих точок, пари найвіддаленіших точок;
- алгоритм метода виключення для розв’язання алгоритмічних задач.
Учні повинні мати уявлення про:
- застосування поняття векторного добутку для реалізації алгоритмів розв’язання геометричних задач.
Учні повинні вміти:
- застосовувати алгоритми визначення площі простого многокутника, положення точки відносно простого многокутника, опуклої оболонки, пари найближчих точок, пари найвіддаленіших точок для реалізації конкретних задач;
застосовувати алгоритм метода виключення для реалізації конкретних задач.
Як раз свій варіант викладання теми «Обчислювальна геометрія та числові методи» я пропоную в даному посібнику з використанням опису підпрограм.

1. Визначення площі многокутника
Задача 1. Визначення довжини відрізка
За заданими координатами початку і кінця відрізка визначити його довжину.

Довжина відрізка
Процедура визначення довжини:

procedure line(x0,y0,x,y:real;var l:real);
begin
l:=sqrt(sqr(x-x0)+sqr(y-y0));
end;

Задача 2. Визначення площі трикутника (формула Герона)
За заданими сторонами трикутника визначити площу трикутника.

Площа тритника за формула Герона обчислюється:
, де
Процедура визначення площі трикутника:

procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

Задача 3. Визначення площі трикутника за заданими координатами вершин
За заданими координатами вершин трикутника визначити його площу.
Для визначення площі скористуємось двома процедурами за координатами знаходимо довжини сторін за довжинами сторін визначаємо площу трикутника.
Програмний код:

Program pr1;
var x1,y1,x2,y2,x3,y3,st:real;
procedure line(x0,y0,x,y:real;var l:real);
begin
l:=sqrt(sqr(x-x0)+sqr(y-y0));
end;
procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

begin
readln(x1,y1,x2,y2,x3,y3);
line(x1,y1,x2,y2,a);
line(x2,y2,x3,y3,b);
line(x3,y3,x1,y1,c);
pl(a,b,c,st);
writeln (st);
end.

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

Розбиваємо многокутник на трикутники і знаходимо суму трикутників. Координати вершин многокутника заносимо в массив.
Програмний код:

Program Prog 2;
var xx,yy:array[1..100] of real;
a1,b1,c1,st,s_mn:real;
i,n:integer;
procedure line(x0,y0,x,y:real;var l:real);
begin
l:=sqrt(sqr(x-x0)+sqr(y-y0));
end;

procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;
begin
readln(n);
for i:=1 to n do readln(xx[i],yy[i]);
s_mn:=0;
for i:=1 to n-2 do begin
line(xx[1],yy[1],xx[i+1],yy[i+1],a1);
line(xx[i+1],yy[i+1],xx[i+2],yy[i+2],b1);
line(xx[i+2],yy[i+2],xx[1],yy[1],c1);
pl(a1,b1,c1,st);
s_mn:=s_mn+st;
end;
writeln(s_mn);
end.
end.

Задача 5. Визначення площі довільного многокутника
За заданими координатами вершин многокутника визначити його площу.
Для обчислення площі можна використати формулу:

Обґрунтування:
1) Для трикутника:

Координати векторів (x2- x1,y2-y1), (x3- x1,y3-y1).
Модуль векторного добутку рівний площі паралелограма, а ½ модуля векторного добутку - площі трикутника.

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

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

3) Структуру формули можна зрозуміти на прикладі многокутника.
Нехай потрібно визначити площу многокутника A1, A2, A3, A4, A5 з координатами вершин x1,y1; x2,y2; x3,y3; x4,y4; x5,y5. Площа многокутника S можна преставити трапеціями, у яких абсциси є основними, а різниця ординат сусідніх точок висотами.

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).
В скороченому вигляді ці формули можна записати так:


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

, де 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.

2. Визначення положення точки відносно
n-кутника

Задача 1. Перевірка належності точки прямій
Підставляємо координати точки в рівняння прямої і дивимося, чи є вони рішенням даних рівнянь. Так - належить, Ні - не належить.
Нехай (x1,y1), (x2,y2) – точки на прямій, то рівняння прямої буде наступним: (x-x1)( y2-y1)=(y- y1)(x2-x1).
Функція перевірки належності точки з координатами (x,y) , буде наступна:
Function ft(x,y:real):Boolean;
Begin
If (x-x1)*(y2-y1)=(y- y1)*(x2-x1) then ft:=true else ft:=false;
End;

Задача 2. Перевірка належності точки відрізку
Як визначити, чи належить точка A(x,y) відрізку з кінцевими точками B(x1,y1) і C(x2,y2)?
1) Це можна зробити через довжини відрізків BA+AC=BC.
2) За належністю точки прямій, яка містить відрізок і розміщення точки між початком та кінцем відрізка.
Нехай (x1,y1), (x2,y2) – координати початку і кінця відрізка, то рівняння прямої буде наступним:
(x-x1)( y2-y1)=(y- y1)(x2-x1).
Функція перевірки належності точки з координатами (x,y) , буде наступна:

Function ft(x,y:real):Boolean;
Begin
If (x-x1)*(y2-y1)=(y- y1)*(x2-x1) then
If (((x>=x1)and(x<=x2)and(x1<=x2))or((x>=x2)and(x<=x1)and(x2<=x1)))
then ft:=true else ft:=false;
End;
3) Точки відрізка z можна описати рівнянням
pOB+(1-p)OC=z, 0<=p<=1, OB і ОC - вектори.
Якщо існує таке p, 0<=p<=1, що
pOB+(1-p)OC=A, то А лежить на відрізку, інакше - ні.
Рівність розписується по координатний так:
px1+(1-p)x2=x
py1+(1-p)y2=y
З першого рівняння знаходимо p, підставляємо в друге: якщо одержуємо рівність і 0<=p<=1, то А на відрізку, інакше - ні.
px1+x2-px2=x  p(x1-x2)=x-x2  p= (x-x2)/ (x1-x2)
(x-x2)/ (x1-x2)y1+(1-(x-x2)/(x1-x2))y2=y
Програмний код і тестування проробіть саостійно.
Задача 3. Перевірка належності точки трикутнику
Для трикутника можна розробити алгоритм, який обчислює площі трикутників утворених даною точкою і сторонами трикутника, якщо сума утворених трикутників рівна сумі трикутника, то точка належить трикутнику, інакше не належить.

Нехай (x1,y1), (x2,y2), (x3,y3) – координати вершин трикутника;
(x,y) – координати точки для перевірки.

Програмний код:
Program pr4;
var x1,y1,x2,y2,x3,y3,x,y,a1,b1,c1,s1,s2,s3,st:real;

procedure line(xp,yp,xk,yk:real; var l:real);
begin
l:=sqrt(sqr(xp-xk)+sqr(yp-yk));
end;
procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

begin
writeln(‘Введіть координати вершин трикутника’);
readln(x1,y1,x2,y2,x3,y3);
writeln(‘Введіть координати точки’);
readln(x,y);
line(x1,y1,x2,y2,a1); line(x1,y1,x,y,b1); line(x2,y2,x,y,c1);
pl(a1,b1,c1,s1);

line(x2,y2,x3,y3,a1); line(x2,y2,x,y,b1); line(x3,y3,x,y,c1);
pl(a1,b1,c1,s2);

line(x3,y3,x1,y1,a1); line(x3,y3,x,y,b1); line(x1,y1,x,y,c1);
pl(a1,b1,c1,s3);

line(x1,y1,x2,y2,a1); line(x2,y2,x3,y3,b1); line(x3,y3,x1,y1,c1);
pl(a1,b1,c1,st);

if s1+s2+s3=st then writeln(‘належить’) else writeln(‘не належить’);
end.

Задача 3. Перевірка належності точки многокутнику
Під належністю точки многокутнику приймається належність точки внутрішній області многокутника або його межі. В тому числі, всі вершини належать многокутнику.
1) Аналогічно до задачі про належність точки трикутнику, можна розв’язати задачу для довільного опуклого многокутника, розбивши його на трикутники.

Програмний код:
Program Prog 5;
var xx,yy:array[1..100] of real;
x,y,a1,b1,c1,s1,s_mn, s_tr:real;
i,n:integer;
procedure line(xp,yp,xk,yk:real;var l:real);
begin
l:=sqrt(sqr(xp-xk)+sqr(yp-yk));
end;

procedure pl(a,b,c:real; var s:real);
var p:real;
begin
p:=(a+b+c)/2;
s:=sqrt(p*(p-a)*(p-b)*(p-c));
end;

begin
writeln(‘Введіть кількість вершин многокутника’);
readln(n);
writeln(‘Введіть координати вершин многокутника’);
for i:=1 to n do readln(xx[i],yy[i]);
writeln(‘Введіть координати точки’);
readln(x,y);
s_mn:=0;
for i:=1 to n-2 do begin
line(xx[i],yy[i],xx[i+1],yy[i+1],a1);
line(xx[i+1],yy[i+1],xx[i+2],yy[i+2],b1);
line(xx[i+2],yy[i+2],xx[i],yy[i],c1);
pl(a1,b1,c1,s1);
s_mn:=s_mn+s1;
end;
s_tr:=0;
xx[n+1]:=xx[1];
yy[n+1]:=yy[1];
for i:=1 to n do begin
line(xx[i],yy[i],xx[i+1],yy[i+1],a1);
line(xx[i],yy[i],x,y,b1);
line(xx[i+1],yy[i+1],x,y,c1);
pl(a1,b1,c1,s1);
s_mn:=s_mn+s1;
end;
if s_mn=s_tr then writeln(‘належить’) else writeln(‘не належить’);
end.

2) Для визначення положення точки відносно многокутника перевіряється той факт, що точка лежить по одну сторону від всіх ребер полігону. Якщо це не так, то вона зовні. В загальному випадку такий спосіб не працює.

Програмний код:
Program Prog 5;
var x,y:array[1..100] of real;
x0,y0:real;
i,n:integer;
b:Boolean;
begin
writeln(‘Введіть кількість вершин многокутника’);
readln(n);
writeln(‘Введіть координати вершин многокутника’);
for i:=1 to n do readln(x[i],y[i]);
writeln(‘Введіть координати точки’);
readln(x0,y0);
x[n+1]:=x[1];
y[n+1]:=y[1];