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

АННОТАЦИЯ.

У курсовому проекті вирішується завдання обчислення площі довільного багатокутника итерационным алгоритмом.

ЗАДАНИЕ.

Багатокутник (необов'язково опуклий) заданий на площині перетином координат вершин гаразд обходу його меж. Визначити площа многоугольника.

Аннотация.

Завдання виконання курсового проекта.

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; і: 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.