私は三角形のセットを持っています。一緒に結合されたときに凸包を構成するこれらの三角形のすべての組み合わせを見つける方法を探しています。凸包は空でなければなりません。エッジのみの凸包内にポイントはありません。また、辺を共有する三角形のみを結合できます。組合に隙間はありません。
例:次の点は 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));
最大の凸包を探しているので、凸包にはできるだけ多くの三角形が含まれている必要があります。しかし、考えられるすべての組み合わせがあれば、三角形の少ない組み合わせを簡単に除外できます。上記の例では、最終的にこれらの 6 つの凸包になるはずです。
私は、すべての三角形に最大で 3 つの隣接する三角形 (各辺に 1 つ) があることを使用する必要があると推測しています。そして、交点で角度の合計が 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 度) という特殊なケースをどのように説明すればよいかわかりません。