Заливка с сортировкой

Заливка с  сортировкой

Смысл данного способа заключается в следующем.

Заливка осуществляется за счет закраски отдельных участков всех  растровых линий, параллельных одной из координатных осей (допустим X), расположенных в заданном габарите (например, в диапазоне от  x_min- x_max). Закраске подлежат участки растровых линий, которые находятся внутри заливаемой области  

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

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

На приведенном рисунке (Рис. 4.1‑1) для горизонтальной  растровой линии с координатой y_s точками пересечения с ребрами многоугольника, представляющего заливаемую область, являются точки:

         a_п, b_п, d_п, e_п, f_п, i_п , k_п, n_п.

     В этом случае отсортированная по координате X последовательность этих точек будет иметь следующий вид:

i_п , d_п, k_п, b_п, e_п, n_п, f_п, a_п.

Рекомендуемые материалы

На основании полученной отсортированной последовательности точек пересечения, в качестве закрашиваемых заданным цветом берутся следующие отрезки растровой линии y_s:

2.2. Дискретизация, квантование и кодирование сигналов - лекция, которая пользуется популярностью у тех, кто читал эту лекцию.

 i_п d_п, k_п b_п, e_п n_п, f_п a_п.

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

При реализации данного способа при выборе очередного ребра для определения его пересечения с растровой линией целесообразно

Рис. 4.1‑1

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