12. Двумерное отсечение. Простой алгоритм отсечения отрезка.

Отсечение – удаление изображение за пределами выделенной области.

Для отсечения необходимо знать:

1. Геометрические характеристики отсекаемых объектов
2. Геометрические характеристики отсекателя

Регулярным (стандартным) отсекателем на плоскости является прямоугольник со сторонами, параллельными координатным осям объектного пространства или экрана. Такое окно задается левым, правым, верхним и нижним двумерными ребрами.

Видимый объект - объект, целиком лежащий в области. Невидимый объект - объект, не лежащий в области. Частично видимый объект - объект, частично лежащий в пределах отсекателя.

Алгоритм

1. Ввод координат отсекателя Xл, Xпр, Yн, Yв
2. Ввод координат концов отрезка P1(X1,Y1), P2(X2,Y2)
3. Вычисление кодов концов отрезка T1, T2. Вычисление сумм кодов концов отрезка S1, S2
4. Установка признака видимости отрезка pr=1 (pr=1 - отрезок видимый; pr=-1 - отрезок невидимый)
5. Задание начального значения тангенса угла наклона отрезка m=... (большое число, предполагается, что отрезок вертикальный)
6. Проверка полной видимости отрезка:
   • если (S1=0)&(S2=0)=true, то отрезок видимый
   • занесение в результат координат концов отрезка R1=P1, R2=P2 и переход к п. 31
7. Вычисление логического произведения кодов концов отрезка P
8. Проверка тривиальной невидимости отрезка:
   • если P=0, то отрезок невидим. В этом случае установка признака pr=-1 и переход к п. 31
9. Проверка видимости первого конца отрезка:
   • если S1=0 (первый конец видим), то выполнение следующих действий: R1=P1 (занесение этой вершины в результат), Q=P2 (занесение координат другой вершины в рабочую переменную Q), i=2 (номер шага отсечения), переход к п.15
10. Проверка видимости второго конца отрезка:
    • если S2=0 (первый конец видим), то выполнение следующих действий: R1=P2 (занесение этой вершины в результат), Q=P1 (занесение координат другой вершины в рабочую переменную Q), i=2 (номер шага отсечения), переход к п.15
11. Установка начального значения шага отсечения i=0
12. Вычисление текущего номера шага отсечения i=i+1
13. Проверка завершения процедуры отсечения:
    • если i>2, то переход к п.31
14. Занесение в рабочую переменную Q координат i-ой вершины Q=Pi
15. Определение расположения отрезка:
    • если X2=X1 (отрезок вертикальный), то переход к п.23 (не может быть пересечения с левой и правой границами отсекателя)
16. Вычисление тангенса угла наклона отрезка m=(Y2-Y1)/(X2-X1)
17. Проверка возможности пересечения с левой границей отсекателя:
    • если Qx>Xл (пересечения нет),то переход к п.20
18. Вычисление ординаты точки пересечения отрезка с левой границей отсекателя: Yр=m(Xл-Qx)+Qy
19. Проверка корректности найденного пересечения:
    • если (Yр>Yн)&(Yр<Yв)=true (пересечение корректное), то выполнение следующих действий: Ri.x=Xл, Ri.y=Yр (занесение полученных координат в результат), переход к п.12
20. Проверка возможности пересечения отрезка с правой границей отсекателя:
    • если Q.x<Xп (пересечения нет), то переход к п.23.
21. Вычисление ординаты точки пересечения с правой границей: Yр=m(Xп-Q.x)+Q.y
22. Проверка корректности найденного пересечения:
    • если (Yр>Yн)&(Yр<Yв)=true (пересечение корректно), то выполнение следующих действий : Ri.x=Xп, Ri.y=Yр (занесение полученных координат в результат), переход к п.12
23. Проверка горизонтальности отрезка:
    • если m=0, то переход к п.12
24. Проверка возможности пересечения с верхней границей отсекателя:
    • если Q.y<Yв (пересечения нет), то переход к п.27
25. Вычисление абсциссы точки пересечения с верхней границей: Xр=(Yв-Q.y)/m+Q.x
26. Проверка корректности найденного пересечения:
    • если (Xр>Xл)&(Xр<Xп)=true (пересечение корректно), то выполнение следующих действий: Ri.x=Xр; Riy=Yв (занесение полученных координат в результат); переход к п. 12
27. Проверка возможности пересечения с нижней границей отсекателя:
    • если Q.x>Yн (пересечения нет), то переход к п. 30 (вершина невидима и ни одно пересечение не является корректным, следовательно отрезок невидим)
28. Вычисление абсциссы точки пересечения с нижней границей: Xр=(Yн-Q.y)/m+Q.x
29. Проверка корректности найденного пересечения:
    • если (Xр>Xл)&(Xр<Xп)=true (пересечение корректно), то выполнение следующих действий: Ri.x=Xр; Riy=Yн (занесение полученных координат в результат); переход к п. 12
30. Установка признака видимости pr=-1 (отрезок невидим полностью, так как ни одно пересечение не оказалось корректным)
31. Проверка признака видимости:
    • если pr=1, то вычерчивание отрезка R1R2
32. Конец