У загальному випадку розміщення (рис. 1.11) при заданих координатах центрів і радіусах знаходимо міжцентрову відстань
(1.44)
та компонент повороту локальної системи з початком у центрі першого кола й віссю 0'х’, що збігається з 01 02, відносно глобальної системи хОу :
t=f(x,y). (1.45)
Далі знаходимо xn1,2, yn1,2 за формулами (1.43) у локальній системі та зводимо результат до глобальної системи, враховуючи, що х1=х0, у0=у1, a=t.
Задача спряження двох кіл третім
Задача спряження двох кіл третім зводиться до побудови кола, дотичного до двох заданих кіл. При цьому радіус шуканого кола задано, а треба знайти його центр і точки спряження.
Розв'язати цю задачу креслярськими приладами нескладно. Певні труднощі виникають при розробці програмного розв'язування цієї задачі засобами комп'ютерної графіки.
Загальна вимога до програмного забезпечення розв'язування будь-якої задачі — включати аналіз сумісності поставлених умов. Це означає, що перш ніж застосувати алгоритм розв'язку, треба визначити, яким умовам мають відповідати вхідні дані.
У задачі спряження формулювання умов сумісності вхідних даних та складання алгоритму розв'язування виникають труднощі, спричинені багатоваріантністю.
Як відомо, дотик двох кіл може бути зовнішнім або внутрішнім. У загальному випадку існує чотири варіанти дотику шуканого кола з двома заданими. Ці варіанти формалізуються наданням знака "-" чи "+" радіусам заданих кіл. Якщо дотик відповідного кола і шуканого с зовнішнім, то його радіус від'ємний, а якщо внутрішнім, то додатний.
Ще два варіанти, що відрізняються розміщенням центра шуканого кола відносно лінії центрів заданих кіл, формалізуємо наданням знака радіусу спряжувального кола. Якщо центри О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.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 ланок ВС та TL, а також точку перетину V ланок СD та LW. Ці точки, по-перше, обмежують видимі частини ланок TL та LW, а по-друге, їх включають як вузлові в екран STUCVWRK, за допомогою якого визначатимуть видимість наступної лінії рівня.
Випробування точок та відрізків на належність екрану в межах цієї задачі можна спростити порівняно з попереднім алгоритмом. а саме:
вузли ліній рівня слід брати на однакових інтервалах, тобто 1-2=2-3=... =5-6;
належність точок до екрана визначають порівнянням координат відповідних вузлів, наприклад yL< уC, тому вузол L- екранується:
якщо на деякому інтервалі з'являється додатний вузол, наприклад вузол U на інтервалі 2-3, то відповідну ланку при наступному екрануванні треба випробовувати
не тільки на порівняння ординати у на межах інтервалу, а й на перетин з двома
підданками TU та UС.
Площа та координати центра ваги плоскої фігури
Як відомо, площу елементарної фігури, обмеженої графіком у = f(x), віссю Ох та прямими x=c, x=d, визначають як
. (1.79)
Координати центра ваги елементарної фігури:
(1.80)
де
- (1.81)
статичний момент площі елементарної фігури відносно осі 0x;
(1.82)
статичний момент площі елементарної фігури відносно осі Оу.
У формулах (1.79), (1.81) і (1.82) верхній знак відповідає f(x) > 0, a нижній -
f(x) < 0.
За умов розглядуваної задачі під плоскою фігурою розуміють плоску область, обмежену замкненими контурами, що не перетинаються між собою. Кожний контур є замкненою ламаною. Якщо деякі з контурів криволінійні, то вони заздалегідь з достатньою точністю апроксимуються ламаними.
Вважатимемо, що вузли р контурів, які обмежують область, визначаються масивами координат хij, yij (i=1,2,…, mi; j=1,2,.., p) та умовами замкненості x1j= xmj, y1j=ymj. Отже, кожний контур містить nj=mj-1 вузлів , які не збігаються. Нехай також вузли обмежувальних контурів упорядковані так, що матеріальна площа лежить справа від напряму впорядкування.
Тоді згідно з означенням плоскої фігури та прийнятими домовленостями знак перед правими частинами виразів (1.79), (1.81) і (1.82) можна опустити. Елементарною фігурою буде трапеція, а підінтегральною функцією — лінійна функція.