Постановка задачі.
Відсікання відрізка на площині прямокутним вікном
Тепер, якщо деякий біт включений і для початку і для кінця відрізка, то відрізок повністю лежить поза області, інакше частина відрізка лежить в області, і треба перерахувати координати кінців. Але даний алгоритм можна застосувати тільки в тих випадках, коли сторони прямокутного вікна паралельні осям координат. Потрібно реалізувати алгоритм та побудувати видиму частину відрізка. Більшість… Читати ще >
Постановка задачі. Відсікання відрізка на площині прямокутним вікном (реферат, курсова, диплом, контрольна)
Нехай дані координати кінців відрізка (x1, y1) і (x2, y2). А також дані координати верхній лівій вершини прямокутного вікна (TopLeftX, TopLeftY) і координати нижньої правої вершини (BottomRightX, BottomRightY). Необхідно визначити місце розташування відрізка щодо прямокутного вікна.
Якщо відрізок знаходиться цілком усередині прямокутної області, то він будується без змін. Якщо відрізок цілком знаходиться поза розглянутого прямокутного вікна, то він не будується. Якщо ж відрізок частково лежить у вікні, то необхідно знайти точки перетину відрізка з гранями прямокутника, використовуючи для цього рівнянь прямої:
(X — x1) / (x2 — x1) = (y — y1) / (y2 — y1) (1.1).
Потрібно реалізувати алгоритм та побудувати видиму частину відрізка.
Опис алгоритму Сазерленда-Коена
Часто виникає необхідність відсікти виведене зображення по межі області, область зазвичай має вигляд прямокутника. Розглянемо алгоритм Сазерленда-Коена. Даний алгоритм дозволяє для деякого відрізка заданого координатами початку і кінця ((x1, y1), (x2, y2)), і деякою прямокутної області, визначити координати початку і кінця частини відрізка лежить всередині області.
Алгоритм розділяє площину на 9 частин, і кожній з них ставить у відповідність 4-х бітний код наступним чином: включений біт 0 означає, що точка лежить лівіше прямокутника, включений біт 1 означає, що точка лежить правіше прямокутника, включений біт 2 означає, що точка лежить вище прямокутника, включений біт 3 означає, що точка лежить нижче прямокутника, Таким чином, отримуємо наступне схематичне зображення (див. рис. 1.2).
Тепер, якщо деякий біт включений і для початку і для кінця відрізка, то відрізок повністю лежить поза області, інакше частина відрізка лежить в області, і треба перерахувати координати кінців.
Цей алгоритм дозволяє швидко виявити відрізки, які можуть бути або прийняті або відкинуті цілком. Обчислення перетинів вимагається коли відрізок не потрапляє в один з цих класів. Цей алгоритм особливо ефективний в двох крайніх випадках:
більшість примітивів міститься цілком в великому вікні,.
більшість примітивів лежить цілком поза відносно маленького вікна.
Але даний алгоритм можна застосувати тільки в тих випадках, коли сторони прямокутного вікна паралельні осям координат.