Отсечение плоских фигур (алгоритм Коэна-Сазерленда)

Предварительно необходимо договориться о направлении обхода вершин (по часовой стрелке или против неё). Фигура должна быть замкнутой.

Последовательно производят отсечение многоугольника по четырём границам.

.

Анализ ребер: возможно 4 варианта расположения ребра в пространстве:

Может также возникнуть вариант, когда ребро совпадает с границей.

В случае 1: Добавить в список рисуемых вершин Р;

2: Добавить в список Q;

3: Ничего не добавляется;

4: Добавить в список Р,Q;

Пример: многоугольник задан списком вершин {1,2,3,4,5,6,7,1}

Последовательно переберём все рёбра. Начнем процесс с точки 1 и ребра 1-2. Начнём формировать новый список вершин. В соответствии с ориентацией ребра занесём в выходной список вершину 2 => {2}. Далее рассмотрим ребро 2-3: добавляется точка 8 => {2, 8}

3-4: {2, 8, 9, 4}.

4-5: {2, 8, 9, 4, 10}.

5-6: {2, 8, 9, 4, 10}. Ребро полностью оказалось вне, поэтому ничего не добавляется.

6-7: {2, 8, 9, 4, 10, 11, 7}.

7-1: {2, 8, 9, 4, 10, 11, 7, 1}.

Таким образом, новый список вершин: {2, 8, 9, 4, 10, 11, 7, 1}.

Определение яркости в точке пересечения с областью вывода.

Вычисления проводятся по одной из двух формул:

(1)

(2)

Примечание:

По формуле (1) считают, если |у₂ – у₁| ³ |х₂ – х₁|, по формуле (2) - если

|у₂ – у₁| < |х₂ – х₁|;