15.3. РАЗРЕЗАНИЕ ПРОИЗВОЛЬНОГО ОТРЕЗКА ПРЯМОЙ ПРОИЗВОЛЬНЫМ ПРАВИЛЬНЫМ ПРЯМОУГОЛЬНИКОМ

Рассмотрим частный случай алгоритма разрезания. Он возникает при когда соответствующий многоугольник представляет собой прямоугольник со сторонами, параллельными осям координат. Будем называть такой прямоугольник правильным Существуют достаточно простые способы определения расположения точек относительно вертикальных и горизонтальных прямых, ограничивающих прямоугольник. На рис. 15.2 участок 5 характеризует наблюдаемый фрагмент изображения (окно наблюдения). Если точки находятся на одном из участков, за исключением участка 5, либо на участках одной из групп (1, 4, 7), (1, 2, 3), (3, 6, 9) или (7, 8, 9), то отрезок не виден. Он становится виден, когда обе точки находятся на участке 5. Проблему видности отрезка следует тщательно изучить для всех вариантов расположения концевых точек.

Этот частный случай столь важен с практической точки зрения, что для него целесообразно написать специальный алгоритм разрезания — здесь он приводится в виде алгоритма 15.2. На шаге 1 проверяется, не лежит ли рассматриваемый сегмент целиком в одной из четырех групп, каждая из которых включает по три участка, как показано на рис. 15.2: (1, 4, 7), (3, 6, 9), (7, 8, 9), (1,2, 3). Если это так, то отрезок находится за пределами наблюдаемого фрагмента изображения и, следовательно, выполнение алгоритма можно прекратить. На шаге 2 проверяется соответствие разметки концевых точек допущению 14.1. Шаг 3 предназначен для обработки горизонтальной прямой (с учетом шагов За—Зв), а шаг 4 (с учетом шагов 4а и 4б) — для обработки вертикальной прямой. Шаги 5—11 предназначены для анализа общего случая. Шаги 1, 3 и 4 без всякого ущерба можно было опустить, однако это приведет к увеличению объема вычислений. Эти шаги позволяют быстро проанализировать случаи, в которых не требуется использования общего критерия пересечения. Таким образом, это пример ситуации, когда увеличение длины алгоритма приводит к уменьшению среднего времени его выполнения.

На шаге 5 определяется знак четырех вершин относительно рассматриваемой прямой. В частности, соответствует нижней

Рис. 152. Разрезание при помощи прямоугольника окна наблюдения

левой вершине вершине верхней правой вершине вершине Условие, проверяемое на шаге 7, выполняется, если прямая пересекает левую границу наблюдаемого фрагмента изображения. На шагах 76 и 1е определяются координаты точки пересечения, которые во всех последующих вычислениях используются в качестве координат концевой точки отрезка. Отметим, что условия, проверяемые на этих двух шагах, не могут выполняться одновременно. Если бы эти условия выполнялись одновременно (т. е. были бы меньше то алгоритм должен был бы закончиться после выполнения шага 1. Условие, проверяемое на шаге 8, выполняется, если прямая пересекает верхнюю границу наблюдаемого фрагмента изображения. На шаге 86 определяются координаты точки пересечения. Отметим, что в силу допущения 14.1 необходимо оценивать расположение только одной концевой точки. Условие, проверяемое на шаге 9, выполняется, если прямая пересекает правую границу наблюдаемого фрагмента изображения, а условие, проверяемое на шаге 10, выполняется, если прямая пересекает нижнюю границу наблюдаемого фрагмента изображения. На шагах 96, 9в и 106 определяются координаты точек пересечения, которые затем используются в качестве координат концевых точек.

Отметим, что лишь два из четырех условий, проверяемых на шагах 7—10, могут выполняться. Следовательно, выполнение алгоритма можно ускорить, прекратив применять тест знака после того, как приняло значение 2. Кроме того, следует отметить, что когда отрезок прямой целиком попадает в наблюдаемый фрагмент изображения, ни одно из условий 76, 7в, 86, 96, 9е и 106 не может выполняться и единственной нетривиальной операцией является шаг 5.

Алгоритм 15.2. Разрезание произвольного отрезка прямой произвольным правильным прямоугольником

Обозначения. Концевые точки прямой имеют координаты Прямоугольник определяется координатами и и Процедура (вычерчивание) обеспечивает воспроизведение изображения прямой, — вспомогательные величины, определенные на шаге 5.

(см. скан)

(см. скан)

(см. скан)