如何在 MATLAB 中识别多个相交的多边形？

Question

我正在尝试识别 overlapping/intersecting 多边形。我发现的技术一次只能比较两个多边形。我在数据集中有数万个单元格，每个单元格中有 2-20 个多边形，每个多边形由 x-y 坐标描述。我想在每个单元格中找到重叠的多边形。在每对之间循环检查交叉点非常慢，所以我想问...

有没有办法同时比较所有多边形并提取重叠的 ID？

这是数据集中单个条目的简单示例：

shapes = cell(4,2);
shapes{1,1} = 'poly1';
shapes{2,1} = 'poly2';
shapes{3,1} = 'poly3';
shapes{4,1} = 'poly4';
shapes{1,2} = [1, 3, 3; 1, 1, 3]';
shapes{2,2} = [2, 4, 2; 2, 2, 5]';
shapes{3,2} = [4, 5, 5, 4; 3, 3, 5, 5]';
shapes{4,2} = [1, 3, 3, 1; 4, 4, 6, 6]';

此示例包含这 4 个多边形：

这个图是用单独的 'polyshape' 对象制作的，但这并不意味着我需要在解决方案中使用这种对象。

我想要的输出是每个重叠对的记录：

result =
  2×2 cell array
    {'poly1'}    {'poly2'}
    {'poly2'}    {'poly4'}

P.S。我当前的方法是遍历每一对，并在该对的每个多边形上使用 poly2mask 函数。然后使用 & 运算符将二进制掩码加在一起。这会在有任何重叠的地方生成一个 1 的逻辑数组。

P.P.S。我看到的实际多边形都是环形扇区，因此它们并不都是凸面

Answer 1

这是一个使用 'polyshape' 向量并避免在额外循环中进行所有这些成对比较的解决方案（尽管我不知道 'overlap' 函数是如何工作的）。

% Set up empty vector to hold the different shapes
polyvec = [];

% Loop all shapes and combine into polyshape vector
for ii = 1 : size(shapes, 1)

    poly = polyshape(shapes{ii,2}(:,1), shapes{ii,2}(:,2));

    % When you combine polyshape objects together the you get 
    % a vector that is of the polyshape object type
    polyvec = [polyvec, poly];

end

% Use the overlap function to compute a symmetric binary matrix 
% of which polygons in the polygon vector overlap. 
interMatSym = overlaps(polyvec);

% I only need the upper triangle of the symmetric interaction 
% matrix and all polygons overlap with themselves so use 'triu'
interMat = triu(overlaps(polyvec), 1);

% Find the coordinates of the overlap in the interaction matrix
[x, y] = find(interMat);

% Save the result
result = [shapes(x,1), shapes(y,1)];

result =
  2×2 cell array
    {'poly1'}    {'poly2'}
    {'poly2'}    {'poly4'}

如果有更有效地创建 polyshpae 向量的方法，我很想知道！

如何在 MATLAB 中识别多个相交的多边形？

How to identify multiple intersecting polygons in MATLAB?

matlab

geometry

polygon

intersection

overlap