How to split a polygon.

Hello everyone.

If I have a polygon with the following coordinates:

x=[0 4 7 5 1];    %Polygon x-coordinates
y=[0 -2 0 10 8]; %Polygon y-coordinates

How can I split the polygon formed by the coordinates shown bellow in for example six parts which area is equal to each other?

[the cyclist]

Two questions before anyone spends time thinking about this:

• Is this a homework assignment?
• Is the only requirement that the six parts have equal area? I'm wary of other assumptions you may be neglecting to mention. For example, would it be ok to just make vertical slices? Or do you need to find a single point in the interior, such that lines to the vertices separate the area equally?

[Carlos Zúñiga]

Hello, thank you for your answer.

Actually it is not a homework. It is a problem that I couldn't achieve.

Yes, just as I said, all the areas must be equal. About the vertical slices, yes, we can use vertical slices because I'm traying to do the same but rotating the coordinets according to a slope with a rotation matrix.

Greetings and thank you so much for your time!

Answer 1

[Bruno Luong]

Each slice has area of 9.5

x=[0 4 7 5 1];    %Polygon x-coordinates
y=[0 -2 0 10 8]; %Polygon y-coordinates

n = 6;
P = polyshape(x,y);
A = P.area/n;
xmin = min(x); xmax = max(x);
ymin = min(y); ymax = max(y);
x0 = xmin+0.01;
b = zeros(1,n-1);
Q = cell(1,n);
Qk = polyshape(); % empty
for k=1:n-1
    x0 = fzero(@(x) areafun(P, xmin, x, ymin, ymax)-k*A, x0);
    b(k) = x0;
    Qp = Qk;
    [s, Qk] = areafun(P, xmin, b(k) , ymin, ymax);
    Q{k} = subtract(Qk, Qp);
end
Q{n} = subtract(P, Qk);

close all;
figure
hold on
for k=1:n
    Q{k}.area
    plot(Q{k});
end
axis equal

function [s, Q] = areafun(P, xmin, xmax, ymin, ymax)
R = polyshape([xmin xmax xmax xmin],[ymin ymin ymax ymax]);
Q = intersect(P,R);
s = Q.area;
end

[the cyclist]

Nice solution.

The first time through the for loop, Qk is not yet defined. It looks like just setting

Qk = 0;

before the for loop code will fix it.

[Carlos Zúñiga]

Hello Mr. Bruno. Thank you for your answer.

I was analysing your code and I have a question, What is the Qk variable? in the line where Qp = Qk, Qk it is not seted before.

Greetings.

[Bruno Luong]

Yeah sorry Qk must be intialized, whatever the value (it not effectively used the first time).

I edit the code to fix the error.

[Carlos Zúñiga]

Thank you so much Bruno.

I have another question, what if I want to split just a singular area, for example the first blue area in two parts but now in horizontal sections? Do you what I mean?

Thank you again!

[Carlos Zúñiga]

Actually I already answer myself!

Thank you so much Mr. Bruno!

[Bruno Luong]

Star-like partitioning

x=[0 4 7 5 1];    %Polygon x-coordinates
y=[0 -2 0 10 8]; %Polygon y-coordinates

n = 6;
P = polyshape(x,y);
A = P.area/n;
xmin = min(x); xmax = max(x);
ymin = min(y); ymax = max(y);
b = zeros(1,n-1);
Q = cell(1,n);
[xc,yc] = P.centroid;
r = sqrt(max((x-xc).^2+(y-yc).^2))*1.1;
Qk = polyshape(); % empty

x0 = 2*pi/n;
for k=1:n-1
    x0 = fzero(@(tt) areafun(P, xc, yc, tt, r)-k*A, x0);
    b(k) = x0;
    Qp = Qk;
    [s, Qk] = areafun(P, xc, yc, x0, r);
    Q{k} = subtract(Qk, Qp);
end
Q{n} = subtract(P, Qk);

close all;
figure
hold on
for k=1:n
    Q{k}.area
    plot(Q{k});
end
axis equal

function [s, Q] = areafun(P, xc, yc, tt, r)
ntt = max(ceil(abs(tt)*128),2);
phi = linspace(0,tt,ntt);
Q = polyshape([xc xc+r*cos(phi)],[yc yc+r*sin(phi)]);
Q = intersect(P,Q);
s = sign(tt)*Q.area;
end