Якщо ж поділ дає різноманітні задачі, метод виділення під цілей.

Наприклад. Обчислення площі п-кутника, що заданий координатами вершин.

П-кутник розбивається діагоналями на п-2 трикутники.

Зауваження. В розглянутому прикладі діагоналі проводяться з однієї вершини. Якщо многокутник опуклий, то вибір такої вершини для поділу на трикутники є довільним. У випадку не опуклого п-кутника в якості вершини поділу вибирається не опукла вершина. Якщо таких вершин буде декілька, то за методом РІВ п-кутник поділяється на к- та т-кутники між двома не опуклими вершинами.

Для перевірки не опуклості вершин можна скористатися одним з двох способів:

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

Якщо підстановка замість вільних змінних по у та х координати решти вершин даватиме один і той же знак, то відповідна вершина буде опуклою.

<== попередня сторінка	\|	наступна сторінка ==>
Тема: Методи розробки алгоритмів і програм.	\|	Сортування масиву. Розділення його на частини, по окремим впорядкуванням їх та наступним злиттям частин.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.