Алгоритм Сазерленда-Коэна

Для ускорения отсечение предлагается ввести коды для точек отрезка (YmaxYminXmaxXmin). Затем, если логическое «И» над кодами отрезка не равно нулю, то отрезок полностью невидим. Если оба кода (логическое «ИЛИ») равны 0 то отрезок полностью внутри окна, иначе – нужно отсекать по тем сторонам, для которых биты логического «ИЛИ» кодов единичные. При получении очередной точки для нее считается код и история повторяется.

Алгоритм Кируса-Бэка

Наиболее распространенный алгоритм, подходит для выпуклого окна произвольной конфигурации. Отрезок отсекают последовательно по всем сторонам окна. Для точек отрезка находят расстояние до прямой, если оба положительные, то отрезок полностью невидим, если оба отрицательные, то он не пересекается с этой прямой, иначе – нужно найти точку пересечения, коэффициент k=d1/(d1-d2). P=A+k*(B-A).

Коэффициент k получается из подобия треугольников. , , ,

Невыпуклые окна разбивают на выпуклые и производят отсечение по ним.

Но можно и не вычислять точки пересечения при каждом пересечении. Достаточно только вычислить значение параметра, в котором происходит пересечение (k) и укорачивать интервал, который соответствует части отрезка, находящейся внутри окна. В начале этот интервал k1=0, k2=1, затем при пересечении в точке k, модифицируется коэффициент, соответствующий той точке, которая лежит вне окна (di>0) либо k1=max(k1,k), либо k2=min(k2,k). Если после пересечения окажется, что k1>k2, значит, отрезок находится полностью вне окна. После того, как обработаны все границы окна – следует рассчитать точки для k1,k2. Экономим на расчете точек, теряем на лишних расчетах коэффициентов пересечения.