формирования матрицы инцидентности ребер циклам;

исследования содержания внутренней области цикла с удалением ложных ребер из массива описания оригинала;

триангуляции грани, ограниченной многоугольником;

распознавания простейших объемных тел по их проекциям на основании ассоциаций.

Формирование указанной информации выполняется алгоритмами, которые являются вспомогательными по отношению к основному, реализующему процесс анализа чертежа.

Рис. 41. Объект чтения чертежа

Описание основного алгоритма

Пусть относительно чертежа некоторого объекта (рис. 41) известны исходные данные, необходимые для работы алгоритмов чтения чертежа. Списки 1, 2, 3 описывают каждый проекцию чертежа. Обратимся к списку. 1 (пусть это будет описание горизонтальной проекции I) и возьмем первую по счету точку в этом списке, например, (вообще говоря, порядок обхода списка точек проекции может быть произвольным). Относительно точки Л известны координаты ха,; У а а также метки проходящих через Л на чертеже линий (например, а, Ь). Теперь начинаем просматривать список 2, отыскивая здесь точки, абсциссы которых равны ха,- Натолкнувшись на такую точку (например, А^), определяем ее координаты на чертеже ха, Za которые вместе с координатами точки Л1 составляют координаты Ха, у а, Za некоторой возможной точки Л оригинала в пространстве. Мы говорим возможной потому, что вследствие особенностей операции проецирования и расположения оригинала в пространстве относительно плоскости проекций, две его проекции могут дать недостоверную информацию. Для устранения неоднозначностей переходим к списку 3 и по найденным ранее в списке координатам у а,; Za ищем точку, имеющую такие координаты (например, А^). Если такая точка обнаружена, то координаты х^; ух, Za точки Л в пространстве, выявленные ранее, будут перенесены в список точек оригинала. После такой процедуры, обзор списка 2 продолжается до полного его исчерпания. При этом в списке 2 может быть обнаружена точка В^{хв;, ZbJ, у которой хв = ха,- Проверка списка 3 помогает установить, что точки с координатами Уа,; Zb на третьем виде нет. Следовательно, вершины с координатами х^,; Уа,; Zb в оригинале не существует. Обзор списка 2 продолжается и после

такого решения с прежней точкой А х списка 1. Переход к очередной точке списка 1 происходит после исчерпания по обзору списка 2. Схема обсуждаемого алгоритма приведена на рис. 42.

Краткое пояснение схемы, представленной на рис. 42

Схемы алгоритмов оформляются в соответствии с действующими государственными стандартами СССР: ГОСТ 19427-74 и 19428-74. Каждый символ (блок) в схеме алгоритма характеризуется двумя координатами: буквой и цифрой. Приведем основные обозначения (рис. 42):

АО - начало процесса;

ВО - здесь у - номер ячейки массива пространственного образа; И; i2; 13 - обозначения номеров видов на комплексном чертеже, который анализируется;

СО - в ячейке кода точки с признаком i 1 высекается первый адрес где содержится код абсциссы точки, послед-

ний засылается в рабочую ячейку г^. В засылаются

(Начало)

Рис, 42. Схема осиовиого алгоритма чтения чертежа

метки прямых, инцидентных точке на рассматриваемой проекции;

DO - процедура, аналогичная СО, с той разницей, что выполняется с кодом точки списка 2. Метки прямых засылаются в рабочую ячейку г^,

ЕО - сравниваются абсциссы точек, выделенных в списках 1 и 2. В случае их равенства осуществляется переход к А2;

А2 - второй адрес ячейки с кодом точки первого списка (ордината точки) засылается в рабочую ячейку Гх,

82 - второй адрес ячейки, где хранится код ординаты точки,

засылается в г^, а метки прямых, инцидентных точке, - в ячейку г^,

С2 - осуществляется сравнение ординат у кодов списков 1 и 3;

D2 - получение управления от С2 в случае равенства ординат, засылка ординаты точки списка 1 и аппликаты точки списка 2 в рабочую ячейку г^, а ординаты точки списка 3 и ее аппликаты - в г2, Е2 - сравнение содержания ячеек и г^;

А1 - координаты (абсцисса списка 1, ордината и аппликата списка 3) засылаются в ячейку координат точек пространственного образа (йу). Метки прямых, инцидентных проекциям точки (содержание ячеек г^; г^, г^, засылаются в ячейки Ujx, cij+b соответственно;

В1 - осуществление переадресации команд засылки А1 на очередную четверку ячеек Uj массива кодов пространственного образа;

С/ - осуществление перехода к очередной точке списка 1, в случаях, когда все операции с восстановлением пространственного образа предьщущёй точки закончены;

D1 - проверка, имеются ли еще коды в списке 1; если да - управление получает СО, если нет, то задача решена и осуществляется выход из алгоритма;

Е1 - получение управления от блока ЕС в случае неравенства абсцисс и осуществление перехода к очередной точке списка 2;

Р1 - проверка наличия кодов в списке 2 по адресу, сформированному в В1. Если коды имеются, то управление получает DO. В противном случае - С1;

A3 - получение управления в случае неравенства ординат;

83 - проверка признака окончания кодов списка 3. Если

список не исчерпан, то управление получает В2 в противном случае - С1; F2 - выход из алгоритма.

Рассмотрим теперь алгоритм, формирующий матрицу смежности точек оригинала. Этот алгоритм реализует положение, лежащее в основе модели чтения чертежа; если проекции двух

точек соединены на комплексном чертеже либо совпадают на одном из видов, то эти точки соединены в пространстве .

В качестве исходных данных используются величины, выработанные в ходе автоматического восстановления пространственного образа в результате работы алгоритма (рис. 42). При этом используется информация не только о координатах точек, но и метки прямых, которым инцидентны проекции точек на чертеже (ячейки fi+i> j+i, cij+з). Для того чтобы установить, с какими точками в' пространстве соединена рассматриваемая точка оригинала, достаточно проанализировать различные точки из списка пространственного образа в паре с. рассматриваемой. Если на всех трех видах исходного чертежа у проекций рассматриваемой пары точек найдутся одинаковые метки линий, которым они инцидентны, то это равносильно выполнению приведенного выше условия.

В случае, когда проверяется i-я и-/-я точки, элементы а,-,-матрицы смежности получают значение а,-у = 1, если точки соединены; в противном случае = 0.

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

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

3. АЛГОРИТМЫ ВОССТАНОВЛЕНИЯ СТРУКТУРЫ ОРИГИНАЛА

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

Алгоритм формирования циклов, принадлежащих одной плоскости, с присвоением специальных меток

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

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

число замкнутых контуров - циклов, принадлежащих рассматриваемой плоскости;

описание циклов, включающее в себя: число вершин контура Mi, число контуров, объемлющих данный контур. Последнее число в дальнейшем фигурирует как метка и; список номеров вершин, принадлежащих М{ (номер вершины определяется ее местом в списке точек пространственного образа); порядковый номер цикла в общем списке.

Описание п^йскостей составляет массив В, в котором хранятся .коэффициенты уравнений этих плоскостей. На рис. 43 показана обобщенная схема алгоритма, в которой программные символы включают в себя достаточно простые стандартные процессы обработки информации.

Пояснение схемы, приведенной на рис. 43.

ВО - процесс состоит из шагов.

1-й шаг. Просматривается массив точек пространственного образа, выбирается очередная точка Ni.

2-й шаг. По матрице смежности ищется смежная с i-й точка (просматривается i-я строка матрицы смежности).

3-й шаг. По матрице смежности ищется смежная с /-й точка (просматривается /-я строка).

Номер очередной точки после вычисления коэффициентов плоскости, проходящей через i; /; k, выбирается так: проверяется, есть ли такая > k, причем k, смежная с /. Если имеется, то k-ik, и повторяется вычисление коэффициентов плоскости для точек i; /; k; в случае, когда нет, проверяется наличие вершины /, смежной с i-й точкой при условии > /. Повторяется процедура, аналогичная изложенной с вершиной k. Наконец, если /\ нет, то проверяется, не исчерпан ли список точек (есть ли Il > i). Если ix есть, то процесс повторяется от начала до конца; если нет - вырабатывается сигнал окончания процесса.

СО - вычисление коэффициентов уравнения плоскости, проходящей через точки i; /; k, координаты которых известны;

ЕО - проверка, позволяющая перейти от составления массива плоскостей оригинала к процессу построения М{ и и.

А2 - проверка Xi, у,; г-, очередной точки по признаку

Здесь AjBjCPj - коэффициенты /-Й плоскости из массива плоскостей оригинала.

В2 - группировка вершин, лежащих в /-Й плоскости, в цикл Ml, При этом используется матрица смежности вершин и про-

\начало)

Выбор очередной тройки смежных вершин к

Вычисление коз(рсрициенгпо6 уравнения плос-кости

r-DO

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

просмотр списка точек, принадяе-кащих плоскости

r-D2-Выделение кодов поус-ловию:У=0

F2i-

Рис. 43. Схема алгоритма формирования циклов

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

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

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

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

Алгоритм формирования матрицы инцидентности ребер циклам М{ с присвоением меток

Исходными для алгоритма являются координаты точек пространственного образа, матрица смежности вершин и массив А циклов М{. Выходом алгоритма является матрица инцидентности ребер циклам Ml (ребра рассматриваются как пары смежных точек). При этом количество циклов, инцидентных каждому ребру, выражается числом п, которое фигурирует в дальнейшем в качестве метки и ребра. В массиве ребер указаны номера циклов, инцидентных каждому ребру, что позволяет найти эти циклы в соответствующем массиве. В процессе формирования матрицы инцидентности ребер циклам могут быть выделены несколько операторов:

1) формирование ребра из пары точек, смежных в оригинале;

2) поиск циклов, инцидентных ребру;

3) формирование метки и для данного ребра.

Ограничимся краткими пояснениями этих операторов. Формирование ребер происходит просмотром для каждой i-й точки массива пространственного образа i-й строки матрицы смежности. Если выделена /-я точка, смежная с i-й, то i-я и /-я точки составляют ребро. Поиск циклов, инцидентных ребру, осуществляется сравнением номеров точек, принадлежащих ребру с номерами вершин, входящих в каждый из циклов в массиве А. В каждом случае включения точек в состав цикла формируется счетчик /дг. После окончания обзора массива циклов формируется метка

Алгоритм исследования содержания циклов

с удалением ложных ребер, вершин в М-оригинале

и нанесением меток .

Дополнительными исходными данными для алгоритма являются массивы А и В, описывающие циклы и плоскости оригинала с метками v для каждого цикла, а также матрица инцидентности ребер циклам с метками и для каждого ребра. Выходом алгоритма являются метки нанесенные в описаниях тех циклов, которые являются либо ложными гранями, либо контурами входа в углубление или отверстие, а также метки Г для П^-граней. Из исходных массивов, таким образом, можно удалить ложные ребра и. вершины. Фактически рассматриваемый алгоритм состоит из двух самостоятельных процессов: исследования содержания циклов с присвоением меток; удаления ложных ребер и вер-

шин. процесс исследования осуществляется путем перебора имеющихся в массиве циклов. Прежде всего выполняется проверка на наличие условий, которые не могут быть у цикла с меткой d (одновременное выполнение условий п = 2 и v =0, причем в отношении первого равенства достаточно выполнение его для произвольного ребра ликла). При выполнении этих условий циклу присваивается метка Г и осуществляется переход к очередному циклу (если они еще имеются).

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

Алгоритм построения сечения и анализа его графа

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

1-й фрагмент. Включает в себя оператор выбора в пространстве трех точек, определяющих положение секущей плоскости, организующей сечение. Сначала (рис. 45) выбираются ребра М-оригинала, на которых лежат определяющие точки и являются срединами этих ребер.

Первое ребро выбирается в исследуемом цикле как первое в массиве-ребер. Второе ребро выбирается также в исследуемом цикле как определяемое (К-1)-й и /С-й вершинами, начиная, от одной из вершин первого ребра (при этом К = г/2, где г - общее число вершин в цикле; если К - дробное, то округляют в большую сторону). Третье ребро выбирается тем же путем, что и второе, с той разницей, что оно принадлежит отличному от исследуемого циклу, инцидентному первому ребру. После выбора ребер вычисляются координаты их средних точек л;?; yf; zf; затем управление получает стандартная подпрограмма вычисления коэффициентов уравнения плоскости а cz xf; yf; zf, организующей сечение.

2-й фрагмент. Здесь формируется массив S точек, принадлежащих сечению М-оригинала плоскостью а. Заголовок массива включает в себя координаты точек, лежащих на первом и втором ребрах, инцидентных исследуемому циклу. Это выделение необходимо потому, что в графе сечения должны анализироваться

(на чало)

Построение цик ла при Si и Si (S,S,-точки цикла)

Выделение 1-го ребра Ri

Нет

Выделение г-го ребра Fi

N-. = 2

Выделение цикла, инцидентного ребру ri;i-Ji

3,4--

D1 -

Построение точек пересечения ребер с а

для i>N

IpEO--

Выделение очередного цикла

FO-1-

Выделение RczMsCnepBoe В массиве)

Вычисление

Выработка для проверяемого цикла сигнала

.Eh-

Вь/работка для проверяемого цикла сигнала d

Ы-ч

и^онец)

Вычисление коэффициентод в уравнении

плоскости а.

Рис. 44. Алгоритм построения сечения:

1 - счетчик циклов построения пересечений ребер; - счетчик обследованных ребер в г^, n - число подлежащих обследованию ячеек г^, где хранятся коды ребер; - обозначение исследуемого ребра с номерами циклов, инцидентных ему (строка матрицы инциденций); - счетчик ребер, направленных

в (-J.; i = 3, 4, 5.....iff, 2? - координаты точек, через

которые проходит сс (середины ребер /, 2, 3)

ЦИКЛЫ, Проходящие через точки, принадлежащие исследуемому циклу. В этот же фрагмент включен оператор построения точек пересечения ребер циклов М-оригинала с секущей плоскостью а. Оператор сводится к простым операциям входящих в процесс решения систем линейных уравнений. 3-й фрагмент. Включает в себя команды упорядоченного перебора циклов 7И-оригинала, предназначенных для построения во фрагменте двух элементов сечения. Перебор основан на последовательном исчерпывании матрицы инциденций циклов, прохо-

1-е ребро 2epeSpo

Рис. 45. Выбор ребер оригинала для организации сечения

Рис. 46. Построение анализирующей прямой l

1-е pe6i

3-е ребро

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

4-й фрагмент. Анализирует граф полученного сечения. При. этом выделяются циклы, проходящие через ребра 1 v. 2 анализируемого цикла. Если при таком анализе оказывается, что в графе сечения цикл вложен в цикл и оба они инцидентны ребру сечения, соединяющему вершины, являющиеся сечением ребер 1 и 2, то анализируемый сечением цикл является отверстием (положение 5, ситуация 1, случай а формальной модели М-оригинала). Алгоритм заканчивается присвоением меток d либо Г исследуемому циклу.

Отметим, что в данном алгоритме можно применить упрощенный способ определения факта вложения одного цикла в другой. Пусть исследуется цикл М{ и сечение проходит через первое и второе ребра этого цикла (рис. 46). Так как у ребер 1 и 2/г > 2 (по условию), то мы можем через элементы сечения, смежные элементу, который включает в себя ребра 1 и 2, провести анализирующую прямую L (ее можно провести через середины смежных с ребром 1 или 2 ребер графа сечения). Вычислив координаты точек пересечения прямой L с ребрами сечения и отнеся их к соответствующим циклам сечения, можно по расположению точек пересечения на прямой L сделать заключение о том, вложен или нет один цикл в другой. Признаком вложения будет вложение пары точек, относящихся к одному из циклов, внутрь отрезка, образованного на прямой L другой парой точек.

Алгоритм удаления ложных вершин и ребер

Как указывалось выше, основной алгоритм чтения чертежа восстанавливает наиболее полный линейный пространственный образ, намечая соединения точек оригинала там, где они могут быть, исходя из чертежа. Применение формальной модели М-оригинала позволяет удалить из его описания ложные вершины и ребра на основе информации о содержании циклов, полученной в предыдущем алгоритме. В самом деле, если к ребру подходят циклы и /г > 2, то точно два из них должны быть Сметками Г .