Использование алгоритма Сазерленда-Ходжмена для оценки степени покрытия территории учреждения камерами видеонаблюдения

Основная идея алгоритма Сазерленда — Ходжмена состоит в том, что отсечь многоугольник относительно одной прямой или плоскости относительно легко. В этом алгоритме исходный и каждый из промежуточных многоугольников отсекается последовательно относительно одной прямой. Работа алгоритма для прямоугольного окна показана на рисунке 2.8. Исходный многоугольник задается списком вершин Р₁, …, Р_n, который порождает список его ребер Р₁Р₂, P₂P₃, …, P_n-1P_n, P_nP₁. На рисунке 2.8 показано, что многоугольник сначала отсекается левой стороной окна, в результате чего получается промежуточная фигура. Затем алгоритм вновь отсекает эту фигуру верхней стороной окна. Получается вторая промежуточная фигура. Далее процесс отсечения продолжается с оставшимися сторонами окна. Этапы отсечения показаны на рисунке 2.8. Этот алгоритм способен отсекать любой многоугольник, выпуклый или невыпуклый, плоский или неплоский, относительно любого окна, являющегося выпуклым многоугольником. Порядок отсечения многоугольника разными сторонами окна непринципиален.

Результатом работы алгоритма является список вершин многоугольника, у которого все вершины лежат по видимую сторону от очередной отсекающей плоскости. Поскольку каждая сторона многоугольника отсекается независимо от других, то достаточно рассмотреть только возможные ситуации расположения одного отрезка относительно одной отсекающей плоскости. Будем рассматривать каждую точку Р из списка вершин многоугольника, за исключением первой, как конечную точку ребра, начальной точкой S которого является вершина, предшествующая Р в этом списке. Тогда возможны только четыре ситуации взаимного расположения ребра и отсекающей плоскости. Они показаны на рисунке 2.9.

Рисунок 2.8 — Последовательное отсечение многоугольника.

Результатом каждого сопоставления ребра многоугольника с отсекающей плоскостью будет занесение в список вершин результирующего многоугольника нуля, одной или двух вершин. Если рассматриваемое ребро полностью видимо, то результатом будет вершина Р. Заносить в результат начальную вершину S в этом случае не надо, так как если вершины рассматриваются поочередно, то S уже была конечной точкой предыдущего ребра и поэтому уже попала в результат. Если же ребро полностью невидимо, то результат не изменяется.

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

Для первой вершины многоугольника необходимо определить только факт ее видимости. Если вершина видима, то она попадает в результат и становится начальной точкой S. Если же вершина невидима, она тоже становится начальной точкой, но в результат не попадает.

Последнее ребро — P_nP₁ — следует рассмотреть особо. Это реализуется путем запоминания первой вершины многоугольника в F. Тогда последним ребром становится P_nF, и его можно обрабатывать точно так же, как и любое другое ребро.

Прежде чем описать алгоритм полностью, приведем два дополнительных соображения, касающихся определения видимости точки и определения пересечения ребра многоугольника с отсекающей плоскостью. Определение видимости точки эквивалентно определению той стороны границы отсекающей плоскости, по которую лежит эта точка. Если ребра отсекающего многоугольника обходятся по часовой стрелке, то его внутренность лежит по правую сторону от границы. При противоположном порядке обхода она лежит по левую сторону. Ранее рассматривались два метода определения положения (видимости) точки относительно ориентированного отрезка или плоскости. Первый сводится к определению знака скалярного произведения вектора нормали на вектор, начинающийся в произвольной точке на прямой или плоскости и заканчивающийся в пробной точке. Второй метод заключается в подстановке координат пробной точки в уравнение ориентированной прямой или плоскости. Последней метод является вариантом того, что предложено Сазерлендом и Ходжменом.

Третий метод определения видимости сводится к проверке знака координаты z у векторного произведения двух векторов, лежащих в одной плоскости. Пусть две точки Р₁ и Р₂ лежат на отсекающей плоскости, а Р₃ — это пробная точка. Эти три точки задают некую плоскость, на которой лежат два вектора Р₁Р₂ и Р₁Р₃. Если эту плоскость считать плоскостью ху, то у векторного произведения векторов Р₁Р₂Р₁Р₃ ненулевой будет только компонента z, равная (x₃-x₁)(y₂-y₁)-(y₃-y₁)(x₂-x₁). Если знак этой компоненты будет положительным, нулевым или отрицательным, то Р₃ будет лежать соответственно справа, на или слева от прямой Р₁Р₂.

Все эти методы реализуются особенно просто для случая прямоугольных отсекающих окон, стороны которых параллельны координатным осям.

Сазерленд и Ходжмен предложили новый метод формирования последовательности промежуточных многоугольников. В их алгоритме ребра многоугольника обрабатываются поочередно. А это значит, что можно использовать с минимальными изменениями прежние коды концевых точек ребер. Последняя вершина многоугольника обрабатывается особо. На рис. 3 приведена блок схема этого алгоритма. На рисунке 2.10а приведена процедура, применяемая к рядовой вершине, а процедура на рисунке 2.10б применима только к последней вершине многоугольника. Запись алгоритма, порождающего и запоминающего промежуточные многоугольники, приводится ниже.

А Б.

Рисунок 2.10 — Структурная схема алгоритма Сазерленда — Ходжмена.

Сазерленд и Ходжмен показали, как можно избежать порождения и запоминания вершин промежуточных многоугольников. Для этого вместо отсечения каждого ребра (вершины) многоугольника одной плоскостью, ограничивающей окно, надо отсекать каждое такое ребро (вершину) последовательно всеми границами окна. После отсечения очередного ребра (вершины) многоугольника по одной из границ окна, алгоритм рекурсивно обращается к самому себе, чтобы отсечь результат предыдущего обращения по следующей границе окна. Это свойство делает данный алгоритм более удобным для аппаратной реализации.

Алгоритм Сазерленда — Ходжмена для отсечения многоугольника Р — массив вершин исходного многоугольника.

Q — массив вершин результирующего многоугольника.

W — массив вершин отсекающего окна. Первая вершина повторяется в конце массива.

N_P — число вершин исходного многоугольника.

N_Q — число вершин результирующего многоугольника.

N_W — число вершин окна плюс единица вершины всех многоугольников перечисляются по часовой стрелке.

для каждой стороны окна выполнить:

for i = 1 to N_W — 1.

установить счетчик вершин результата и обнулить результат

N_Q = 0.

Q = 0.

отсечь каждое ребро многоугольника по данной стороне окна

for j = 1 to N_P

особо обработать первую вершину многоугольника

if j 1 then 1.

запомнить первую вершину

F = P_j

goto 2.

проверить факт пересечения ребром многоугольника стороны окна

1 call Факт—сеч (S, P_j, W_i, W_i+1; Признак).

if Признак = нет then 2.

если ребро пересекает сторону окна, вычислить точку пересечения

call Пересечение (S, P_j, W_i, W_i+1; Тсечения).

занести точку пересечения в результат

call Выход (Тсечения, N_Q, Q).

изменить начальную точку ребра многоугольника

2 S = P_j

проверить видимость конечной точки (теперь это S) ребра многоугольника

call Видимость (S, W_i, W_i+1; Sвидимость).

if Sвидимость < 0 then 3.

если точка видима, то занести ее в результат

call Выход (S, N_Q, Q).

3 next j.

обработать замыкающее ребро многоугольника если результат пуст, то перейти к следующей стороне окна

if N_Q = 0 then 4.

проверить факт пересечения последним ребром многоугольника стороны окна

call Факт—сеч (S, F, W_i, W_i+1; Признак).

if Признак = нет then 4.

факт пересечения установлен; вычислить точку пересечения

call Пересечение (S, F, W_i, W_i+1; Тсечения).

вывести точку пересечения в результат

call Выход (Тсечения, N_Q, Q).

Теперь многоугольник отсечен стороной W_iW_i+1 окна

Работа алгоритма возобновляется с результатом отсечения

4 Р = Q.

N_P = Q.

5 next i.

finish.

Подпрограмма определения факта пересечения ребра многоугольника со стороной окна.

subroutine Факт—сеч (Начало, Конец, W1, W2; Признак).

определить видимость начальной точки ребра многоугольника

call Видимость (Начало, W1, W2; Твидимость) Твидимость1 = Твидимость.

определить видимость конечной точки ребра многоугольника

call Видимость (Конец, W1, W2;Твидимость) Твидимость2 = Твидимость.

считается, что ребро многоугольника, которое начинается или заканчивается на стороне окна, не пересекается с ней.

Эта точка должна быть занесена в результат ранее

if Твидимость 0 or Твидимость1 > 0 and Твидимость2 < 0 then.

Признак = да.

else.

Признак = нет.

end if.

return.

Подпрограмма определения видимости точки.

subroutine Видимость (Точка, Р1, Р2; Твидимость).

видимость Точка следует определить относительно стороны Р₁Р₂

< 0, если Точка невидима Твидимость = 0, если Точка лежит на стороне Р₁Р₂

> 0, если Точка видима.

в этой подпрограмме используется вычисление векторного произведения

Sign — функция, принимающая значения -1, 0, 1 в зависимости от того, будет ли знак ее аргумента отрицателен, равен нулю или положителен

Раб1 = (Точка х — Р1х)(Р2у — Р1у) Раб2 = (Точка у — Р1у)(Р2х — Р1х) Раб3 = Раб1 — Раб2.

Твидимость = Sign (Раб3).

return.

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

subroutine Пересечение (Р1, Р2, W1, W2; Тсечения) подпрограмма использует параметрическое писание отрезков отрезки Р₁Р₂ и W₁W₂ считаются двумерными матричное уравнение с неизвестными значениями параметров получается путем приравнивания компонент х и у у двух параметрических описаний отрезков Коэф — матрица 2Х2, содержащая значения коэффициентов, уравнения отрезка Параметр — матрица 2Х1, содержащая значения параметров описания отрезков Параметр (1,1) — значение параметра описания отрезка Р Прав — матрица 2Х1, содержащая значения правых частей уравнений Обрат — функция, обращающая матрицу Умнож — функция умножения матриц.

сформировать матрицу Коэф

Коэф (1,1) = Р2х — Р1х Коэф (1,2) = W1ч — W2x.

Коэф (2,1) = Р2у — Р1у Коэф (2,2) = W1y — W2y.

сформировать матрицу правых частей

Прав (1,1) = W1x — P1x.

Прав (2,1) = W1y — P1y.

обратить матрицу коэффициентов

нет необходимости проверять здесь невырожденность этой матрицы, поскольку факт пересечения уже установлен

Коэф = Обрат (Коэф).

вычислить значения параметров в точке пересечения

Параметр = (Коэф) Умнож (Прав).

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

Тсечения = Р1 + (Р2 — Р1) Параметр (1,1).

return.

подпрограмма формирования результирующего многоугольника.

subroutine Выход (Вершина, N_Q, Q).

Вершина — содержит точку, заносимую в результат.

увеличить число вершин результата и добавить точку в Q

N_Q = N_Q + 1.

Q (N_Q) = Вершина.

return.