Файл: Оперативные графические системы в автоматизации проектирования..pdf

Использование древовидной структуры для организа­ ции массива команд отображения является эффективным с точки зрения расхода памяти п позволяет объединить две структуры в одну. При этом структура обладает до­ статочной гибкостью для проведения быстрых преобразо­ ваний п хорошей компактностью, что позволяет использо­ вать ее для поддержания изображения на экране ЭЛТ.

В качестве примера рассмотрим способ построения массива команд отображения электронной схемы с по­

одного звена можно организовать в виде дерева, приве­ денного на рис. 6.30,s. Тогда для начертания 3-звеиного фильтра можно три раза использовать определение од­ ного звена с различными начальными точками вычерчи­ вания. Древовидная структура, определяющая RC фильтр, может быть представлена в памяти так, как это показано на рис. 6.31. Такое представление позволяет эффективно производить различные манипуляции с изо­ бражением. Так, для вычерчивания фильтра в другом месте экрана достаточно изменить координаты начальной точки только в первой команде массива. В том случае, если необходимо производить манипуляции в одном зве­ не фильтра (стирание, изменение размеров и типа эле­ ментов и т. д.), не изменяя других звеньев, требуется раз­ множить массив команд отображения звена фильтра.

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

Определение иерархической структуры. Иерархиче­ ская организация данных является многоуровневой структурой, построенной с помощью списков. В такой структуре от элементов списка может быть сделан пере­ ход к любым другим логически связанным элементам, которые в свою очередь объединены в список и связаны с родственными элементами другого списка и т. д.

Иерархическая структура может быть описана с по­ мощью направленного конечного графа, содержащего

200

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

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

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

Рассмотрим возможную структуру для представления треугольника (рис. 6.32, а). Структура, изображенная на рис. 6.32,6, образуется из элементов, которые можно разделить на понятия классов (треугольники, прямые, точки и т. д.) и собственно элементов, являющихся чле­ нами данного класса (треугольник Т\, прямые Пр 1, Пр2, ПрЗ, точки А, В, С).

Элементы, составляющие данный класс, объединяют­ ся в список, причем каждый элемент может быть связан как с элементами, определяющими его и расположенны­ ми на более низком уровне, так и с элементами, которые он сам определяет, находящимися выше данного элемен­ та в структуре. Так, прямая связана с точками, которые составляют начало и конец ее, п треугольником, в состав которого входит данная прямая. Аналогично точка сое­ динена в структуре со всеми прямыми, исходящими пз данной точки.

Для более эффективной обработки рассмотренной структуры целесообразнее несколько видоизменить ее. Объединим в список элементы, образующие классы, а все списки структуры преобразуем в кольца, включив в элементы дополнительные связи. На рис. 6.33 представ­ лена полученная структура, описанная направленным графом.

202

ва

Рис. 6.32. Пример иерархической структуры: а — чертеж треугольни­ ка; б — представление иерархической структуры изображения тре­

угольника

Рис. 6.33, Граф иерархической структуры

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

Введение в структуру колец хотя и увеличивает рас­ ход памяти для хранения структуры по сравнению с дре-

АВреса связи

Рис. 6.34. Блок вершимы иерархическом

Информация структуры

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

Представление иерархической структуры в памяти. Вершины графа, отражающие элементы иерархической структуры, могут представляться в памяти в виде До­ словных блоков с полями, в которых содержится инфор­ мация и адреса связи, указывающие на другие блоки (рис. 6.34). В представленной на рис. 6.32, б структуре связи между элементами одного класса, а также элемен­ тами данного уровня н элементами более низкого (связь «вниз») и более высокого уровней (связь «вверх») вы­ полняются по-разному. Так как прямая всегда содержит только две точки, связь «вниз» может быть достаточно просто отражена с помощью 2-словиого блока, в котором размещаются адреса связи, указывающие на блоки то­ чек (рис. 6.35, а). Однако точка может принадлежать более чем одной прямой, например точка А на рис. 6.32, а, поэтому связь «вверх» должна быть выполнена в виде списка блоков (рис. 6.35,6).

204

Использование иерархических структур в оператив­ ных графических системах. Иерархические структуры об­ ладают универсальностью и гибкостью, позволяют хра­ нить большое количество данных и отражать сложные взаимоотношения между ними. Они способны быстро реагировать на все изменения, вносимые в структуру, наиболее полно удовлетворяют требованиям, предъявляе­ мым к структуре, отображающей математическую мо­ дель объекта, в оперативных графических системах.

А

В

6

Рис. 6.35. Организация связи между элементами иерархической струк­ туры: а, б — связь «вниз» и «вверх»

За последнее десятилетие разработано большое число программных пакетов для создания и модификации структур данных. С их помощью можно достаточно эф­ фективно организовать списочные структуры, обладаю­ щие большой сложностью [16—24].

В качестве примера рассмотрим применение двух та­ ких пакетов: AED (Algol Extended for Design) и ASP (Associative Structure Package) для создания матема­ тической модели электронной схемы. Полученная при этом структура является достаточно полной и содержит в своем составе все необходимые признаки для про­ грамм анализа электронных схем.

Комплекс программ, написанный на языке AED, по­ зволяет пнженеру-проектировщпку в оперативном режи­

205