Согласованная триангуляция многогранников с общими гранями

[Alex Krylov]

Тут неожиданно для себя обнаружил отсутствие готового софта (по крайней мере я не нашел) для "согласованной триангуляции" (conforming triangulation) выпуклых многогранников (в $R^n$), имеющих общие грани. Цель - без добавления дополнительных вершин разбить многогранники на симплексы, при этом на общих гранях "сетки" должны совпадать. В качестве примера (чтобы было понятно, о чем речь): "Пусть два 3D-куба имеют общую грань (квадрат). Пусть это квадрат ABCD. Триангулировать этот квадрат можно двумя способами - либо с помощью диагонали BD, либо с помощью диагонали AC. Когда при триангуляции обоих кубов выбирается одна и та же диагональ, получаем "согласованную триангуляцию"".

Не знает ли кто готового (открытого) софта, где бы данная проблема была решена (мож я проглядел)... Или возможно кто-нибудь посоветует вариант наименее трудозатратного решения данной проблемы путем самого минимального/малоинвазивного "допиливания" готового софта.

[Alex Krylov]

Все гениальное просто...

На самом деле исходная задача звучит так: "Имеется выпуклый многогранник P1, внутри него находится другой выпуклый многогранник - P2. Требуется найти триангуляцию для разности P2\P1."

Оказывается, в концептуальном плане тут все очень просто.

Вот для наглядности двумерный пример. Имеется красный квадрат P1, внутрь него вложен голубой кадрат P2 (см. рис. ниже). Требуется найти триангуляцию для разности P2\P1.

Как быть? Приподнять*) голубой квадрат над красным (см. рис ниже). Найти выпуклую оболочку (ну то есть в 3D построить выпуклый многогранник, заданный вершинами). А потом грани спроецировать назад в 2D. В результате проецирования помимо искомой триангуляции также получим исходные многогранники (в нашем случае квадраты).


*) Отсюда англоязычное название данной процедуры - lifting. За счет добавления еще одной размерности, "разнесения по разным этажам" исходная невыпуклая задача становится выпуклой, появляется выпуклая интерпретация.

См. J.E. Goodman, Cell decomposition of polytopes by bending, и теоремы 3,4 там
DOI: 10.1007/BF02787218

[Alex Krylov]

И вот пример кода, осуществляющего триангуляцию P1\P2, где P1,P2 - два вложенных тетраэдра:

Используется синтаксис Matlab M

k = 4;
%Вершины тетраэдра P1
v1= [                0,                   0,                   0;...
     1.000000000000000,                   0,                   0;...
     0.875942811492984,   1.100312685796844,                   0;...
     0.358184285119867,   0.171539751648851,   2.000000000000000];
%Вершины тетраэдра P2, вложенного в P1 
v2= [0.571932608194886,   0.337094176268626,   0.585786240620734;...
     0.704699684706738,   0.042223494692337,   0.192944505224134;...
     0.437741457576473,   0.245854227348432,   0.991581476941187;...
     0.500652716967284,   0.400077739788815,   0.059571697857093];
 
v12 = [v1; v2];
v12_lifted = zeros(size(v12)+[0,1]);%Lifted vertices array

%Lifting procedure
for i = 1:size(v12, 1)
    
    if (i<=k)
    v12_lifted(i,:) = [v12(i,:),0];   
    else
    v12_lifted(i,:) = [v12(i,:),1];   
    end
    
end

K = convhulln(v12_lifted);%Находим выпуклую оболочку

%Для визуализации результатов триангуляциии использован класс Polyhedron из
%Multiparametric Toolbox 3
T1 = Polyhedron(v1);
T2 = Polyhedron(v2);
for i = 1:size(K,1)
    %Отфильтровываем (как побочный продукт) триангуляцию исходных множеств P1 и P2 
    %Оставляем только триангуляцию P1\P2
    if (~all(K(i,:)<=k))&&(~all(K(i,:)>k)) 
        T1.plot('Alpha',0.4,'Color','r');
        hold on;
        T2.plot('Alpha',0.4,'Color','c');        
        P = Polyhedron(v12_lifted(K(i,:),1:size(v12,2)));
        P.plot('Alpha',0.4,'Linewidth',2, 'Color','g','Marker','o');      
        waitforbuttonpress;
        hold off;
    end
end

Достаточно минималистично. Используется встроенная функция Matlab convhulln()

[Alex Krylov]

Цитата:

Все гениальное просто...

Но есть нюанс...

Вот пример результата работы алгоритма триангуляции, о котором говорилось выше (для тех, кто хочет знать, что это за множества изображены на картинке и откуда они взялись, см. самый конец обсуждения https://dxdy.ru/topic162168-15.html):


Видно, что множества обладают совершенно очевидной симметрией, однако, триангуляция асимметрична! Применительно к тому кругу задач, о котором говорилось в конце топика
https://dxdy.ru/topic162168-15.html, такая триангуляция не очень хороша.

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

Чтобы получить более приличный результат, надо для данных, предварительно подвергнутых "подъему/лифтингу"(!), находить не выпуклую оболочку (с побочной триангуляцией), а триангуляцию Делоне (что есть по сути еще один "лифтинг"). Затем полученную триангуляцию Делоне надо дополнительно обрабатывать (осуществить "спуск" назад), отобрав только наружные фацеты, причем не просто наружные фацеты, а те, что видны "сверху".

Вот результат триангуляции Делоне "поднятых" данных и "спущенных" назад:


Гораздо приличней выглядит.