В мир информатики # 90 (16–30 апреля).
Школа программирования

Генератор массива пикселей

О.В. Трушин,
г. Уфа

Описываемые ниже алгоритмы основаны на идее отображать на экране математические зависимости⁴ с помощью случайных чисел и “фильтров”, накладываемых на сгенерированные данные.

Для начала составим программу⁵, генерирующую пиксели в прямоугольной области экрана (см. рис. 1).

Рис. 1

Координаты очередной генерируемой точки x, y зададим как случайные числа [1] в диапазонах x1..x2, y1..y2, а ее цвет c — как число из диапазона от 1
до 15. Генерацию очередного пикселя будем проводить с помощью процедуры NextPixel, в которой происходит также увеличение общего числа сгенерированных точек на 1 (имя соответствующей переменной величины — n):

Procedure NextPixel;

Begin

{Получаем случайные значения

координат и цвета точки}

x := x1 + Random(x2 – x1 + 1);

y := y1 + Random(y2 – y1 + 1);

c := 1 + Random(15);

{Увеличиваем значение n на 1}

Inc(n)

End;

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

Function Put: boolean;

If True {Здесь будет условие фильтрации}

Then

Begin

Put := True;

{Увеличиваем значение m на 1}

Inc(m)

Else Put := False

End;

В основной части программы зададим необходимые параметры и организуем цикл (до нажатия клавиши), в котором будем генерировать точки и выводить их на экран при выполнении условия фильтра. На каждой 10 000-й генерации будем отображать количества точек — всех и отфильтрованных.

Uses Crt, Graph;

Var n, m: longint; x, y, x1, x2, y1, y2: word;

c: byte; tn, tm: string;

Gd, Gm: integer;

BEGIN

{Инициализируем графический режим}

Gd := 0; InitGraph(Gd, Gm, '');

n := 0; m := 0; {счетчики точек}

x1 := 20; y1 := 20;

x2 := 620; y2 := 420;

xc := 320; yc := 220;

Repeat

{Генерируем очередную точку}

NextPixel;

If Put {"Накладываем" фильтр}

Then {Выводим пиксель}

PutPixel(x, y, c);

If n mod 10000 = 0 Then

Begin

{Строка для вывода на экран текста.

Преобразуем значения n и m в текст}

Str(n:10, tn);

Str(m:10, tm);

{Готовим прямоугольную область для вывода}

SetFillStyle(0, 0);

Bar(100, 450, 400, 480);

{Выводим текст}

OutTextXY(100, 450, 'n=' + tn);

OutTextXY(100, 460, 'm=' + tm)

End

{До нажатия клавиши}

Until KeyPressed;

ReadKey; CloseGraph

END.

Запустим программу — пока ничего интересного не наблюдается: все точки выводятся в заданную область, счетчик отображает их количество, фильтр не работает (выводятся все точки). Введем в функцию Put условие попадания точки с координатами x, y в прямоугольник с границами x = 140..500,
y = 100..350:

If (x > 140) And (x < 500) And (y > 100)

And (y < 350)

При выполнении программы получим изображение, показанное на рис. 1.

Далее попробуем наоборот — выводить только те пиксели, которые не попадают в заданную прямоугольную область (рис. 2):

Рис. 2

Попытка решить такую задачу типовым методом, например, ограничив область полосами сверху и снизу и добавив оставшиеся зоны слева и справа, ни к чему хорошему не приведет. Фильтр получается громоздким и некрасивым. Однако простота заданного условия наводит на мысль, что и решение должно быть простым. Действительно, “фильтр наоборот” сделать нетрудно — достаточно лишь инвертировать условие этого фильтра с помощью логической операции отрицания:

If Not((x > 140) And (x < 500) And (y > 100)And (y < 350))7

Итак, точки генерируются, внизу экрана счетчики исправно показывают их количества — всех n и отфильтрованных m. Нетрудно заметить, что отношение этих количеств примерно равно отношению площадей зоны генерации и зоны фильтрации. И чем больше точек, тем отношение точнее. Эта закономерность лежит в основе так называемого “метода Монте-Карло” для определения площадей фигур [2].

Апробируем метод Монте-Карло для определения площади круга. Уравнение окружности радиусом r с центром в точке xc, yc имеет вид (x – x_c)² + + (y – y_c)² = r², откуда условие нахождения точки с координатами x, y внутри круга запишется так:

If Sqr(x — xc) + Sqr(y — yc) < Sqr(r)

Задав значение r равным, например, 180 и подсчитав значения n и m, величину площади круга sk можно определить по формуле sk = s0 * (m/n)⁸, где s0 — площадь всей зоны генерации точек.

В приведенной выше программе заменим фрагмент, относящийся к выводу текста, на следующий9:

{Строка для вывода на экран текста.

Площадь зоны генерации}

s0 := (x2 — x1) * (y2 — y1);

{Точное значение площади круга}

s := pi * r * r;

{Площадь круга по методу Монте-Карло}

sk := s0 * (m/n);

{Преобразуем значения s и sk в текст}

Str(s:10:2, f1);

Str(sk:10:2, f2);

SetFillStyle(0, 0);

Bar(100, 450, 400, 480);

OutTextXY(100, 450, 'n=' + tn + ' s=' + f1);

OutTextXY(100, 460, 'm=' + tm + ' sk=' + f2);

Видно, что при росте количества генераций явного повышения точности расчета не происходит. Это вызвано несовершенством генератора случайных чисел, задействованного функцией Random.

Возникает вопрос — можно ли получить график функции, ограничивающей зону фильтра, использовав в условии знак равенства вместо знаков, соответствующих неравенству? Например, в случае окружности:

If Sqr(x – xc) + Sqr(y – yc) = Sqr(r).

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

If Abs(Sqr(x — xc) + Sqr(y — yc) — Sqr(r)) < 30

Величина погрешности в правой части неравенства зависит от вида функции и подбирается экспериментально.

Задание для самостоятельной работы

Отобразите с помощью описанного генератора массива пикселей:

1) эллипс: ((x – x_c)/a)² + ((y – y_c)/b)² = r²;

2) астроиду: (x – x_c)^2/3 + (y – y_c)^2/3 = r^2/3;

3) прямую, проходящую через две заданные точки.

Литература

1. Случайные числа в программах. / “В мир информатики” № 33 (“Информатика” № 34/2004).

2. Метод Монте-Карло. / “В мир информатики” № 2 (“Информатика” № 34/2003).

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

⁴ Необходимость в этом часто возникает при решении задач моделирования. — Ред.

⁵ Автор использует язык программирования Паскаль. Подробные комментарии к программе позволят вам подготовить соответствующую программу и на другом языке. — Ред.

⁶ В языках программирования Бейсик и Си вместо функции логического типа следует использовать функцию, возвращающую результат, равный 1 или 0. — Ред.

⁷ Можно упростить условие, применив законы логики. Предлагаем читателям сделать это самостоятельно. — Ред.

⁸ Скобки в выражении приведены исключительно для того, чтобы показать пропорциональность площадей и количества точек.

⁹ В нем использованы новые величины s0, s, sk, f1 и f2, которые, конечно, должны быть описаны в программе. — Ред.