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

При реализации программно, работает медленнее простого. Аппаратно – быстрее в sqrt(2).

1. Ввод координат отсекателя Xл, Xп, Yн, Yв.
2. Ввод координат концов отрезка P1(X1,Y1), P2(X 2,Y 2).
3. Ввод точности ε вычисления точки пересечения отрезка с границей отсекателя.
4. Установка номера шага отсечения i=1.
5. Вычисление кодов концевых точек и запись их в соответствующие массивы T1 и T2 размерностью 1х 4, вычисление сумм кодов концов S1 S2
6. Проверка полной видимости отрезка. Если коды обоих концов отрезка равны нулю (полная видимость отрезка), то переход к п. 9.
7. Проверка полной невидимости отрезка. Вычисление побитного логического произведения кодов концевых точек отрезка. Если произведение отлично от нуля (отрезок невидим), то переход к п. 10.
8. Анализ частично видимого отрезка в том случае, если побитовое логическое произведение кодов его концов равно нулю:
   8.1. Поиск наиболее удаленной от P1 видимой точки S исследуемого отрезка. Запоминание исходной точки P1 в промежуточной переменной R.
   8.2. Проверка на окончание процесса решения: если i>2, то определение логического произведения pr кодов концов отрезка. Если pr≠0, то переход к п.10, иначе переход к п.9.
   
   8.3. Проверка точки P2 на наиболее удаленную от P1 видимую точку отрезка. Если сумма всех элементов массива T2 равна нулю (S2), то переход к пункту 8.12.
   8.4. Проверка нахождения точки пересечения отрезка с границами отсекателя. Если  P1- P2≤ε (расстояние между концевыми точками исследуемого отрезка меньше допустимой погрешности), то переход к пункту 8.12.
   8.5. Вычисление средней точки Pср. отрезка: Pср. = (P1 + P2 )/2 (Pср.x = (P1.x + P2..x )/2 ; Pср.y = (P1.y + P2.y )/2).
   8.6. Запоминание текущей точки P1: Pm=P1.
   8.7. Замена точки P1 на среднюю точку: P1= Pср .
   8.8. Вычисление нового кода T1 точки P1.
   8.9. Вычисление произведения pr кодов концов нового отрезка P1P2.
   8.10.Проверка полной невидимости отрезка P1P2. Если побитовое логическое произведение pr кодов концевых точек равно нулю, то переход к пункту 8.4. В противном случае отрезок P1P2 невидим.
   8.11. Возврат к предыдущему отрезку P1P2 : P1 = Pm, = Pср , переход к пункту 8.4. ( Вычислена наиболее удаленная от точки P1 видимая точка отрезка).
   8.12..Поиск наиболее удаленной от P2 видимой точки отрезка. Замена мест точек P1 и P2 : P1 = P2 , P2=R. Увеличение шага выполнения отсечения i=i+1. Переход к п.5.
   
9. Визуализация отрезка. 10.Конец. При программной реализации алгоритма целесообразно для вычисления кодов концевых точек отрезков и их логических произведений использовать отдельные функции.