4.3.2. Алгоритм Сазерленда - Ходгмана

За допомогою цього алгоритму можна виконати вирізання будь-яким багатокутником (опуклим чи ні). Для застосування цього алгоритму треба мати багатокутник з вершинами і опукле додатно визначене вікно зі сторонами . Виберемо одну з граней вікна, наприклад Ε (з вершинами ΑΒ), а потім повторимо цей процес для всіх меж вікна. Дослідимо розташування кожної зі сторін відносно Ε так. Нехай є стороною, яку досліджуємо:

якщо , є ліворуч від ΑΒ записуємо в список вихідних даних вершину (рис. 4.25,а)

а б

Рис. 4.25. Сторони , розташовані по один бік від ΑΒ

якщо і праворуч, то нічого не заносимо у список (рис.4.26,б);

а) б)

Рис.4. 26. Сторони , розташовані по різні боки від ΑΒ

якщо є ліворуч, а праворуч, то обчислюють точку перетину Ι, яку вводять у список вихідних даних (рис.4.26,а).
якщо праворуч, а ліворуч, то обчислюють точку перетину Ι. В список вихідних даних уводять точки Ι і (рис.4.26.б).

Алгоритм повторюють для кожного боук вікна вирізання з урахуванням кожного разу багатокутника з попереднього кроку.

4.3.3. Алгоритми Сазерленда-Ходгмана вирізання поверхонь

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

Рис. 4.27. Вирізання багатокутником

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

список сторін поверхні, які маємо намір вирізати;

лінії, згідно з якими відбуватиметься вирізання.

На кожному кроці вирізання відбувається два процеси.

1. Для кожної досліджують чи вона видима відносно лінії. Видимі точки заносяться в список вихідних даних.

2. Одночасно досліджується, чи точка є по той самий бік, що і точка . Якщо ні, то обчислюється точка перетину відрізка зі стороною e, і ця точка також з аноситься в список вихідних даних.