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

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

ОГС = {F, E}.

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

e_ij = (f_i, f_j, , ),

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

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

а) б)

Рисунок 2.1

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

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

Рисунок 2.2[2]

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

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

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

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

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

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

3) определяется значение 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.

Для объекта производства строится ОГС ОП. Для распознаваемого КТЭ строится ОГС КТЭ. Одну из вершин ОГС КТЭ, , следует ассоциировать с какой-либо вершиной ОГС ОП, . Типы ассоциируемых вершин должны быть одинаковы: . Далее выполняется проверка конфликтов. При этом функция f(a,b) не просто существование ребра из a в b, а существование ребра с определенными типами смежности и вложенности. То есть, из вершины , ассоциируемой с вершиной должны исходить такие же ребра, как из вершины , с таким же типом смежности и вложенности.