8.3. ЗАПОЛНЕНИЕ КОНТУРА ПО КРИТЕРИЮ ЧЕТНОСТИ

Хотя реализация проверки на четность в алгоритмах заполнения области между сторонами многоугольника тривиальна, она перестает быть таковой при переходе на дискретную плоскость. Помимо сложностей, связанных с выявлением касаний, которые должны учитываться как сдвоенные точки, следует принимать во внимание и кратные пикселы, поскольку они могут исказить результаты подсчета числа пересечений. Трудности, связанные с определением прямых и пересечений прямых и кривых и обсуждавшиеся в гл. 7, должны послужить предупреждением о риске, которым чреват данный подход. В этом разделе будет изложен алгоритм, в котором используется К-ГСС, и затем будет показано, что для полных областей он дает правильные результаты. В алгоритме 8.2 представлены основные операции, связанные с выполнением проверки на четность.

Алгоритм 8.2. Тривиальная процедура проверки на четность на плоскости

(см. скан)

Совершенно очевидно, что алгоритм 8.2 неточен. Во-первых, в нем ведется подсчет пикселов, а не отрезков, образованных смежными пикселами, которые окрашены в цвет контура. (Напомним, что пересечение двух кривых на дискретной плоскости не обязательно представляется одним пикселом.) Во-вторых, этот алгоритм не предусматривает отыскание экстремумов. Корректный алгоритм, по крайней мере для полных областей, можно построить, если учитывать не пикселы, а отрезки, и учитывать прямые, расположенные над и под прямой, используемой для проверки на четность. Если одна из этих прямых не пересекает контур в окрестности рассматриваемого пересечения, то это означает, что рассматриваемая («проверяемая на четность») прямая является касательной.

Алгоритм 8.3. Алгоритм заполнения области по критерию четности на основе анализа значений пикселов

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

(см. скан)

В данном случае в качестве структуры данных удобно использовать граф смежности строк контура (К-ГСС), поскольку его вершины соответствуют пересечениям контура с некоторой горизонтальной прямой. В точке максимума верхний порядок вершины равен нулю, а в точке минимума нижний порядок вершины равен нулю. Если контур не содержит кратных пикселов, то пересечению дуги с горизонтальной прямой в К-ГСС соответствует вершина с порядками (1,1). Более того, вершины, соответствующие экстремумам, будут иметь порядки (0,2) или (2,0). Любые другие пары значений порядков недопустимы для полной области. Эти условия использованы в алгоритме 8.3. Для определения порядков вершин К-ГСС (посредством подсчета числа интервалов, перекрывающихся с рассматриваемым) в данном алгоритме служит процедура LINK (СВЯЗЬ, представленная в виде алгоритма 8.3а). Предполагается, что единицами измерения значений х и у служат размеры ячеек сетки. Появление признака ошибки в

распечатке алгоритма сигнализирует о порядках, отличных от допустимых пар значений (1,1), (0,2) и (2,0). На рис. 8.3 приведено несколько примеров значений порядков вершин ГСС для различных конфигураций пикселов.

Рис. 8.3. Примеры конфигураций, возникающих при перекрытии интервалов; указанные значения счетчиков использованы в алгоритмах 8.3, 8.3а: символ а — верхний порядок, символ б — нижний порядок

Алгоритм 8.3а. Определение порядка вершины ГСС Procedure LINK

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

(см. скан)