CODEWITHSUNDEEP
matlabgeometrypolygonintersectionoverlap
Sam D.
Sam D.

Reputation: 72

How to identify multiple intersecting polygons in MATLAB?

I'm trying to identify overlapping/intersecting polygons. The techniques I have found only compare two polygons at a time. I have tens-of-thousands of cells in a dataset, and in each one there are 2-20 polygons, each described by x-y coordinates. I want to find the overlapping polygons in each cell. Looping between every pair to check for an intersection is very slow, so I want to ask...

Is there a way to compare all polygons at the same time and extract the IDs of those that are overlapping?

Here is a simple example of a single entry from the dataset:

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]';

This example contains these 4 polygons:

The example dataset contains these 4 polygons

This plot was made with separate 'polyshape' objects, but that doesn't mean I need to use this kind of object in the solution.

The output I would like is a record of each overlapping pair:

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

P.S. My current method is to loop through each pair and use the poly2mask function on each polygon of the pair. Then use the & operator to add the binary masks together. This produces a logical array of 1's where there is any overlap.

P.P.S. The actual polygons I am looking at are all annular sectors, therefore they are not all convex

Annular sector

Upvotes: 2

Views: 1889

Answers (1)

Sam D.
Sam D.

Reputation: 72

Here is a solution that makes use of 'polyshape' vectors and avoids making all those pairwise comparisons in extra loops (although I don't know how the 'overlap' function works). 

% 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'}

If there is a way to create a polyshpae vector any more efficiently then I'd love to know!

Upvotes: 1

Related Questions