АНОТАЦІЯ
У курсовому проекті вирішується завдання обчислення площі довільногобагатокутника ітераційним алгоритмом.
ЗАВДАННЯ.
Багатокутник (не обов'язково опуклий) задано на площиніперетином координат вершин в порядку обходу її меж. Визначитиплоща багатокутника.
ЗМІСТ
Анотація
Завдання на виконання курсового проекту
Зміст
Введення
1 Розробка програмної реалізації
2 Перевірка на контрольних прикладах
3 Висновок
Додаток 1. Блок-схема.
Додаток 2. Програма.
ВСТУП
Системи, подібні представленої, часто можна зустріти в повсякденномужиття.
Дана задача не має аналітичного рішення. В геометрії існуютьформули, що дозволяють обчислювати площі правильних багатокутників, але длядовільних багатокутників таких формул немає. Рішення задачі можнаотримати чисельними методами. Розглянемо два з них.
1. Площа довільної фігури можна обчислити методом Монте-Карло.
Фігура вписується в іншу фігуру з відомою площею. Випадково на останню ставляться довільну кількість точок. Площа визначається за формулою, де 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
