Алгоритмы закрашивания многоугольников

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

Граничный многоугольник области задается упорядоченным списком вершин Pg = (P ₁, P ₂ ,.., P_n), который описывает замкнутую ломаную линию. Для полноты формального описания многоугольной области важно также задать правило, определяющее то, с какой стороны от граничной линии располагаются ближайшие внутренние точки области.

Одно из наиболее простых и понятных правил определения внутренних точек области можно сформулировать следующим образом: всякая точка плоскости является внутренней точкой многоугольника, если луч, проведенный из нее в любом направлении, пересекает границу этого многоугольника нечетное число раз(рис. 1.7). Число же точек пересечения всякой прямой линии с границей будет четным. Причем при движении вдоль прямой будут чередоваться точки входа в многоугольник и выхода из него.

Рис. 1.7

Сказанное справедливо и для горизонтальных строк растра
(Y = Const). Поэтому закрашивание многоугольника можно выполнять построчно в пределах от ординаты Ymin самой нижней вершины многоугольника до ординаты Ymax самой верхней его вершины. Если список точек пересечения сторон многоугольника со строкой Y упорядочить по возрастанию или убыванию координаты x, то каждая очередная пара точек в списке будет определять границы (xl, Y) и (xr, Y)закрашиваемого сегмента строки (рис. 1.7).

Расчет границ Ymin и Ymax закрашивания по Y позволяет сократить число рассматриваемых строк. Однако, по разным причинам, например, за счет масштабирования многоугольник может частично или полностью выйти по Y за пределы интервала , где
Yemax – максимальное значение координаты y области вывода. Чтобы исключить безрезультатные вычисления в этих случаях, найденные значения следует скорректировать так:

(1.22)

(1.23)

При реализации метода следует учесть случаи, требующие особой обработки. Во-первых, это вершины многоугольника. В каждой вершине сопрягаются две смежные стороны. Если при закрашивании учитывать все точки пересечения сторон со строками, не исключая, начальную и конечную, то каждой вершине будут соответствовать две совпадающие границы сегментов, что во многих случаях, может привести к неправильному закрашиванию. Вторым особым случаем закрашивания являются горизонтальные стороны (∆y = 0) граничного многоугольника, поскольку они не пересекают строки растра, а лежат на них.

На рис. 1.8 приведен пример граничного контура многоугольника, на котором цифрами отмечены особые случаи: 1 – это вершины, которые должны обрабатываться как одна граница сегмента; 2 – вершины, которые следует рассматривать как две совпадающие границы; 3 – граничные вершины горизонтальных сторон.

Если для всякой стороны P_iP_{i +1} приращение по y рассчитывать как

, (1.24)

то случаи 1 и 2 легко различать между собой по знаку приращений ∆y смежных сторон, примыкающих к вершинам. В случае 1 они совпадают, а в случае 2 – противоположны.

Рис. 1.8

Для корректной обработки особых случаев примем следующее правило: если сторона многоугольника направлена вверх (∆y > 0), то из расчета точек пересечения со строками будем исключать ее начальную вершину, и наоборот, если сторона многоугольника направлена вниз (∆y < 0), то из расчета точек пересечения со строками будем исключать ее конечную вершину.

В остальных случаях для каждой стороны нужно установить пересекается ли она с текущей строкой и если – да, то вычислить координату x точки пересечения. Пусть для очередной стороны многоугольника y_i – координата y начальной вершины, а y_k – координата y ее конечной вершины. Тогда критерием пересечения стороны со строкой Y будет выполнение следующего условия:

(1.25)

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

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

1. Последовательно просматривая список вершин (P ₁, P ₂ ,.., P_n), найти границы сканирования Ymin и Ymax.

2. Вычислить Ymin = max(Ymin, 0); Ymax = min(Ymax, Yеmax).

3. Для каждой строки Y из [ Ymin.. Ymax ] выполнить п.п. 3.1. – 3.4.

3.1. Очистить список Xb.

3.2. Для всех i из [1 .. n ]выполнить п. 3.2.1. – 3.2.2.

3.2.1. Если i < n, то k = i + 1, иначе k = 1.

3.2.2. Если ((y _i < Y) и (y _k >= Y)) или ((y _i >= Y) и (y _k < Y)), то

вычислить координату x точки пересечения стороны P_i P_k
со строкой Y и записать в Xb.

3.3. Отсортировать список Xb по возрастанию.

3.4. Последовательно беря из списка Xb пары xl, xr, закрасить
соответствующие им сегменты строки Y.

В алгоритме для каждой строки Y сначала очищается список Xb границ сегментов, а затем циклически рассматриваются все стороны P_i P_k многоугольника, i – индекс текущей, а k – индекс последующей вершины. Учитывается, что за вершиной P_n следует вершина P ₁. В цикле производится тестирование сторон P_i P_k многоугольника по критерию (1.25). Для сторон, удовлетворяющих условию (1.24), вычисляется координата x точки пересечения стороны со строкой и записывается в Xb.

Когда обработка списка вершин заканчивается, список Xb сортируется по возрастанию. Сортировка гарантирует, что после этого левые и правые границы сегментов при движении от начала к концу списка будут чередоваться. Поэтому на заключительном этапе для закрашивания сегментов строки из Xb последовательно берутся пары элементов.

У данного алгоритма есть некоторые особенности, показанные на рис. 1.9. Во-первых, вершины локального максимума по Y будут всегда закрашиваться, а вершины локального минимума – нет. Это – следствие принятого критерия (1.25) к обработке сторон. На рис. 1.19 квадратиками отмечены места расположения вершин многоугольника. Вершины заданы в центрах квадратиков.

Рис. 1.9

Во-вторых, как видно из того же рисунка, тонкие слабо наклонные к оси OX выступы многоугольника могут закрашиваться с разрывами. Здесь причина в построчном способе закрашивания. Максимальная погрешность в расчете границ сегментов из-за их округления составляет 0,5 пикселя, но погрешность в изображении сторон по длине в таких случаях может стать значительно большей. Чтобы визуально улучшить вид многоугольника и снизить погрешность изображения тонких слабонаклонных выступов можно после завершения закрашивания обрисовать граничный контур многоугольника тем же цветом, что и цвет закраски.

Для определения внутренних точек закрашиваемой многоугольной области можно применить другое, более формальное и более универсальное правило, основанное на использовании понятия ориентации граничного контура. Если исходить из того, что порядок вершин в списке Pg = (P ₁, P ₂ ,.., P_n) определяет и порядок построения сторон многоугольника, то каждую сторону P_iP_{i+ 1}можно рассматривать как вектор, направленный из P_i в P_{i+ 1}. Тогда правило определения внутренних точек области сформулируем следующим образом:при движении от начала всякого вектора граничного контура к его концу ближайшие внутренние точки области расположены слева от него (рис. 1.10).

Рис. 1.10

Из этого правила следует, что при обходе вершин против часовой стрелки, внутренние точки области лежат внутри многоугольника, а при обходе по часовой стрелке – вне многоугольника. В последнем случае должна закрашиваться вся область вывода, кроме точек внутри многоугольника.

В соответствии со сказанным граничный многоугольник будем считать ориентированным по часовой стрелке или против, в зависимости от заданного в списке Pg = (P ₁, P ₂ ,.., P_n) направления обхода его вершин. Использование понятия ориентации для границы многоугольника открывает новые возможности.

Как видно из рис. 1.10, стороны много­угольника, направленные вверх (приращение ∆y > 0), являются правыми границами, а стороны, направленные вниз (∆y < 0), – левыми границами закрашиваемых сегментов строки. Поэтому точки пересечения сторон с очередной строкой по знаку ∆y можно сразу классифицировать как левые или правые границы сегментов. В связи с этим вместо общего списка Xb границ сегментов строки здесь удобнее формировать отдельно список Xl левых и список Xr правых границ. Очевидно, что очередную координату x следует заносить в список Xr, когда ∆y > 0, и в список Xl – в противном случае. Когда все точки пересечения сторон многоугольника со строкой будут найдены, количество элементов в списках Xl и Xr должно быть одинаковым.

Если граничный многоугольник ориентирован так, что должна закра­шиваться внешняя область (по часовой стрелке), то все строки, не имеющие точек пересечения с многоугольником, должны закрашиваться полностью (рис. 1.11). Для остальных строк список Xl не будет содержать левой границы первого закра­шива­емого сегмента, а список Xr не будет содержать правой границы последнего сегмента строки. В этих случаях для закрашивания в пределах области вывода в качестве недостающей левой границы первого сегмента следует взять левую границу области вывода, а в качестве недостающей правой границы последнего сегмента строки – ее правую границу.

Ориентацию (по часовой стрелке или против) граничного многоугольника можно определить аналитически. Для этого не требуется анализ взаимного расположения всех вершин. Ориентация граничного многоугольника совпадает с ориентацией невырожденного треугольника, заданного самой высшей или самой низшей вершиной многоугольника и двумя смежными с ней вершинами. Для определенности найдем в списке Pg наивысшую вершину P_j и две смежные с ней вершины P_{j- 1} и P_{j+ 1}(рис. 1.11).

Рис. 1.11

Известно, что площадь треугольника, заданного координатами вершин, в данном случае вершин P_{j -1}, P_j и P_{j +1}, определяется по формуле

. (1.26)

Анализ показывает, что значение площади, вычисленное по этой формуле, положительно, если обход точек P_{j -1}, P_j, P_{j +1} соответствует движению против часовой стрелки и отрицательно, если обход этих точек соответствует движению по часовой стрелке. Если рассматривается область без самопересечений, то ориентация всей области совпадает с ориентацией данного треугольника. Если выбранные точки лежат на одной прямой, то S = 0. Очевидно, что при S = 0 точка P_j находится в центре цепочки горизонтальных сторон. В таком случае j надо увеличивать до тех пор, пока не получится S ≠ 0.

Ниже представлен алгоритм закрашивания ориентированных многоугольников, построенный на основании изложенного.

1. Последовательно просматривая список вершин (P ₁, P ₂ ,.., P_n), найти индекс j наивысшей вершины, а также границы сканирования Ymin и Ymax.

2. Вычислить Ymin = max(Ymin, 0); Ymax = min(Ymax, Y еmax).

3. Вычислить площадь S треугольника P_{j -1} P_j P_{j +1}.

4. Если S < 0, то строки области вывода от 0 до Ymin закрасить целиком.

5. Для каждой строки Y из [ Ymin.. Ymax ] выполнить п.п. 5.1. - 5.5.

5.1. Очистить списки Xl и Xr.

5.2. Для всех i из [1 .. n ]выполнить п. 5.2.1. – 5.2.2.

5.2.1. Если i < n, то k = i + 1, иначе k = 1.

5.2.2. Если ((y _i < Y) и (y _k >= Y)) или ((y _i >= Y) и (y _k < Y)), то
выполнить п.п. 5.2.2.1. – 5.2.2.2.

5.2.2.1. Вычислить координату x точки пересечения стороны P_i P_k
со строкой Y.

5.2.2.2. Если P_k. y - P_i. y >0, то записать x в Xr, иначе - записать x в Xl.

5.3. Если S <0, то дополнить список Xl левой границей области вывода, а список Xr - ее правой границей.

5.4. Отсортировать списки Xl и Xr по возрастанию.

5.5. Последовательно беря из списков Xl и Xr по одному элементу в качестве границ xl, xr сегмента, закрасить все сегменты строки Y. Причем, если
xl > xr, то закрашивание производить не следует.

6. Если S < 0, то строки области вывода от Ymax до Y еmax закрасить целиком.

Для обработки особых случаев в данном алгоритме используется тот же критерий, что и в предыдущем алгоритме. Особенностью является учет ориентации многоугольника, а также использование раздельных списков левых Xl и правых Xr границ сегментов строки.

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

1.5. Теоретико-множественные операции
над двумерными областями

Сложные фигуры можно синтезировать из более простых, в том числе и из примитивов, с помощью теоретико-множественных операций (ТМО). Примеры операций объединения, пересечения, разности и симметрической разности приведены на рис 1.12.

Рис. 1.12

Если имеются примитивы с криволинейными границами, то такие границы аппроксимируются ломаными линиями из отрезков прямых, поэтому в качестве примитивов будем иметь в виду многоугольники. Результатом ТМО над многоугольниками может быть как односвязаная, так и многосвязная область плоскости. Поиск точного описания границ результирующей области требует сложных вычислений и тонкого анализа возможных вариантов взаимного расположения границ областей [1]. Если же учесть, что изображение формируется построчно, то ТМО проще выполнять над горизонтальными сечениями исходных областей непосредственно во время визуализации [3].

На рис. 1.13 показана реализация построчного выполнения ТМО над сечениями S_A и S_B исходных фигур A и B строкой Y. Переменная S обозначает сечение результирующей области, полученное с помощью ТМО над S_A и S_B. Сплошные участки сечений фигур будем называть сегментами, x_Al, x_Bl, x_Ar, x_Br – левые и правые границы сегментовдля S_A и S_B.

Рис. 1.13

Поставим в соответствие внутренним точкам сегментов сечения S многоугольной области функцию L (x), которую будем называть пороговой. Определим ее следующим образом:

(1.27)

Поведение пороговой функции иллюстрирует рис. 1.14. Как видно, внутренним точкам области соответствует значение L (x) = 1.

Пусть теперь имеются сечения S_A и S_B строкой Y двух фигур A и B. Обозначим через L_a (x) и L_b (x) пороговые функции для S_A и S_B. Рассмотрим взвешенную сумму Q (x) = gL_a (x) + hL_b (x) пороговых функций (рис. 1.15) для g ≠ h и g, h ≠ 0.

Рис. 1.14

Рис. 1.15

Анализ свойств суммы Q (x) позволяет выделить области значений, соответствующие различным видам ТМО. Результат анализа приведен в табл. 1.1.

Таблица 1.1

Q (x)	ТМО
≥ min(g, h)	Объединение
= g + h	Пересечение
= g, h	Симметрическая разность
= g	Разность A \ B
= h	Разность B \ A

Из табл. 1.1 видно, что рассмотренный метод применим для реализации всех основных видов ТМО.

Перейдем к разработке алгоритма выполнения ТМО над сечениями двух плоских фигур A и B. Будем считать, что в качестве исходных данных для очередной строки Y используются массивы левых Xal и правых Xar границ сегментов сечения S_A фигуры A, и массивы левых Xbl и правых Xbr границ сегментов сечения S_B фигуры B.

Закодируем все ТМО, а также примем конкретные значения весов для расчета Q (x): g = 2; h = 1. Тогда табл. 1.1 примет вид табл. 1.2.

Таблица 1.2

Код ТМО	Q (x)	ТМО
	≥ 1	Объединение
	= 3	Пересечение
	= 1, 2	Симметрическая разность
	= 2	Разность A \ B
	= 1	Разность B \ A

Код заданной ТМО также будет параметром алгоритма.

Для совместной обработки исходных границ сегментов используем рабочий массив M. Элементы массива M представляют собой записи с полями M [ i ] .x и M [ i ] .dQ. Поле M [ i ] .x служит для записи координаты x границы сегмента, а поле M [ i ] .dQ – для записи соответствующего приращения пороговой функции с учетом веса операнда. Поле dQ необходимо для того, чтобы при последовательном просмотре массива M можно было однозначно восстановить вид функции Q (x).

Результатом работы алгоритма будут массивы Xrl и Xrr левых и правых границ сегментов сечения результирующей области R строкой Y.

Кроме перечисленных выше, в алгоритме использованы также следующие переменные:

SetQ – множество значений суммы Q пороговых функций L операндов, соответствующее заданной ТМО;

k и m – счетчики элементов соответственно в массивах Xrl и Xrr;

Xemin и Xemax – соответственно левая и правая границы области вывода.

Для удобства представления алгоритма используется функция Length (X), возвращающая заполненное количество элементов в массиве X.

Алгоритм выполнения любой из перечисленных в табл. 1.2 ТМО представлен ниже.

1. Если TMO = 1, то SetQ = [1,3] // объединение

иначе если TMO = 2, то SetQ = [3,3] // пересечение

иначе если TMO = 3, то SetQ = [1,2] // сим. разность

иначе если TMO = 4, то SetQ = [2,2] // разность А - В

иначе если TMO = 5, то SetQ = [1,1] // разность B - A

2. n = Length (Xal).

3. Для всех i из [1.. n ]выполнить M [ i ]. x = Xal [ i ]; M [ i ]. dQ = 2.

4. nM = n; n = Length (Xar).

5. Для всех i из [1.. n ]выполнить M [ nM + i ]. x = Xar [ i ]; M [ nM + i ]. dQ = -2.

6. nM = nM + n; n = Length (Xbl).

7. Для всех i из [1.. n ]выполнить M [ nM + i ]. x = Xbl [ i ]; M [ nM + i ]. dQ = 1.

8. nM = nM + n; n = Length (Xbr).

9. Для всех i из [1.. n ]выполнить M [ nM + i ]. x = Xbr [ i ]; M [ nM + i ]. dQ = -1,

10. nM = nM + n; // общее число элементов в массиве M

11. Отсортировать массив M по возрастанию M [ i ]. x.

12. k = 1; m = 1; Q = 0.

13. Если (M [1]. x >= Xemin) и (M [1]. dQ < 0), то
Xrl [1] = Xemin; Q = - M [1]. dQ; k = 2.

14. Для всех i из [1.. nM ]выполнить п.п. 14.1. - 14.4.

14.1. x = M [ i ]. x; Qnew = Q + M [ i ]. dQ.

14.2. Если (Q Ï SetQ) и (Qnew Î SetQ), то Xrl [ k ] = x; k = k + 1.

14.3. Если (Q Î SetQ) и (Qnew Ï SetQ), то Xrr [ m ] = x; m = m + 1.

14.4. Q = Qnew.

15. Если Q Î SetQ, то Xrr [ m ] = Xemax.

В первой части алгоритма границы сегментов из исходных массивов Xal, Xbl, Xar, Xbr переписываются в рабочий массив M. При этом в поле dQ записываются приращения пороговых функций с учетом веса операндов. Цель сортировки массива M по возрастанию – упорядочивание значений аргумента функции Q (x). После сортировки начинается обработка массива M. Особым случаем является такой, когда ­первым элементом массива M оказывается правая граница сегмента, т.е. M [1]. x >= Xemin и M [1]. dQ < 0. В этой ситуации список Xrl левых границ сегментов необходимо дополнить значением Xemin.

В циклической части алгоритма последовательно просматриваются элементы массива M. В качестве текущего значения переменной x всегда выбирается очередное значение M [ i ]. x. При этом функция Q изменяется на величину M [ i ]. dQ.

Если в очередном цикле предыдущее значение Q не входило в SetQ, а новое ее значение Qnew в SetQ входит, значит x – координата левой границы сегмента результирующей области. Это значение записывается в Xrl. Аналогичным образом устанавливаются случаи, в которых x является координатой правой границы. Такие значения x записывается в массив Xrr.

По завершению цикла обработки M число левых границ в массиве Xrl должно быть равно числу правых границ в массиве Xrr. Если же в этот момент Q Î SetQ, значит не найдена правая граница последнего сегмента. Тогда за нее принимается правая граница Xemax области вывода.