Рис. 7.12. Рассечение многоугольника общего вида Модуль отсечения отрезка можно рассматривать как "черный ящик", на вход которого подаются две пары координат конечных точек исходного отрезка, а на выходе формируются две пары координат конечных точек того участка этого отрезка, который лежит внутри зоны отсечения, или не формируется ничего, если отрезок не пересекает зону отсечения.
а) б)
Рис. 7.13. Отсечение отрезка"images/tmpB6CA-299.png" alt="Отсечение верхней границей рамки">
Рис 7.14. Отсечение верхней границей рамки: а - геометрия; б - модуль, реализующий операцию
Рассмотрим отсечение верхней границей рамки. Модуль, выполняющий эту операцию, получает на входе координаты крайних точек отрезка и значение утгх в качестве параметра, задающего зону отсечения (рис. 7.14). Нетрудно показать, используя подобие треугольников
7.4. Отсечение многоугольников на рис. 7.15, что если отрезок пересекает границу, то координаты точек пересечения определяются уравнениями
В результате модуль отсечения вернет одну из трех пар координат: {(хиу}),(х2,у2)}, {(хиУїЦхьУпк)} или {(хг,утах),(х2,у2)}. По этой же схеме организуются и модули отсечения нижней, правой и левой границами рамки, только в соответствующих уравнениях используются другие параметры рамки, а координаты хиу могут меняться ролями. Каждый модуль работает независимо, но целесообразнее организовать из них конвейер (рис. 7.16). Такой конвейер, реализованный аппаратно, будет корректно обрабатывать четыре вершины. На рис. 7.17 показано, как с помощью такого аппаратного модуля реализуется отсечение многоугольника.
Рис. 7.15. Пересечение отрезка с верхней границей рамки
Рис. 7.16. Объединение отдельных модулей в конвейер: а- геометрический смысл операции; б - структура конвейера