Глава 15. РАЗРЕЗАНИЕ МНОГОУГОЛЬНИКОВ
15.1. ВВЕДЕНИЕ
Термин «разрезание» используется для обозначения процесса установления того, пересекается ли прямая (либо многоугольник) с каким-либо многоугольником. Основная цель применения процедуры разрезания — выяснить, попадает ли некоторая совокупность объектов в определенное окно на экране дисплея. Следует подчеркнуть, что нельзя передавать функции разрезания дисплею по двум причинам. Во-первых, зона воспроизведения изображения может составлять лишь часть экрана дисплея (например, часть экрана может быть отведена для воспроизведения текста). Во-вторых, отсутствует формальный способ воспроизведения точек с недопустимыми координатами. Очень часто дисплей игнорирует старшие двоичные разряды, в результате чего изображение циклически переносится на экране с конца предыдущей строки в начало следующей. Таким образом, требуются алгоритмы, предназначенные для решения этой задачи.
Кроме того, разрезание используется для решения проблем видности. Чтобы определить, загораживает ли один объект другой, необходимо прежде установить, пересекаются ли они между собой. Третий способ применения процедуры разрезания, исследованный еще в очень незначительной степени, связан с разбиением невыпуклого многоугольника на выпуклые подмногоугольники. Такое разбиение может потребоваться не только в машинной графике (см. подразд. 14.4.3), но и в распознавании образов, где выпуклые подмножества многоугольника можно использовать в качестве непроизводных элементов для описания формы (очертаний) исходного многоугольника (см. разд. 15.7).
Результаты разд. 14.4 будут использованы для разработки ряда алгоритмов разрезания. В разд. 15.2 рассматривается разрезание отрезка прямой выпуклым многоугольником, а в разд. 15.3 дается решение этой задачи для одного практически важного случая: многоугольник представляет собой прямоугольник, стороны которого параллельны осям координат. Разрезанию произвольного многоугольника прямой посвящен разд. 15.4, а разрезанию многоугольника другим многоугольником — разд. 15.5. И, наконец, в разд. 15.6 исследуется проблема вычислительной эффективности решения некоторых геометрических задач.
