Ориентированный граф смежности

Ориентированный граф смежности (ОГС)^[22] – граф, отражающий в упрощенном виде топологию твердотельной модели: ребра ОГС – ребра твердотельной модели, E, вершины ОГС – грани твердотельной модели:

ОГС = {F, E}.

Ребро ОГС характеризуется четырьмя свойствами:

e_ij = (f_i, f_j, , ),

где f_i, f_j – грани, между которыми расположено ребро, – тип смежности (перегиба), – признак, который для краткости назовем вложенность.

Тип смежности – определяется взаимным расположением нормалей к граням f_i, и f_j. Если точка их пересечения находится внутри тела (Рисунок 14.1 а), сочленение этих граней «выпуклое». В противном случае, если нормали пересекаются за пределами тела, (Рисунок 14.1 б) ‑ сочленение «вогнутое».

Поскольку типов смежности два (выпуклый и вогнутый) этот признак – бинарный, Î {0, 1}: если ребро выпуклое ‑ =0, если вогнутое ‑ =1.

Вложенность – признак, зависящий от того, принадлежит ли ребро e_ij внешнему контуру i -й грани или внутреннему. Например, ребро A (Рисунок 14.2) принадлежит внешнему контуру грани F, а ребро В ‑ внутреннему. Также как тип смежности, вложенность - бинарный признак: если ребро внутреннее, =1 (вложенность есть), если ребро внешнее, =0 (вложенности нет).

Следует отметить, что контур с ребром В по отношению к грани F – внутренний, а по отношению к грани F₁ – внешний. Таким образом, для ребра от F к F₁ признак =0, а для ребра от F к F₁ признак =1. Собственно, ориентированным ОГС делает именно признак «вложенность».

 

а) б)

Рисунок 14.1

Рисунок 14.2

Вершины ОГС характеризуются типом, S_b:

S_b X { C lose, B ounded, T hrough, U nbounded, O pen }.

Значение S_b для некоторой грани F_i определяется следующим образом:

определяется тип смежности каждого связанного с ней ребра ‑ (n – количество граней, смежных с гранью Fi);

определяется количество, Е, изменений типа смежности для внешнего контура грани F_i, (есть количество изменений значений в множестве Т) при обходе этого контура в одном направлении;

определяется значение S_b:

если E = 0 (признак не меняется), то S_b принимает значение либо O pen (если все ребра выпуклые), либо C lose (если все ребра вогнутые).

если E = 1 (признак меняется один раз), S_b = B ounded.

если E = 2 (признак меняется дважды), S_b = T hrough.

если E > 2 (признак более двух раз), S_b = U nbounded.

ОГС применяется для распознавания КТЭ в модели детали. С этой целью необходимо построить ее ОГС, G_дет. Создается также ОГС распознаваемого КТЭ, G_КТЭ. Задача распознавания решается как поиск в графе G_дет подграфа G_КТЭ.

Шаблоны ОГС КТЭ

Шаблон ОГС КТЭ – правило, позволяющее выделить в ОГС детали подграф, соответствующий отдельному КТЭ.

Шаблон включает четыре основных категории:

1) тип начальной грани;

2) глубина поиска;

3) тип смежности ребер;

4) тип смежных граней.

Начальная грань. В структуре каждого КТЭ можно выделить грань, которая занимает особое положение по отношению к другим. Например, в пазах, различные варианты которых приведены на рисунке 3.1, такой гранью является донышко. Формальным признаком такой грани может служить, например, максимальная степень (количество ребер). Однако в общем случае особый статус может иметь и другая грань. Выделить начальную грань должен помочь технолог, консультирующий разработчика САПР. В данном контексте следует просто полагать, что такая грань есть у каждого КТЭ и ее тип имеет важное значение при поиске подграфа КТЭ в ОГС детали.

Глубина поиска – максимальная степень смежности с начальной гранью. Как правило, рассматриваются только грани, непосредственно прилегающие к начальной и глубина поиска, соответственно, равна 1.

Рисунок 15.1

Для закрытого со всех сторон паза (рисунок 3.1 д) можно составить следующий шаблон: тип начальной грани – «С» («close»), глубина поиска – 1, тип смежности ребер – «вогнутый», тип смежных граней – «В» («bounded»). Используя приведенный шаблон программа распознавания в ОГС детали найдет закрытую грань, выделит вместе с ней все вогнуто смежные с ней грани и назовет все это КТЭ «Паз».

Шаблоны для открытого паза и уступа (рисунок 4.1 г, в) отличаются от шаблона глухого паза типом начальной грани ‑ она должна иметь тип «В» («bounded»). Между собой они никак не отличаются. Для этого в шаблоне следует предусмотреть место для особых условий. Например, открытый паз должен иметь только одно ребро с выпуклым типом смежности.

Для сквозного паза (Рисунок 15.1б) тип начальной - «t» («through»). Остальные категории шаблона аналогичны шаблонам других пазов.