how to compute intersection of union for two polygons?

I have two polygons (mat files attached), how to compute their IOU (Intersection of union)? here is the code I'm using, but it gives me a wrong values.

T1 = importdata('T1.mat');

T2 = importdata('T2.mat');

polygon1= [T1(:,1),T1(:,2)];

polygon2= [T2(:,1),T2(:,2)];

poly1 = polyshape(polygon1(:,1),polygon1(:,2));

%plot(poly1)

poly2 = polyshape(polygon2(:,1),polygon2(:,2));

hold on

%plot(poly2)

ply_inter = intersect(poly1, poly2);

area_inter = area(ply_inter);

% plot(ply_inter)

ply_union = union(poly1,poly2);

area_union = area(ply_union);

% plot(ply_union)

IoU = area_inter/area_union

[Steven Lord]

At first glance that looks right. What value are you getting for IoU and what value do you expect to get?

[Abb]

@Steven Lord it gives me 28 percent overlaping but I expect both have aroud 80 to 90 percent overlapping!

Answer 1

[John D'Errico]

T1 = importdata('T1.mat');
T2 = importdata('T2.mat');
polygon1= [T1(:,1),T1(:,2)];
plot(T1(:,1),T1(:,2),'b.')
hold on
plot(T1(:,1),T1(:,2),'r.')
hold off

And that SEEMS like the two curves are pretty much identical. They overlap almost perfectly, so that we see only one set of dots. So what is the problem?

Next, I'll draw the points given, but with a line between each consecutive pair of points, AS PROVIDED, IN THE ORDER PROVIDED.

plot(T1(:,1),T1(:,2),'b-')

Ok. That tells the complete story!

Do you understand that polyshape does NOT sort the points around the perimeter?

These two polyshapes are NOT the ones that you see in the first figure. Instead, each of those polyshapes zig-zag all over the place.

If you want the two polyshape, you would need to sort the points in an order, perhaps going either clockwise, or counter-clockwise around the curve.

[Abb]

By this answer and @John D'Errico answer, I could compute it sucessfully, here is the code.

T1 = importdata('T1.mat');
T2 = importdata('T2.mat');
cx = mean(T1(:,1));
cy = mean(T1(:,2));
a = atan2(T1(:,2) - cy, T1(:,1) - cx);
[~, order] = sort(a);
x = T1(order,1);
y = T1(order,2);
polygon1= [x,y];
poly1 = polyshape(polygon1(:,1),polygon1(:,2));
plot(poly1)
cx = mean(T2(:,1));
cy = mean(T2(:,2));
a = atan2(T2(:,2) - cy, T2(:,1) - cx);
[~, order] = sort(a);
x = T2(order,1);
y = T2(order,2);
polygon2= [x,y];
poly2 = polyshape(polygon2(:,1),polygon2(:,2));
hold on
plot(poly2)
ply_inter = intersect(poly1, poly2);
area_inter = area(ply_inter);
% plot(ply_inter)
ply_union = union(poly1,poly2);
area_union = area(ply_union);
% plot(ply_union)
IoU = area_inter/area_union

[John D'Errico]

@Abb

That would work perfectly. You effectively converted to polar coordinates. around the centroid of the data. Then you sorted in terms of polar angle. (Good job!) It would not matter in which direction the sort went of course, as polyshape does not care about that.

A second, more sophisticated option would be to use what is called the CRUST algorithm. It allows a set of disordered points to be untangled. That would be useful, if the polygons were not almost convex things. So if the polygons were U-shaped, CRUST would be more useful.

A third approach would be to use a traveling salesman algorithm to find the shortest path through all of the points in each set. This would work quite well of course, and would handle even failrly messy curves. But for that you would need to download a tool to perform the solve. (Or write one yourself.)

But by far easiest is exactly what you did. Again, well done. I'm always happy to see someone take an idea and fly with it, then producing the correct result.

[Abb]

@John D'Errico thanks alot. I think this works now, but the other ways may help me later