Комбинации треугольников, образующих выпуклый корпус

Question

У меня есть набор треугольников. Я ищу способ для найти все комбинации этих треугольников, которые образуют выпуклый корпус при объединении. Выпуклая оболочка должна быть пустой, т. Е. нет точек внутри выпуклой оболочки только на ребре. И только треугольники, которые разделяют сторону, могут быть соединены вместе, т.е. никаких пробелов в союзе.

Пример: Следующие пункты дают 12 треугольников (триангуляция Делоне).

xy = [3.3735 0.7889; -0.1072 -3.4814; -3.9732 4.1955; -5 5; 5 5; 5 -5; -5 -5]; 
DT = delaunayTriangulation(xy); 
triplot(DT); 
%The coordinates for each triangle -- each row is a triangle. 
TRIX = reshape(DT.Points(DT.ConnectivityList, 1), size(DT.ConnectivityList)); 
TRIY = reshape(DT.Points(DT.ConnectivityList, 2), size(DT.ConnectivityList)); 

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

Я предполагаю, что я должен использовать, что каждый треугольник имеет не более трех соседних треугольников (по одному на каждой стороне). И что я должен проверить, равна ли сумма угла меньше или равна 180 градусам в точках пересечения. Это гарантирует, что союз выпуклый - см. Рисунок ниже. (Угол может также быть ровно на 360 градусов, если несколько треугольников образуют полный круг).

---

треугольник Углы:

% Vectors connecting points 
diffx = diff([TRIX TRIX(:,1)], [], 2); diffy = diff([TRIY TRIY(:,1)], [], 2); diffxy = [diffx(:) diffy(:)]; 
% Norm 
normxy = reshape(arrayfun(@(row) norm(diffxy(row,:)), 1:size(diffxy,1)), size(DT.ConnectivityList)); 
nominator = repmat(sum(normxy.^2, 2), 1, 3) - 2*normxy.^2; 
denominator = 2 * repmat(prod(normxy, 2), 1, 3)./normxy; 
% Angle 
tri_angle = acosd(nominator./denominator); 
tri_angle = circshift(tri_angle, [0 -1]); % Shift so the angles match the correct point. 

Я переформатировать информацию таким образом, что строки являются точками и столбцы треугольников:

n_tri = size(TRIX,1); % Number of triangles 
% Adjacency matrix connecting points (rows) with triangles (columns). 
adj_points = zeros(size(xy,1), n_tri); 
adj_angle = NaN(size(adj_points)); 
for point =1:size(xy,1) 
    idx = find(DT.ConnectivityList == point); 
    [a_tri, ~] = ind2sub(size(DT.ConnectivityList), idx); 
    adj_points(point,a_tri) = 1; 
    adj_angle(point,a_tri) = tri_angle(idx); 
end 

Я цикл по всем краям и рассчитать углы по обеим сторонам края (edges angles). Таким образом, я могу найти пары треугольников, образующих выпуклое множество (adj_convex):

DT_edges = edges(DT); % All edges in the Delaunay triangulation 
% Adjacency matrix connecting edges (rows) with triangles (columns). 
adj_edge = logical(adj_points(DT_edges(:,1),:) .* adj_points(DT_edges(:,2),:)); 

edgesangles = NaN(size(DT_edges)); 
adj = zeros(n_tri); % Adjacency matrix indicating which triangles are neighbours. 
adj_convex = zeros(n_tri); 
for edge=1:size(DT_edges,1) 
    % The angles on either side of the edge. 
    tri = adj_edge(edge,:); 
    t = adj_angle(DT_edges(edge,:), tri); 
    edgesangles(edge,:) = sum(t, 2); 
    tri_idx = find(tri); 
    adj(tri_idx,tri_idx) = 1; 
    adj_convex(tri_idx,tri_idx) = prod(edgesangles(edge,:) <= 180); 
end 
convexedges = (edgesangles <= 180); 
% Set diagonals to zero. 
adj(logical(eye(n_tri))) = 0; 
adj_convex(logical(eye(n_tri))) = 0; 

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

Answer 1

Надеется, некоторые из ваших проблем можно ответить, используя эти строки кода

выпуклости полигона

что у вас есть набор треугольников, то вы должны удалить все точки внутри этого многоугольника, т.е. сделать только посмотрите на точки на границе многоугольника. Вы можете проверить, является ли точка внутри многоугольника с помощью inpolygon функции

[in,on] = inpolygon(xq,yq,xv,yv); 

условие, что все углы должны быть менее 180 ° в этом случае я считать достаточным. Вы также можете просто создать выпуклый корпус и проверить, идентичен ли набор.Используйте convhull

K = convhull(X,Y) 

Является подмножеством большего размера?

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

x %// target polygon x 
y 
xt %// test polygon x 
yt 
in = inpolygon(x, v, xt, yt); 
if sum(in)==length(x) 
    %// target polygon is subset of testpolygon 
end 

найти все условию

Здесь я хотел бы использовать - скажем - бедных мужчин подходить. Просто перебирайте все комбинации и проверяйте выпуклость. Список всех треугольников предоставлен вам компанией DelaunayTriangulation. То есть

DT(:,:) 

дает вам все треугольники и их точки.

Триангуляция Делоне класс

Вы уже используете класс Триангуляция Делоне, почему бы не использовать методы этого класса? У вас есть в основном все, что вам нужно

1. Check if triangulation is subset of other triangulation
2. Get boundary points of triangulation.
3. Get the convex hull of a triangulation.

вам нужно больше?

Answer 2

Этот ответ может быть решен с помощью простого рекурсивного алгоритма:

1. начать с любым треугольником
2. Найти все треугольники, которые разделяют ребро с этим треугольником
3. Для каждого из этих треугольников, проверить, если это множество выпукло.
   • Стоп, если не выпуклый
   • Добавить треугольник подключен к последнему добавляются треугольник, чтобы установить, что еще должен быть проверен

Так что этот алгоритм является рекурсивным, так как он жадно пытается добавить больше треугольников к набору, пока он уже не выпуклый. Код ниже дает этот результат (я пропустил все тривиальные (1 треугольник) ответы.

Проверка, нет ли внутренних точек в выпуклой оболочке, немного наивна: постройте выпуклую оболочку и посмотрите, все ли на ней все точки.

function [convexTriangleSets,DT] = triangles() 
    % inputs 
    xy = [3.3735 0.7889; -0.1072 -3.4814; -3.9732 4.1955; -5 5; 5 5; 5 -5; -5 -5]; 
    DT = delaunayTriangulation(xy); 

    function convexTriangleSets = testAddTriangle(iTriangle,attachedTriangleIndices,includedTriangleIndices) 
     % add triangle 
     includedTriangleIndices(end+1) = iTriangle; 

     % naive test if allpoint of set of triangles are on convex hull 
     nodes = unique(DT(includedTriangleIndices,:)); 
     coords = DT.Points(nodes,:); 
     ch = convexHull(delaunayTriangulation(coords)); 
     allNodesOnConvexHull = length(nodes) == length(ch)-1; 

     if ~allNodesOnConvexHull 
      convexTriangleSets = {}; 
      return 
     end 

     % find triangles connected to iTriangle 
     currentTriangle = DT.ConnectivityList(iTriangle,:)'; 

     attachedCell = DT.edgeAttachments(currentTriangle([1 2 3]),currentTriangle([2 3 1])); 
     attachedRow = unique([attachedTriangleIndices,attachedCell{:}]); 
     attachedTriangleIndices = attachedRow(~ismember(attachedRow,includedTriangleIndices)); 

     % recursively try to expand connected triangles 
     convexTriangleSets = {sort(includedTriangleIndices)}; 
     for ii = 1:length(attachedTriangleIndices) 
      convexTriangleSets = [convexTriangleSets,... 
       testAddTriangle(attachedTriangleIndices(ii),... 
           attachedTriangleIndices,... 
           includedTriangleIndices)]; %#ok<AGROW> 
     end 
    end 

    includedTriangleIndices = []; 
    attachedTriangleIndices = []; 
    convexTriangleSets = {}; 
    for iTriangle = 1:DT.size 
     convexTriangleSets = [convexTriangleSets,... 
      testAddTriangle(iTriangle,attachedTriangleIndices,includedTriangleIndices)]; %#ok<AGROW> 
    end 

    % filter single triangles 
    convexTriangleSets(cellfun(@length,convexTriangleSets) == 1) = []; 

    % filter unique sets; convert to string because matlab cannot unique a cell array 
    [~,c] = unique(cellfun(@(x) sprintf('%d,',x),convexTriangleSets,'UniformOutput',false)); 

    convexTriangleSets = convexTriangleSets(c); 

    % plot result 
    n = ceil(sqrt(length(convexTriangleSets))); 
    for kk = 1:length(convexTriangleSets) 
     subplot(n,n,kk) 
     triplot(DT,'k') 
     hold on 
     patch('faces',DT(convexTriangleSets{kk},:), 'vertices', DT.Points, 'FaceColor','r'); 
    end 
end