ИСТИНА

Первообладателями программы являются авторы прграммного обеспечения, Московский государственный университет имени М.В.Ломоносова в лице ректора Академика РАН Садовничего В.А., Кафедра геофизики Геологического факультета МГУ в лице зав кафедрой член-корр. АН СССР профессора Федынского В.В. Авторы программного обеспечения О. К. ЛИТВИНЕНКО, В. Б. ГУСЕВ, Ю. Г. РУСЬЯНОВ, М. Д. РУКИН МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧИ - ПОСТРОЕНИЯ КАРТ ИЗОЛИНИЙ В настоящее время разработано несколько алгоритмов и про¬грамм, обеспечивающих построение карт изолиний [2—5]. Как показал опыт эксплуатации устройства «Атлас», предназначенного для построения карт изолиний цифровых моделей различных геофизических полей, непосредственное соединение исполнительного устройства с ЭВМ приводит к неоправданно большим затратам машинного времени. Нашей промышленностью серийно выпускается комплекс аппаратуры, предназначенный для автоматического построения штри¬ховых изображений, — автоматический построитель графиков АПГ, управляемый автономно при помощи перфоленты. АПГ включает в себя электронный преобразователь (УП-7) и двух¬координатный регистрирующий прибор (ДРП-3). Этот комплекс позволяет строить непрерывные ломаные линии по заданным координатам вершин на листе размером до 80 X 80 см [1]. В работе приводятся алгоритм и блок-схема решения задачи построения изолиний с использованием АПГ. Пусть в узлах равномерной прямоугольной сетки, покрывающей некоторую область D на плоскости, заданы значения функции f (х, у). Требуется построить семейство изолиний на уровнях Сi = Со + ih, когда задано начальное значение уровня С0 и сечение изолиний h, где i — номер уровня. В алгоритме построения изолиний выделяются два крупных блока: а) блок линейной интерполяции функции на отрезках между узлами ее задания и выдачи последовательностей точек пересечения изолинии с этими отрезками; б) блок гладкой аппроксимации изолиний по полученным точкам. При этом нами введен ряд критериев, наиболее важные из которых следующие. 1. Ломаную аппаратурную линию будем называть визуально гладкой, если два смежных ее звена (рис. 1) удовлетворяют соотношению DS £ d/ Dj (1) где Dj — угол между смежными звеньями ломаной; DS - расстояние между вершинами ломаной. Условие (1) требует, чтобы при увеличении угла между звеньями Dj длина этих звеньев уменьшалась следующим образом: при отклонении каждого следующего звена на величину, не превышающую d от первоначального направления. Начиналось новое звено ломанной. * Самописец АПГ строит линии определенной ширины (аппаратурные линии). Поскольку АПГ строит ломаные аппаратурные линии, соединяя пря¬мой два последовательных узла, возникает проблема представления гладких кривых ломаными аппаратурными линиями. Рис. 1. Построение визуально гладкой изолинии. Это требование обеспечивает построение линии вида плавной кривой. Условие (1) позволяет выбирать шаг AS (длину звеньев) визуально гладкой ломаной линии. 2. Процесс гладкой аппроксимации изолиний по узлам изолиний представим как сопряжение гладких аппроксимирующих кривых, соединяющих последовательно пары узлов изолинии (и задана последовательность узлов изолиний). Обеспечим сопряжение этих кривых фиксацией общих касательных в узлах задания. При таком подходе возникает проблема устойчивости аппроксимирующей кривой. Кривую, или представляющую ее функцию, аппроксимирующую изолинию в элементарном прямоугольнике, будем называть устойчивой, если: а) координаты этой кривой не выходят за границы элементарных прямоугольников сетки, содержащих пары узлов изолинии; б) кривая, лежащая в элементарном прямоугольнике, зависит только от расположения узлов, принадлежащих данному и ограниченному числу соседних прямоугольников; в) аппроксимирующая кривая (функция) внутри данного прямоугольника имеет минимальное число экстремумов и точек перегиба. Рассмотрим алгоритм блока интерполяции и выделения изо¬линий для функции f (х, у), заданной на области, состоящей из подобластей Dk = S x S (рис. 2). На рис. 2: S — некоторое фиксированное число (в данном случае S = 16) узлов задания функции, j — текущий индекс узла, к — номер подобласти. На начальном этане строится первый вспомогательный массив Q, фиксирующий лишь прямоугольники, которые покрывают изолинию. Далее выделение прямоугольников покрытия данной изолинии и вычисление координат ее узлов идут параллельно. При этом число операций составляет величину порядка п. Занумеруем стороны элементарного прямоугольника, начиная с верхней стороны по часовой стрелке. Узлы нумеруются по строке слева направо и по столбцам сверху вниз. Массив Q строится следующим образом: каждому прямоугольнику (их число (S — I)2 в подобласти Dk) соответствует одна ячейка оперативной памяти. Заполняются только первые пять разрядов ячейки: e1 — e5. Если изолиния пересекает первую сторону прямоугольника, то e1= 1, если не пересекает, то e1= О, и так далее до e4. Содержание пятого разряда e5 = 1 в том и только в том случае, если изолиния пересекает данный прямоугольник и одновременно границу подобласти Dk, второй вспомогательный массив L содержит в закодированном виде координаты выделенных точек. Блок построения массива L состоит из четырех участков, соответствующих четырем возможностям выхода изолинии из прямоугольника. В каждом участке производится вычисление координат точек и их зашифровка в массив L. При этом 1 — 11-ый разряды ячейки массива L отведены под дробную часть координаты у; 12—22-ой разряды — под дробную часть коорди¬наты х; в следующих 23—30 разрядах находится целая часть координаты г/; в 31—36-ом разрядах — целая часть координаты х. Присутствие единицы в 45-ом разряде означает, что данная точка принадлежит изолинии, выходящей на границу области Dk (признак замкнутости). Такая структура элементов массива L позволяет значительно упростить алгоритм сопряжения изолиний путем сравнения между собой только граничных узлов изолиний. Для того чтобы не образовывать нового массива L' при сопряжении различных подобластей Dk, в ячейку, хранящую признак замкнутости изолинии, засылают также признак неполноты линии (е44 =1 — линия неполна слева, е43 = 1 — линия неполна справа), а также адрес начала в массиве L продолжающей изолинии. Процесс сопряжения изолиний сводится к упорядоченной выборке отрезков изолиний массива L и построения по ним полной аппроксимирующей линии. Рассмотрим параметры, участвующие в построении аппроксимирующей линии. При построении визуально гладкой линии существенное значение имеет шаг ломаной DS. Обозначив через R радиус кривизны кривой линии, для малых Dj имеем (см. рис. 1) DS = R Dj, (2), откуда DS £ ÖRd. Это выражение позволяет оптимальным образом строить ви-зуально гладкую ломаную для данной кривой, если известна оценка ее кривизны. В зависимости от того, замкнута изолиния или нет, полна или неполна, алгоритмом предусмотрено пять различных возможностей построения аппроксимирующей кривой. Для построения гладкой кривой достаточно в каждом узле задать касательную к ней. Касательная вполне определяет не¬который класс аппроксимирующих кривых, удовлетворяющий требованиям устойчивости в смысле локальной зависимости на множестве всех узлов. Наклон касательной в узле определяется только одной предыдущей и одной последующей точками. В блоке аппроксимации все вычисления ведутся в подвижной системе координат, у которой ось ох совпадает с одной из сторон ломаной. Третье требование устойчивости — минимальность числа экстремумов кривой между двумя узлами — еще более сужает класс аппроксимирующих кривых и позволяет обосновать выбор аналитического выражения отрезка кривой. Нами был рассмотрен многочлен из показательных функций следующего вида: Этот многочлен, как можно видеть, имеет на отрезке [0, d] только один экстремум и, следовательно, удовлетворяет требованию устойчивости. Функция (3) удовлетворяет также граничным условиям: в точках х = 0 и х = d они обращаются в нуль, а их производные принимают значения у' (0) и у' (d). По изложенному выше алгоритму составлена программа для ЭВМ БЭСМ-4. Счет и выдача на перфорацию четырнадцати изо¬линий с шагом 1 мГл на области 16 X 16 занимает не более 5 мин. Рис. 3. Пример автоматического построения карт изолиний. Карта вычерченная: а — на устройстве «Атлас», б — на автономном АПГ. Пример построения карт изолиний показан на рис. 3, б. Для сравнения дается карта, построенная на устройстве «Атлас» (рис. 3, а). Список литературы 1. Автоматические построители графиков. М., «Энергия», 1969. Авт. В. Г. Гиленко, JI. А. Меланченко. 2. Б а с Р. Г., Дядюра В. А., Старостей к о В. И. Алго¬ритм автоматического построения геофизических карт по значениям поля в произвольных точках плоскости. «Докл. АН УССР», 1970, № 9. 3. Дядюра В. А., Будняк А. А., Петренко А. И. Авто¬матическое построение геофизических карт и графиков. — В кн.: Геофизиче¬ские исследования на Украине. Киев, «Техника», 1969. 4. Моделирование на ЭВМ обработки геолого-геофизическнх полей. СО АН СССР, Новосибирск. Ин-т геологии и геофизики СО АН СССР, 1970. Авт.: В. А. Головкин, Н. А. Клемберг, К. А. Шемякина и др. Пк^Крамак В. С., Перфильев Л. Г. Математическое обеспе-ченийустройства графического вывода результатов из ЭВМ.—«Экспресс- информация, № 47. Сер. Региональная, разведочная и промысловая геофи¬зика». М., ОНТИ ВИЭМС, 1970.