REFERATUA.ORG.UA — База українських рефератів




треба визначити, яким умовам мають відповідати вхідні дані.

У задачі спряження формулювання умов сумісності вхідних даних та складання алгоритму розв'язування виникають труднощі, спричинені багатоваріантністю.

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

Ще два варіанти, що відрізняються розміщенням центра шуканого кола відносно лінії центрів заданих кіл, формалізуємо наданням знака радіусу спряжувального кола. Якщо центри О1 і О2 заданих кіл не збігаються, то радіус спряжувального кола додатний, коли його центр лежить зліва, та від'ємний, коли його центр лежить справа від вектора 0102.

Центр спряжувального кола, його радіус і точки спряження ще не однозначно визначають кутовий параметр спряжувальноЇ дуги. Точки дотику поділяють спряжувальне коло на дві дуги, сума яких дорівнює 2п. Отже значенням коефіцієнта k можна поставити у відповідність кожну з двох дуг спряжувального кола. Наприклад, значенню k = 0 відповідає менша дуга, k = 1 — більша.

Алгоритм розв'язання в цілому наводимо з урахуванням прийнятої формалізації.

Вхідні дані: x1, y1 i R1 - координати центра О1 і радіус першого кола; x2, y2 i R2 — координати центра і радіус другого кола, R — радіус спряжувального кола; k - коефіцієнт вибору спряжупальної дуги.

Вихідні дані: xc, yc - координати центра спряжувальноЇ дуги; tп — кутовий параметр початкової точки спряжувальної дуги; tд — кутовий параметр спряжувальної дуги.

Обчислення міжцентрової відстані:

Комп'ютерна графіка (1.46)

Нехай

Комп'ютерна графіка. (1.47)

Перевірка сумісності умов. Задача має розв'язок, якщо:

Комп'ютерна графіка, (1.48)

або

Комп'ютерна графіка, (1.49)

або

Комп'ютерна графіка (1.50)

або

Комп'ютерна графіка (1.51)

За допомогою алгоритму визначення координат точок перетину двох кіл, радіуси яких ||R|-R1| тa ||R|-R2| (див. коло), знаходять у локальній системі з початком у О1 та віссю О'х', що збігається з 0102 (рис. 1.12),

Комп'ютерна графіка (1.52)

Комп'ютерна графіка

Координати точки контакту спряжувального кола з першим колом:

Комп'ютерна графіка (1.53)

Координати точки спряження з другим колом:

Комп'ютерна графіка (1.54)

Співвідношення (1.53) та (1.54) дістали з розрахунку подібних трикутників.

Визначення компонент повороту локальної системи x'О'у' відносно глобальної xOy :

Комп'ютерна графіка. (1.55)

Рис.1.12


Обчислення глобальних координат центра спряжувального кола та координати точок спряження за формулами :

Комп'ютерна графіка (1.56)

Обчислення кутового параметра точок спряження відносно центра спряжувального кола:

Комп'ютерна графіка. (1.55)

Ви'значення кутового параметра спряжувальної дуги:

Комп'ютерна графіка. (1.58)

Якщо k = 0 і |t| > п або k = 1 і |t[ < л, то

Комп'ютерна графіка.

Екстремальні випадки задачі спряження

Під екстремальними розуміють випадки. коли деякі вхідні дані досягають екстремальних значень. Так, наведений вище алгоритм повною мірою можна застосовувати в екстремальних випадках, коли R1 = О або R2= 0. При цьому задача зводиться до знаходження кола заданого радіуса, яке проходить через фіксовану точку та дотикається до другого кола. Цей алгоритм застосовують також тоді, коли одночасно R1= О та R2=0. Тут йдеться про знаходження кола заданого радіуса, яке проходить через дві фіксовані точки.

Випадок, коли радіус спряжувального кола дорівнює нулю, тривіальний. Розглядуваний алгоритм до формуй (1.52) включно збігається з алгоритмом знаходження координат точок перетину двох кіл, а формули (1.53)...(1.58) втрачають зміст.

Розглянемо випадки, коли радіус спряжувального кола R досягає екстремальних значень, що дістанемо виразів (1.47) ... (1.51) при зміні в них знаків нерівності на знаки рівності, тобто R = А та R = В. Тут радіус спряжувaльного кола перетворюється в залежну величину, яка не може входити у вхідні дані.

Знаходження координат центра спряжувальиого кола, що грунтувалaся на алгоритмі визначення координат точок перетину двох кіл, також не може бути здійснений у такому вигляді через перетворення перетину до дотику. Комп'ютерний розв'язок у цьому екстремальному випадку привів би до визначення комп'ютерного нуля, що, в свою чергу, призвело б до значних ускладнень програми. У зв'язку з цим наведений екстремальний випадок вимагає окремого алгоритму та суттєвих змін навіть при формулюванні задачі, а саме: знайти коло екстремально дотичне до двох заданих кіл.

Неважко показати, що центр шуканого кола та точки його спряження з заданими колами лежать на лінії їхніх центрів. Тому, не змінюючи умови формалізації щодо знаків R1та R2, накладемо нову умову на коефіцієнт k: при k = 1 спряжувальна дуга розміщена зліва, а при k = -1 справа від вектора Комп'ютерна графіка.

Нарешті, варіант екстремального значення радіуса спряжувального кола формaлізуємо за допомогою коефіцієнта р, при р == 1 маємо R = А,

а при р = -1 — R = В.

Алгоритми нерухомого та рухомого екранів

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

Екранування замкненим багатокутником (нерухомим екраном). Нехай n-кутник задано масивами координат його вершин xi, yi, (i = 1.2. .... m) так, що вершини впорядковані в напрямі проти руxу стрілки годинника, а x1 = xm, y1= уm. Щоб визначити належність точки M (Xо, Yо) до внутрішності n-кутника, обчислимо суму кутів між суміжними променями, що сполучають точку М з вершинами n-кутннка. Маємо

Комп'ютерна графіка (1.76)

Цю формулу дістали, застосувавши формулу площі трикутника з вершинами (х0,у0), (хі,уі), (хі+1,уі+1), а саме:

Комп'ютерна графіка (1.77)

де знак "+" відповідаг впорядкуванню вершин у напрямі проти руху стрілки годинника.

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

Нехай на площину х0у проекціюються лінії рівня деякої поверхні (рис. 1.13). АВСDЕF— найближча лінія, видима всіма своїми вузлами та ланками. Наступну лінію рівня STLWRK екрануємо попередньою лінією. Вузол L лежить у зоні екрана. 3най-демо точку перетину U


 
Загрузка...