How to find area of all possible polygons?

n = 5; % No. of control points

array = 1:1:n;

p=arrayfun(@(k) num2cell(nchoosek(array,k),2), 3:length(array), 'unif', 0);

p=cat(1,p{:});

p=cellfun(@(array) num2cell(perms(array),2),p,'unif',0);

p=cat(1,p{:});

x = [1 ; 2 ; 3 ; 4 ; 2 ];   % coordinate of control points

y = [8 ; 5 ; 8 ; 7 ; 6 ];   % coordinate of control points

for i = 1:length(p)

      x_p{i,1} = x(p{i,1}); 

      y_p{i,1} = y(p{i,1}); 

end

From the above code, I got two cells x_p & y_p which provides coordinates of all possible polygons. I want to find the array of areas of all polygons. The size of area array will be (300 * 1). Thanks in advance.

[John D'Errico]

Just use a loop. Call polyarea for each polygon. WTP? There are only 300 polygons. Be serious.

[Manas Ranjan Pattnayak]

I am basically calculating the convex hull for the given sets using an area approach where the convex hull polygon will give the maximum area. However the 'polyarea' function is insensitive when the sides of polygon cross each other. Need an alternative approach to find the area !!

[Bruno Luong]

What you mean by "insensitive"? It will be sensitive and gives actually the absolute value of the algebraic signed area.

Now this is suitable for your problem or not, who knows because you haven't tell what should be the area you expect when the two or more edges are crossing.

But I believe it does because you seem to look for the permutation with largest area, and when the edge are crossing (which you don't want) polyarea will give smaller result than the non crossing polygonal with the same vertexes but permuted.

So the crossing cases will be eliminated when you take the maximum with polyarea.

[Walter Roberson]

"I am basically calculating the convex hull for the given sets using an area approach where the convex hull polygon will give the maximum area."

Perhaps change your approach to use boundary() . Or find the centroid and distances to the vertices from there.

I have the suspicion that the whole problem can be solved with linear programming or dynamic programming.

[Manas Ranjan Pattnayak]

x = [0;4;0;4;0]; y = [0;0;2;2;0];

polyarea(x,y) = 0.

The expected area is 4. But the area I am getting using polyarea is 0.

[Bruno Luong]

Wrong figure corrected for x = [0;4;0;4;0]; y = [0;0;2;2;0];

The result 0 is * signed* area, since the polygonal is twisted, given the bottom triangle area of 1, and the top triangle of -1 (or the opposite, it doesn't matter), the sum is then 0. See (*) for the rule.

Vertexes order matter.

If you want the area 4, then I would say you have to permute the vertexes (0,0) -> (4,0) -> (4,2) -> (0,2)

But this appears somewhere else in your list of 300.

(*) Rule of polyarea

given (x1,...,xn) and (y1,...,yn) x-y coordinates of n vertexes of a polygonal, draw n oriented edges (with arrows)

• from (x1,y1) to (x2,y2)
• from (x2,y2) to (x3,y3)
• ..
• from (x(n-1),y(n-1)) to (xn,yn)
• from (xn,yn) to (x1,y1)

It gives disjointed sub-polygonals (2 triangles in the example above).

For all subpolygonal:

1. If the subpolygonal has surrounding edges counter-clockwise: add area of as positive
2. If the subpolygonal has surrounding edges clockwise: add area of as negative.

The absolute value of the sum of all signed areas defined as above is what polyara() returns as result.

[Manas Ranjan Pattnayak]

Thank you so much. Found the answer. However just asking - Is there any way to find the "unsigned area" of the polygon??

[Bruno Luong]

Yes but this method is still strongly NOT recommended, since that math behind is not consistent, as stated by the warning. Just manage to eliminate those invalid polygonal.

    >> x = [0;4;0;4;0]; y = [0;0;2;2;0];
    >> p=polyshape(x,y)
    Warning: Polyshape has duplicate vertices, intersections, or other inconsistencies that may produce
    inaccurate or unexpected results. Input data has been modified to create a well-defined polyshape. 
    > In polyshape/checkAndSimplify (line 481)
      In polyshape (line 175) 

    p = 

      polyshape with properties:

          Vertices: [7×2 double]
        NumRegions: 2
          NumHoles: 0

    >> p.area

    ans =

         4

Answer 1

[Bruno Luong]

n = 5; % No. of control points

array = 1:1:n;
p=arrayfun(@(k) num2cell(nchoosek(array,k),2), 3:length(array), 'unif', 0);
p=cat(1,p{:});
p=cellfun(@(array) num2cell(perms(array),2),p,'unif',0);
p=cat(1,p{:});
x = [1 ; 2 ; 3 ; 4 ; 2 ];   % coordinate of control points
y = [8 ; 5 ; 8 ; 7 ; 6 ];   % coordinate of control points

% Vectorize the computing of areas (in S(:))
% by group of polygonals having the same length
np = cellfun('length',p);
[npu,~,J] = unique(np); % npu is logically [3,4,5]
s = zeros(size(p)); % allocate array of area result
for i = 1:length(npu) % == 3
    b = J==i;
    Pi = cat(1,p{b});
    s(b) = polyarea(x(Pi),y(Pi),2);
end

% Many of them represents the same geometrical polygon
% The entire procedure seems redundant thus wasteful
allimax = find(s==max(s));
for j=1:length(allimax)
    imax = allimax(j);
    pmax = p{imax};
    xpmax = x(pmax);
    ypmax = y(pmax);
    figure;
    plot(xpmax([1:end 1]),ypmax([1:end 1]));
end

Answer 2

[Walter Roberson]

The official way to do this since R2017b is to use polyshape() to define a polyshape object from x and y coordinates, and then to use the area() method. You can see from https://www.mathworks.com/help/matlab/ref/polyshape.html#mw_fc5e8ce5-418f-4935-bd8b-6dd205170891 that "bowtie" area is supported.

[Bruno Luong]

"The official way ..."

just wonder: polyarea is not official?

Unless I'm mistaken, polyarea can compute area of multiple polygonal with the same number of vertices in a single call (vectorized then), something polyshape can't.

TMW seems to go lately father and father to OOP, and neglects the essential: speed.

[Walter Roberson]

polyshape decomposes to non selfintersecting polygons and calculates the total area. polyarea uses a much faster formula that is valid when there is no selfintersecting and which ends up subtracting areas if there is, which is useful in some situations. Different purposes.