Алгоритм разбиения средней точкой

В предыдущем алгоритме требовалось вычислить пересечение отрезка со стороной окна. Можно избежать непосредственного вычисления, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой (рис. 12). Алгоритм, основанный на этой идее и являющийся частным случаем алгоритма Сазерленда-Коэна, был предложен Спруллом и Сазерлендом для аппаратной реализации.

В алгоритме используются коды концевых точек отрезка и

проверки, выявляющие полную видимость отрезков (о), и тривиально невидимых (/>). Те отрезки, которые с помощью таких простых проверок нельзя отнести к одной из двух категорий (с, g, f), разбиваются на две равные части. Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделенного отрезка не станет пренебрежимо малой, т.е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. В результате процесс обнаружения пересечения сводится к двоичному поиску. Данный алгоритм можно записать следующим образом.

Для каждой концевой точки отрезка:

- если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе - продолжить;

- если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе — продолжить;

- грубо оценить наиболее удаленную видимую точку путем деления отрезка Р\Р2 средней точкой Рт. Применить вышеизложенные тесты к двум частям Р\Рт и РтР2- Если P1P2 тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее

удаленной видимой точки. Продолжить процедуру с отрезком PiPm. Иначе - средняя точка дает оценку снизу для наиболее удаленной видимой точки. Продолжить процедуру с /W Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или предельно заданной точностью, то надо оценить её видимость и закончить процесс.

5.4. Обобщение: отсечение двумерного отрезка выпуклым окном

В описанных выше алгоритмах предполагалось, что отсекающее окно является координатно-ориентированным прямоугольником. Однако во многих случаях окно не таково. Кирус и Бек предложили алгоритм отсечения окном произвольной выпуклой формы.

Прежде чем описывать алгоритм Кируса-Бека рассмотрим отсечение параметрически заданного отрезка прямоугольным окном. Параметрическое уравнение отрезка P1P2 имеет вид:

где t - параметр. Параметрическое описание отрезка не зависит от выбора системы координат. Это свойство делает параметрическое представление особенно полезным для определения пересечения отрезка со стороной произвольного выпуклого многоугольника.

В двумерной декартовой системе координат уравнение (I) сводится к паре одномерных параметрических уравнений вида:

В случае прямоугольного отсекающего окна одна из координат пересечения отрезка с каждой стороной известна. Необходимо вычислить только вторую координату. Из уравнения (1) получаем:

t=(P(t}-P1)/(P2-P1).

А из уравнения (2) следует, что значения (, соответствующие пересечениям со сторонами окна, равны:

Здесь через хп, х„, у„, уш обозначены координаты левой, правой, нижней и верхней Сторон окна. Если решения этих уравнений дают значение / за пределами интервала 0< =t< =1, то такие решения отбрасываются, поскольку они соответствуют точкам, лежащим вне заданного отрезка.