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

В работе рассмотрены два подхода к разделению триагулированной многосвязной области на связные подобласти без ветвления внутренних границ.
Предложен модифицированный алгоритм построения графа Риба для определения топологии триангулированной поверхности трехмерной области. На основе разделения графа Риба выполняется формирование подобластей триангуляции без ветвления внутренних границ.
В основе другого подхода лежит формирование упорядоченного множества слоев – подмножеств 3-симплексов триангуляции, использующих ее топологические свойства, такие как связность по вершинам и граням. По построению слои не содержат ветвлений внутренних границ. Вместе с тем, для многосвязных расчетных областей характерно получение несвязных слоев. Разработан алгоритм объединения слоев в связные подобласти триангуляции на основе графа подслоев, вершины которого соответствуют связным компонентам дуального графа каждого слоя. Таким образом, объединение слоев сводится к объединению вершин и ребер графа подслоев — задаче много меньшей размерности, отображению разделения графа подслоев на триангуляцию.
Для предложенных алгоритмов проведено сравнение при разделении триангулированных многосвязных областей, имеющих поверхности разного типа и рода. Приведены оценки сложности алгоритмов и проведено сравнение качества разделения по числу 2-симплексов, общих для полученных подобластей триангуляции.