Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Двомірний FC-алгоритм
Схема кодування подібна до тої, що використовується в алгоритмі Коена-Сазерленда (рис. 2). Простір поділяється на 9 областей, що перекриваються і пронумеровані арабськими цифрами від 1 до 9. Коди, які назначені кінцям відрізків, що потрапили в ту чи іншу область, приведені в двійковому і шістнадцятковому вигляді (запис вигляду 0xD).
Рис. 2. Завдання кодів для FC-алгоритму
Відрізок видимий тільки в області 5, тобто відрізок, координати якого задовольняють умовам:
Кожна кінцева точка відрізку V0V1 буде знаходитися в цих областях. Комбінація кодів кінців відрізка, називається кодом лінії, і використовується для визначення можливих варіантів розміщення відрізку і його відсікання. Код лінії формується з кодів кінця відрізка наступним чином:
де Code(V1) означає код кінцевої точки V1, Code(V0) × 16 означає зсув коду початкової точки V0 вліво на 4 розряди.
Так як кожний код може приймати одно з 9 значень, то всього є 81 можливий варіантів розміщення відрізка. Але, якщо Code(V0) рівний Code(V1), то LineCode(V0,V1) рівний LineCode(V1,V0). Є всього 9 таких випадків: 1-1, 2-2, ¼ 9-9. Звідси слідує, що число різних випадків зменшується до 72.
Кожний LineCode вимагає свого набору обчислень для визначення відсікання відрізка за мінімальний час. Всього є 8 основних випадків відсікання, а інші симетричні до них.
Рис. 4. Випадок кутових областей
Головна різниця FC-алгоритму від алгоритмц Коена-Сазерленда полягає у впорядкуванні дій по відсіканню. Ефективність алгоритму Коена-Сазерленда обмежується послідовним характером і фіксованим порядком дій по відсіканню. Як приклад (див. рис. 4) відрізок RW буде відсікатися в порядку: зверху, знизу, праворуч і зліва. Число ж відсікань для визначення видимості рівно 2 - знизу і зліва. В FC-алгоритмі, напроти, для кожного значення LineCode є свій набір дій по відсіканню. Для приведеного вище прикладу необхідно тільки одне відсікання для визначення невидимості відрізка RW. Крім того, підвищення ефективності FC-алгоритму в порівнянні з CS-алгоритмом відповідає відсутності непотрібних циклів і переобчислень кодів кінцевих точок.