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

Линии уровня (изолинии) на плоскости образуются точками, для которых функция принимает постоянные значения

Текущий интервал уровней определяется вспомогательным алгоритмом 'Интервал'. Отдельные изолинии получаемого семейства могут обозначаться, например, цветом точек в соответствии с порядковым номером уровня в наборе, который определяется вспомогательным алгоритмом 'Уровень'. На Рис. 1 цвета точек условно обозначены различными символами (кружочек, крестик, плюсик и т.д.).

Вспомогательные алгоритмы 'Масштаб' и 'ГрафX', 'ГрафY' для пересчета в систему координат графического растрового экрана будут рассмотрены в разделе 4.

| Описание общих величин:

вещ ax,ay,bx,by | Границы карты изолиний.

цел N, вещ таб C[1:15] | Таблица значений N уровней в порядке их возрастания.

вещ kx,kx0,ky,ky0 | Коэффициенты пересчета в систему координат графического

| экрана.

алг вещ f (арг вещ x,y)

| знач := заданная функция двух переменных f(x,y)

| Алгоритмы исполнителя:

нач вещ x,y,hx,hy, цел k0,kxg,yg,i

| | Ввод значений ax,bx,ay,by, количества N и значений уровней C[i], i=1,...,N.

| | Выбор графического режима и вычисление коэффициентов пересчета

| | kx,kx0,ky,ky0 к координатам графического экрана (вызов вспомогательного

| | алгоритма "Масштаб").

| | Выбор шагов сканирования hx, hy.

| | Изображение координатных осей на графическом экране.

| . . . . . . . . . . . . . . . . . . . . . . . . . . . .

| y := ay

| нц пока y <= by | Просмотр строки с координатой y.

| | yg := ГрафY(y) | Пересчет в координату графического экрана.

| | x := ax

| | k0 := Интервал(f(x,y)) | Номер начального интервала уровней в строке.

| | нц пока x <= bx

| | | x := x + hx | Шаг вдоль строки сканирования.

| | | k := Интервал(f(x,y)) | Номер текущего интервала.

| | | если k <> k0 | Произошло пересечение изолинии.

| | | | то

| | | | Цвет := Уровень(k0,k) | Цвет точки соответствует номеру пересеченной

| | | | | изолинии.

| | | | xg := ГрафX(x - hx/2) | Пересчет в координату графического экрана.

| | | | точка(xg,yg) | Изображение на экране точки заданного цвета.

| | | | k0 := k

| | | все

| | кц

| | y := y + hy | Переход на следующую строку сканирования.

| кц

алг цел Интервал (арг вещ z)

| дано | Значение функции z.

| надо | Номер интервала уровней (1..N+1), которому принадлежит это значение.

нач цел i

| знач := N + 1

| нц для i от 1 до N

| | если z < C[i]

| | то знач := i; выход

| | все

| кц

алг цел Уровень (арг цел k0,k)

| дано | Предыдущий и текущий номера интервалов уровней ko,k.

| надо | Номер уровня изолинии, пересеченной при сканировании.

| если k > k0

| | то знач := k - 1

| | иначе знач := k

| все

Примечание. Вспомогательный алгоритм-функцию 'Интервал' можно записать и без использования неструктурной команды выход :

знач := N + 1; i := 1

нц пока (знач <> i) и (i <= N)

| если z < C[i]

| | то знач := i

| все

| i := i + 1

Сканирование в нашем алгоритме производится вдоль "строк", параллельных оси 0x. В связи с этим могут плохо воспроизводиться участки изолиний, близкие к горизонтальным, даже при малых шагах сканирования hx, hy. Поэтому в основном алгоритме 'Карта изолиний' целесообразно предусмотреть повторное сканирование, но уже по "столбцам", параллельным оси 0y. Алгоритм работает сравнительно медленно, поскольку для достаточно качественного "поточечного" воспроизведения изолиний желательно предусматривать мелкую сетку точек сканирования. Несомненным достоинством этого алгоритма является то, что он строит сразу всё семейство изолиний. Однако это требует предварительного выбора сразу всей сетки изолиний и существенно затрудняет какую либо последующую корректировку полученной карты.

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

составляющие которого - частные производные функции по x и y, соответственно, и который определяет направление наискорейшего возрастания функции.

1) Перемещение от начальной точки (X₀, Y₀) вдоль касательной к линии уровня f(x,y)=C (C=f(X₀, Y₀) ) на шаг L в точку (X, Y).

Уравнение касательной к линии уровня в точке (X₀, Y₀) имеет вид

При длине шага L, то есть при

Эта операция осуществляется вспомогательным алгоритмом 'Шаг'. Здесь знак множителя R = ± 1 определяет направление обхода изолинии: при R = 1 перемещение происходит вправо от вектора градиента (как на Рис. 2), а при R = - 1 перемещение происходит в обратном направлении.

2) Поиск точки (X₁, Y₁) с заданным уровнем f (X₁, Y₁) = C, ближайшей к полученной точке (X, Y).

Для этого воспользуемся тем, что наискорейшее изменение значений функции происходит по направлению вектора градиента. Чтобы решить уравнение f (X, Y) = C вдоль линии градиента, используем итерационный метод Ньютона (метод касательных). Обозначим t = (X, Y)^T. Тогда итерационный шаг вдоль линии градиента будет иметь вид

С учетом дифференцируемости f(t) имеем

Для улучшения сходимости алгоритма введем "дробление" шага a _k при неудачной итерации. Получаем вспомогательный алгоритм 'Поиск'.

3) Изображение отрезка прямой, соединяющего точку (X₀, Y₀) с точкой (X₁, Y₁). При этом для перехода к системе координат графического экрана компьютера используются упоминавшиеся ранее вспомогательные алгоритмы 'Масштаб', 'ГрафX' и 'ГрафY' (см. Раздел 4).

Для того, чтобы завершить построение замкнутой изолинии, необходимо перед каждым переходом из (X₀, Y₀) в (X₁, Y₁), начиная с третьего отрезка ломаной, контролировать расстояние от последней из точек t⁰ = (X₀, Y₀)^T до первой из начальных точек s = (P, Q)^T. При их достаточной близости, например, при , следует положить (X₁, Y₁) = s, изобразить последний отрезок и закончить работу.

Если строящаяся изолиния выходит за заданные границы карты, то следует принять R = - 1 и завершить построение изолинии, начиная вновь с начальной точки s, то есть с X₀ = P, Y₀ = Q, и перемещаясь в направлении, обратном первоначальному, до выхода за границы карты.

| Описание общих величин:

вещ ax,ay,bx,by | Границы карты изолиний.

вещ kx,kx0,ky,ky0 | Коэффициенты пересчета в систему координат графического

| | экрана.

алг вещ f (арг вещ x,y)

| знач := заданная функция двух переменных f(x,y)

алг вещ ГрадX (арг вещ x,y)

| знач := производная от f(x,y) по x

алг вещ ГрадY (арг вещ x,y)

| знач := производная от f(x,y) по y

| Алгоритмы исполнителя:

нач вещ x,y,x0,y0,x1,y1,P,Q,C,Eps,L, цел R,xg0,yg0,xg1,yg1,i

| | Ввод значений ax,bx,ay,by.

| | Ввод значений Eps и L, в соответствии с желаемой точностью трассировки

| | изолинии.

| | Ввод начальной точки (x,y), вычисление значения функции f(x,y) и ввод нужного

| | значения уровня C.

| | Выбор графического режима и вычисление коэффициентов пересчета

| | kx,kx0,ky,ky0 к координатам графического экрана (вызов вспомогательного

| | алгоритма "Масштаб").

| | Изображение координатных осей на графическом экране.

| . . . . . . . . . . . . . . . . . . . . . . . . . . . .

| Поиск (x,y,C,Eps,P,Q)

| x0 := P; y0 := Q; R := 1; i := 1

| нц

| | Шаг (x0,y0,L,R,x,y)

| | Поиск (x,y,C,Eps,x1,y1)

| | xg0 := ГрафX (x0); yg0 := ГрафY (y0)

| | поз (xg0,yg0)

| | xg1 := ГрафX (x1); yg1 := ГрафY (y1)

| | линия (xg1,yg1)

| | x0 := x1; y0 := y1; i := i+1

| | поз (xg0,yg0)

| | если (x0>bx+l) или (x0<ax-L) или (y0>by+L) или (y0<ay-L)

| | | то | Выход за границы карты.

| | | если R = -1

| | | | то x := P; y := Q; выход

| | | | иначе R := -1; x0 := P; y0 := Q; i := 1

| | | все

| | все

| | если (R=1) и (i>3) и (Длина(x1,y1,P,Q)<1.5*L)

| | | то выход

| | все

| кц

| xg0 := ГрафX (P); yg0 := ГрафY (Q)

| поз (xg0,yg0); линия (xg1,yg1)

алг вещ Длина (арг вещ x1,y1,x2,y2)

| | Расстояние между точками (x1,y1) и (x2,y2):

| знач := sqrt((x2-x1)**2 + (y2-y1)**2)

алг Шаг (арг вещ x0,y0,L, цел R, рез вещ x,y)

| дано | Начальная точка (x0,y0), длина шага L, направление обхода изолинии R.

| надо | Точка (x,y) на расстоянии L от (x0,y0) по касательной к изолинии.

нач вещ G

| G := sqrt(ГрадX(x0,y0)**2 + ГрадY(x0,y0)**2) | Модуль вектора градиента.

| | Шаг вдоль касательной:

| x := x0 + R*L*ГрадY(x0,y0)/G

| y := y0 - R*L*ГрадX(x0,y0)/G

алг Поиск (арг вещ x,y,C,Eps, рез вещ x1,y1)

| дано | Начальная точка (x,y), значение искомого уровня C, допустимая

| | погрешность по уровню Eps.

| надо | Ближайшая к (x,y) вдоль линии градиента точка (x1,y1) на линии

| | уровня C.

нач вещ U,V,dF,dF1,G2

| U := x; V := y

| dF := C - f(U,V) | Начальное отклонение от уровня C.

| нц пока abs(dF) > Eps

| | G2 := ГрадX(U,V)**2 + ГрадY(U,V)**2

| | x1 := U + dF*ГрадX(U,V)/G2

| | y1 := V + dF*ГрадY(U,V)/G2

| | dF1 := C - f(x1,y1)

| | нц пока abs(dF1) > abs(dF)

| | | x1 := (x1 + U)/2; y1 := (y1 + V)/2

| | | dF1 := C - f(x1,y1)

| | кц

| U := x1; V := y1; dF := dF1

| кц

| x1 := U; y1 := V

Используя вспомогательный алгоритм 'Поиск', можно в алгоритме 'Изолиния' вновь перейти из текущей точки X = P, Y = Q к новой изолинии с другим значением C и приступить к ее построению.

Рассмотрим теперь особенности реализации процесса построения карты изолиний средствами компьютерной графики.

Для изображения изолиний на экране дисплея необходимо перейти от исходной декартовой системы координат карты изолиний к системе координат растрового графического экрана (рис. 3).

Каждой точке (X, Y) исходной системы координат мы должны поставить в соответствие точку прямоугольного растра - пиксел с целочисленными координатами .

Преобразование координат осуществляется по очевидным линейным соотношениям

с округлением значения правой части до ближайшего целого числа. Эти соотношения реализованы вспомогательными алгоритмами-функциями 'ГрафX' и 'ГрафY'.

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

а) б)

Рис. 4.

 где

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

Эти соотношения реализованы вспомогательным алгоритмом ‘Масштаб’, а для непосредственного преобразования координат используются уже упоминавшиеся вспомогательные алгоритмы-функции ‘ГрафX’ и ‘ГрафY’.

алг Масштаб (арг вещ ax,bx,ay,by, рез вещ kx0,kx,ky0,ky)

| дано | Границы карты изолиний ax,bx,ay,by

| надо | Коэффициенты пересчета в систему координат графического

| | экрана kx,kx0,ky,ky0

нач вещ R0,w,h

| R0 := 4/3; w := bx - ax; h := by - ay

| если w/h > R0

| | то kx := максY / w; kx0 := -kx*ax

| | ky := - максY*R0 / w; ky0 := -ky*(w / R0 + (ay + by)) / 2

| | иначе kx := максX(h*R0); kx0 := kx*(h*R0 - (ax + bx)) / 2

| | ky := - максY/h; ky0 := -ky*by

| все

алг цел ГрафX (арг вещ x)

| знач := int (x*kx+kx0+0.5)

алг цел ГрафY (арг вещ y)

| знач := int (y*ky+ky0+0.5)

Здесь максX и максY это стандартные переменные исполнителя ГраТекс системы КуМир, характеризующие соответствующие максимальные координаты графического растрового экрана.

На мою главную страницу