Распознавание конструктивно-технологических элементов

ОГС можно построить для целой детали и для отдельного КТЭ. В таком случае распознать КТЭ в детали можно путем поиска ОГС КТЭ в ОГС детали. То есть задача решается как поиск подграфа в графе.

Пусть имеется два графа: граф G – основной, в котором осуществляется поиск, и граф G’ – подграф, разыскиваемый в основном. Простейший способ решения подобной задачи – последовательный перебор всех возможных отображений вершин подграфа на граф с последующей проверкой на конфликт. Отображение Г подграфа G’ в граф G не содержит конфликтов, если:

где f(a,b) ‑ отношение существования ребра из a в b.

Самый примитивный подход к поиску подграфа – простой перебор. Какая-либо вершина графа G’ ассоциируется с вершиной g_j графа G. После этого проверяются ребра: можно ли каждому ребру, выходящему из вершины , поставить в соответствие ребро графа g, выходящее из вершины G_j. Если результат проверки положителен – она (проверка) выполняется для вершин, смежных с исходной вершиной . В противном случае выбирается новая пара ассоциируемых вершин.

Приведенный пример показывает важность выбора ассоциируемых вершин (первой пары). Удачный подход к решению соответствующей задачи позволит, как минимум, сократить время. Один из способов решения заключается в том, что вершины графов сортируются в зависимости от количества ребер (входящих и выходящих). Наибольшая вершина графа G’ ассоциируется с наибольшей вершиной графа G. Если обнаружены конфликты, для ассоциирования берется следующая вершина графа G. Если количество ребер наибольшей вершины G’, превосходит очередную вершину G, процесс можно прекратить.

При сопоставлении ОГС появляются дополнительные условия, которым должны соответствовать ассоциируемые вершины. Во-первых, они должны иметь одинаковый тип, S_b, а во-вторых, ребра, соединяющие эти вершины, должны иметь одинаковые типы смежности, , и вложенности, .

Недостаток приведенного подхода – необходимость иметь ОГС практически для каждого КТЭ, как бы мало он не отличался от своих собратьев. Более эффективным является не сам ОГС КТЭ, а его шаблон и поиск в ОГС детали подграфа, соответствующего этому шаблону.

Шаблон ОГС КТЭ включает четыре основных категории: тип начальной грани, глубина поиска, тип смежности ребер и тип смежных граней.

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

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

Рисунок 3.1

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

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

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