2.3.Обработка топологических отношений

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

На основании полученных выше выводов примем решение о том, что расположение элементов в кольцевых структурах F(S) или F(A) будет соответствовать их перечислению в направлении обхода против движения часовой стрелки при взгляде на грань снаружи от моделируемого объекта. Вполне логичным будет желание упорядочить другие топологические отношения, представляя их также кольцевыми структурами с обходом входящих в них элементов против движения часовой стрелки при рассмотрении с наружной стороны объекта. Подобный вывод может быть получен при необходимости упорядочения характеристик плоского («планарного») графа (рис.2.7), вершины которого соответствуют вершинам моделируемого многогранника (рис.2.1), дуги - ребрам, элементарные циклы - граням. Топологические элементы моделируемого объекта (рис.2.1) представлены в графе в окружностях, а линии, их соединяющие отображают отношение принадлежности. Линии, выделенные толщиной, соответствуют ребрам объекта. Следует отметить определенную условность используемого названия «планарный» граф. Наружная поверхность трехмерного объекта может быть представлена только разверткой, поэтому в представленном изображении невидимая грань f6 повторяется четыре раза и она находится вне пределов видимых граней.

Кольцевая структура для трех и более элементов единственным образом определяет порядок следования, то есть для каждого элемента структуры предшествующий и последующий элементы будут различными. В бинарных структурах A(S) и A(F) любой элемент будет и предшествующим и последующим одновременно. Для устранения этой неопределенности введем еще одно ограничение на структуры данных трехмерной модели:

при одновременном присутствии в модели отношений A(S) и A(F), в последних первой должна указываться грань, для которой принятое размещение вершин в A(S) для данного ребра соответствует направлению обхода контура грани.

Упорядоченные топологические отношения для модели объекта (рис.2.1) с учетом всего вышесказанного представлены в табл.2.3.

Табл.2.3.Упорядоченные топологические отношения для моделируемого объекта

S

S

A

F

s1

s2

s5

s4

a1

a6

a11

f1

f2

f6

s2

s1

s7

s3

s5

a1

a7

a4

a9

f1

f3

f4

f2

s3

s2

s7

s6

s5

a12

a4

a10

a2

f3

f5

f7

f4

s4

s7

s1

s6

a5

a11

a8

f1

f6

f5

s5

s1

s2

s3

s6

a9

a12

a3

a6

f2

f4

f7

f6

s6

s3

s4

s5

a2

s8

s3

f5

f6

f7

s7

s3

s2

s4

a10

a7

a5

f1

f5

f3

A

S

A

F

a1

s1

s2

a6

a11

a7

a4

a9

f2

f1

a2

s3

s6

a12

a4

a10

a8

a3

f7

f5

a3

s5

s6

a6

a9

12

a2

a8

f6

f7

a4

s2

s3

a10

a2

a12

a9

a1

a7

f4

f3

a5

s4

s7

a10

a7

a11

a8

f1

f5

a6

s1

s5

a11

a1

a9

a12

a3

f6

f2

a7

s2

s7

a5

a10

a4

a9

a1

f3

f1

a8

s4

s6

a5

a11

a3

a2

f5

f6

a9

s2

s5

a12

a3

a6

a1

a7

a4

f2

f4

A10

s3

s7

a2

a12

a4

a7

a5

f5

f3

A11

s1

s4

a1

a6

a8

a5

f1

f6

A12

s3

s5

a4

a10

a2

a3

a6

a9

f4

f7

F

S

A

F

f1

s2

s1

s4

s7

a1

a11

a5

a7

f2

f6

f5

f3

f2

s1

s2

s5

a1

a9

a6

f4

f6

f1

f3

s3

s2

s7

a4

a7

a10

f1

f5

f4

f4

s2

s3

s5

a4

a12

a9

f3

f7

f2

f5

s6

s3

s7

s4

a2

a10

a5

a8

f7

f3

f1

f6

f6

s5

s6

s4

s1

a3

a8

a11

a6

f5

f1

f2

f7

f7

s3

s6

s5

a2

a3

a12

f6

f4

f5

Равнозначность элемен­тов кольцевых структур, осно­ванная на наличии между ними только отношения следования, приводит к эквивалентности следующих представлений одного и того же упорядоченного топологического отношения в табличной форме. Например, для отношения f1(S)возможны следующие варианты представления:

f1(S) = {s2,s1,s4,s7}; f1(S) = {s1,s4,s7,s2}; f1(S) = {s4,s7,s2,s1}; f1(S) = {s7,s2,s1,s4}.(2.12)

Упорядоченность включенных в табл.2.3 топологических отношений для объекта, показанного на рис.2.1, связана прежде всего с необходимостью представления этих данных в виде кольцевых структур, когда речь идет о любом топологическом отношении для какого-либо элемента, например f1(S) илиa2(A). Объединение всех однотипных топологических отношений в составе геометрической модели возможно, например, в виде линейной списковой структуры, элементы которой должны включать два указателя. Один связан с последующим элементом линейного списка, а второй – с текущим элементом кольцевого списка. Такое представление обеспечивает абсолютную независимость кольцевых структур друг от друга и от линейного списка, объединяющего их. Топологические отношения в виде линейных и кольцевых списковых структур с выбором текущих элементов для последних в соответствии с данными табл.2.3 представлены на рис.2.8.

Показанное на рисунке решение, конечно, не является единственным, так как соединение однотипных кольцевых структур может быть и иным. Оптимальное решение для структуры данных трехмерной геометрической модели, очевидно, заключается не в формировании, например, для F(A) той или иной совокупности кольцевых («двумерных») структур, страдающей избыточностью информации и отсутствием связей между отдельными гранями, а в разработке сферических («трехмерных») структур. Необходимость такого подхода регламентируется международным“Стандартом на обмен данных об изделиях –STEP”.

Количество элементов кольцевых структур всех топологических отношений, за исключением A(S) иA(F),является произвольным, но не менее трех. Это является причиной частого использования постоянных по своему количественному составу структурA(S) иA(F) в трехмерном геометрическом моделировании. Как один из возможных вариантов это указано в (2.11).

Следует обратить внимание на то, что отношения S(S), S(A) иS(F) содержат оди­наковое количество элементов в кольцевых структурах для одного и того же топологического элемента. Например, кольцевые структуры для отношенийs2(S), s2(A) и s2(F) содержат по четыре элемента. Это же относится и к отношениямF(S), F(A) и F(F). Выводы, сле­дующие из этого очевидного геометрического факта, и полу­чаемые решения по дальнейшему формирова­нию структур данных трехмер­ных геометрических моделей будут обсуждены ниже как один из способов приближения к стандартуSTEP.

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

Рис.2.9 показывает возмож­ность преобразования одного то­по­логического отношения в дру­гое. Исходя из минимального объ­ема требуемых данных для трех­мерной модели (2.11), закономерен вывод о необходимости разра­ботки алгорит­мов более сложных преобразований, когда требуемое топологическое от­ношение будет получено на основа­нии двух дру­гих. Приведенная в табл.2.4 нумерация алгоритмов этих преобразований введена для удобства обозначения описываемых далее алго­ритмов.

Табл.2.4.Нумерация алгоритмов взаимного преобразования структур данных трехмерных геометрических моделей

Исходные структуры	Получаемые структуры
	S(S)	S(A)	S(F)	A(S)	A(A)	A(F)	F(S)	F(A)	F(F)
S(A)	1			2	3
S(F)	4						5		6
F(S)	7		8						9
F(A)					10	11			12
S(A)+S(F)						13		14
S(A)+A(F)			15				16	17	18
S(A)+F(S)						19		20
S(A)+F(A)			21				22
S(F)+A(S)		23			24	25		26
S(F)+A(F)		27		28	29			30
S(F)+F(A)		31		32
A(S)+A(F)	33	34	35		36		37	38	39
A(S)+F(S)		40			41	42		43
A(S)+F(A)	44	45	46				47
A(F)+F(S)		48		49	50			51
F(S)+F(A)		52		53

На рис.2.10 показаны все требуемые преобразования струк­тур топологических отношений для каждого из вариантов данных мо­дели со­гласно (2.11).

Используемые в рис.2.10 исходные топологические отношения моделей выделены.

Рассмотрим получение всех топологических отношений для модели, структуры данных которой содержатS(F) и F(A) (рис.2.10,ж).

Алгоритм 4- преобразование S(F) в S(S) на примере получения s2(S).

Вструктуре s2(F)f1 следует после f2 (рис.2.12,а), а s1(F) - структура, в которой f1 следует до f2, следовательно s1 становится очередным элементом структуры s2(S) рис.2.12,б).

В структуре s2(F) f3следует послеf1 (рис.2.12,а), а s7(F) - структура, в которойf3следует доf1, следовательноs7становится очередным элементом структуры s2(S) рис.2.12,в).

В структуре s2(F) f4 следует после f3 (рис.2.12,а), а s3(F) - структура, в которой f4 следует до f3, следовательно s3 становится очередным элементом структуры s2(S) рис.2.12,г).

В структуре s2(F) f2 следует после f4 (рис.2.12,а), а s5(F) - структура, в которой f2 следует до f4, следовательно s5 становится очередным элементом структуры s2(S) рис.2.12,д).

В структуре s2(F) f1 следует после f2, а s1(F) - структура, в которой f1 следует до f2, следовательно s1 становится очередным элементом структуры s2(S), но s1 уже есть в этой структуре, следовательно, процесс определения структуры отношения s2(S) закончен (рис.2.12,е). Элементы f1, f2, f3 и f4 кольцевой структуры s2(F) (рис.2.12,ж) рассмотрены в порядке их обхода.

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

Circ = data type [t:type] is create, element, change, delete, size, insert

Описание

Кольцевые списки circ – изменяемые однонаправленные кольцевые списки элементов t. Операции delete и insert модифицируют списки. Кольцевой список имеет заголовочную часть, содержащую имя списка и ссылку на текущий элемент списка.

Операции

create = proc(name:string) returns (circ[t])

Effects возвращает новый, пустой кольцевой список с именем name

element = proc (r:circ[t]) returns (t)

Requires r создан и не пуст

Effects возвращает текущий элемент кольцевого списка

name = proc (r:circ[t]) returns (string)

Requires r создан

Effects возвращает имя кольцевого списка

change = proc (r:circ[t])

Requires r создан и не пуст

Effects переустанавливает ссылку заголовочной части на следующий элемент кольцевого списка r, который становится текущим

is_in = proc (r:circ[t], x:t) returns(bool)

Requires r создан и не пуст

Effects возвращает значение true, если r содержит элемент равный x, в противном случае возвращает значение false

delete = proc (r:circ[t])

Requires r создан и не пуст

Effects удаляет текущий элемент кольцевого списка r и переустанавливает ссылку заголовочной части на следующий после удаляемого элемент

insert = proc (r:circ[t], x:t)

Requires r создан

Modifies r

Effects вставляет x в r перед текущим элементом и переустанавливает ссылку заголовочной части на элемент, следующий после x

size = proc (r:circ[t]) returns (int)

Requires r создан

Effects возвращает число элементов кольцевого списка r, если он пуст, то возвращает 0

End circ

Представим топологическое отношение S(F)в форме кольцевых списочных структур (рис.2.13). Алгоритм преобразованияS(F) в S(S) может быть представлен следующей процедурной спецификацией.

transformation_S(F)_in_S(S) = proc(S_F:circ[circ[string]]) returns(S_S:circ[circ[string]])

requires

modifies

effects S_S = create(S(S)); r = create( ); s = create( ); b = size(S_F);

цикличное выполнение b раз

r = element (S_F); t = create(name(r));

цикличное выполнение size(r) раз

a1 = element (r); change (r); a2 = element (r); a = 0;

цикличное выполнение b-1 раз

change(S_F);

если a = 0, то

s = element (S_F);

если (is_in (s, a1) и is_in (s, a2)),то

a = 1; insert (t, name(s));

insert (S_S, t); change (S_F); change (S_F);

Алгоритм 5- преобразованиеS(F)вF(S)на примере полученияf1(S).

Среди всех отношений S(F)первым, в котором присутствуетf1, являетсяs1(F), следовательно,s1первым попадает в структуру отношенияf1(S).Дальнейшие действия носят чисто алгоритмический характер.

В структуре s1(F) f1 следует после f6, а s4(F) - структура, в которой f1 следует до f6, следовательно s4 становится очередным элементом структуры f1(S).

В структуре s4(F) f1 следует после f5, а s7(F) - структура, в которой f1 следует до f5, следовательно s7 становится очередным элементом структуры f1(S).

В структуре s7(F) f1 следует после f3, а s2(F) - структура, в которой f1 следует до f3, следовательно s2 становится очередным элементом структуры f1(S).

В структуре s2(F) f1следует послеf2, аs1(F)- структура, в которойf1следует доf2, следовательноs1становится очередным элементом структурыf1(S),но он уже есть в этой структуре, следовательно, процесс определения структуры отношенияf1(S)закончен.

Алгоритм 6 - преобразование S(F) в F(F) на примере получения f1(F).

Среди всех отношений S(F)первым, в котором присутствуетf1, являетсяs1(F),следовательно, с него начнется определение структуры отношенияf1(S).

В структуре s1(F) f1следует послеf6, аs4(F)- структура, в которойf1следует доf6, следовательноf6становится очередным элементом структурыf1(F).

В структуре s4(F) f1 следует после f5, а s7(F) - структура, в которой f1 следует до f5, следовательно f5 становится очередным элементом структуры f1(F).

В структуре s7(F) f1 следует после f3, а s2(F) - структура, в которой f1 следует до f3, следовательно f3 становится очередным элементом структуры f1(F).

В структуре s2(F) f1 следует после f2, а s1(F) - структура, в которой f1 следует до f2, следовательно f2 становится очередным элементом структуры f1(F).

В структуре s1(F) f1следует послеf6, аs4(F)- структура, в которойf1следует доf6, следовательноf6становится очередным элементом структурыf1(F),но он уже есть в этой структуре, следовательно, процесс определения структуры отношения f1(F) закончен.

Алгоритм 10 - преобразование F(A) в A(A) на примере получения a4(A).

Среди всех отношений F(A)первым, в котором присутствуетa4,являетсяf3(A),следовательно с него начнется определение структуры отношенияa4(A).

f3(A) - структура, в которой a10 следует до a4, тогда a10 становится очередным элементом структуры a4(A).

f5(A) - структура, в которой a2 следует до a10, тогда a2 становится очередным элементом структуры a4(A).

f7(A) - структура, в которой a12 следует до a2, тогда a12 становится очередным элементом структуры a4(A).

f4(A) - структура, в которой a4 следует до a12, тогда a4 становится очередным элементом структуры a4(A), но он не может быть занесен, так как для него создается структура a4(A).

f4(A) - структура, в которой a9 следует до a4, тогда a9 становится очередным элементом структуры a4(A).

f2(A) - структура, в которой a1 следует до a9, тогда a1 становится очередным элементом структуры a4(A).

f1(A) - структура, в которой a7 следует до a1, тогда a7 становится очередным элементом структуры a4(A).

f3(A) - структура, в которой a4 следует до a1, тогда a4 становится очередным элементом структуры a4(A), но он не может быть занесен, так как для него создается структура a4(A).

f3(A) - структура, в которой a10 следует до a4, тогда a10 становится очередным элементом структуры a4(A), но он уже есть в этой структуре, следовательно, процесс определения структуры отношения a4(A) закончен.

Алгоритм 11 - преобразование F(A) в A(F) на примере получения a1(F).

В структуре f1(A) имеется элемент a1, следовательно f1 становится очередным элементом структуры a1(F).

В структуре f2(A) имеется элемент a1, следовательно f2 становится очередным элементом структуры a1(F).

Алгоритм 12 - преобразование F(A) в F(F) на примере получения f1(F).

В структуре f1(A) имеется a1 и f2(A) - структура, также имеющая a1, следовательно f2 становится очередным элементом структуры f1(F).

В структуре f1(A) имеется a11 и f6(A) - структура, также имеющая a11, следовательно f6 становится очередным элементом структуры f1(F).

В структуре f1(A)имеетсяa5иf5(A)- структура, также имеющаяa5, следовательноf5становится очередным элементом структурыf1(F).

В структуре f1(A) имеется a7 и f3(A) - структура, также имеющая a7, следовательно f3 становится очередным элементом структуры f1(F).

В структуре f1(A)имеетсяa1иf2(A)- структура, также имеющаяa1, следовательноf2становится очередным элементом структурыf1(F),но он уже есть в этой структуре, следовательно, процесс определения структуры отношенияf1(F)закончен. Элементыa1,a11,a5иa7кольцевой структурыf1(A)рассмотрены в порядке их обхода.

Алгоритм 31 - преобразование S(F) и F(A) в S(A) на примере получения s2(A).

В структуре s2(F) f1 следует после f2, а f1(A) и f2(A) имеют общее ребро a1, следовательно a1 становится очередным элементом структуры s2(A).

В структуре s2(F) f3 следует после f1, а f3(A) и f1(A) имеют общее ребро a7, следовательно a7 становится очередным элементом структуры s2(A).

В структуре s2(F) f4 следует после f3, а f4(A) и f3(A) имеют общее ребро a4, следовательно a4 становится очередным элементом структуры s2(A).

В структуре s2(F) f2 следует после f4, а f2(A) и f4(A) имеют общее ребро a9, следовательно a9 становится очередным элементом структуры s2(A).

В структуре s2(F) f1 следует после f2, а f1(A) и f2(A) имеют общее ребро a1, следовательно a1 становится очередным элементом структуры s2(A), но он уже есть в этой структуре, следовательно, процесс определения структуры отношения s2(A) закончен. Элементы f1, f2, f3 и f4 кольцевой структуры s2(F) рассмотрены в порядке их обхода.

Алгоритм 32 - преобразование S(F) и F(A) в A(S) на примере получения a1(S).

f1(A) и f2(A) имеют общее ребро a1, а s1(F) и s2(F) имеют общую пару граней f1 и f2, следовательно s1 и s2 становятся элементами структуры a1(S).

53 алгоритма (табл.2.4), требуемых для реализации взаимных преобразований топологических отношений в соответствии с минимальным составом геометрических моделей (2.11), могут быть сведены к гораздо меньшему количеству, если:

• топологические отношения представить многоуровневыми кольцевыми списочными структурами (рис.2.14);

• требование упорядоченности ввести не только для элементов одного отношения, а для всех уровней получаемых структур.

Использование таких представлений позволяет:

• из отношения S(A, F, S) сразу выделять отношения S(A), S(F), S(S), а из F(A, S, F) – F(A), F(S), F(F);

• формировать отношения S(A, F, S) и F(A, S, F) из отношений A(S, F);

• использовать отношения A(S, F) или A(S) и A(F), обладающих постоянством количества входящих в них элементов, в качестве минимально возможной топологической компоненты трехмерных геометрических моделей сплошных объектов.

Многоуровневое топологическое отношение S(A, F, S) для модели (рис.2.1) требует присутствия 82 топологических элементов, аналогичный показатель связан с использованиемF(A, S, F), тогда какA(S, F) содержит только 60 элементов для той же модели. Это является еще одним аргументом в пользу использования в трехмерных геометрических моделях отношенийA(S, F).