Відсікання опуклим багатокутником

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

Розглянемо завдання про перетинання відрізка з кінцями з опуклим багатокутником, заданим списком ребер. Ребро може бути задане у вигляді пари крапок з безлічі вершин багатокутника (мал. 7.7). Та обставина, що багатокутник опуклий, є дуже істотним: це дозволяє використовувати досить простий алгоритм, що використовує внутрішні нормалі до його сторін. Під внутрішньою нормаллю розуміється вектор, перпендикулярний стороні й спрямований усередину багатокутника. Як і в попередньому алгоритмі, скористаємося параметричним рівнянням прямої, що проходить через кінці відрізка: . Якщо при деякому значенні параметра ця пряма перетинається із прямої, що проходить через крапки , то вектор, що з'єднує довільну крапку ребра із крапкою , буде перпендикулярний вектору нормалі. Отже, скалярний добуток векторів і буде дорівнює нулю. Звідси шляхом нескладних викладень одержуємо .

Рис. 7.7. Перетинання відрізка багатокутником

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

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

- крапок перетинання немає;

- існує одна крапка перетинання;

- існують дві крапки перетинання.

У кожному із цих варіантів для знаходження перетинання відрізка з вікном необхідно вміти визначати приналежність крапки опуклому багатокутнику. З мал. 7.7 видно, що якщо для будь-якої крапки , що належить багатокутнику (або його границі), і довільної крапки ребра побудувати вектор , то виконується умова , оскільки кут між векторами не може перевищувати 90°. Таким чином, якщо дана умова виконується для всіх ребер багатокутника, то крапка є внутрішньою.

Таким чином, алгоритм відсікання відрізка починається з аналізу розташування кінців відрізка стосовно вікна. Якщо обидві крапки лежать усередині вікна, то відрізок повністю видимий, і подальший пошук припиняється. Якщо тільки одна із крапок лежить усередині вікна, то має місце випадок II, і має бути знайти одну крапку перетинання. І, нарешті, якщо обидві крапки лежать поза вікном, то існують або дві крапки перетинання (відрізок перетинає дві границі вікна), або ні однієї (відрізок повністю не бачимо). Втім, дві крапки перетинання можуть збігатися (якщо відрізок проходить через вершину багатокутника), але цей випадок у додатковому аналізі не має потреби.

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