Compact way to calculate the centroid of a boundary of a set of points

Is there any compact way to calculate the centroid of a boundary of a set of points ?

Answer 1

[Jan]

The centroid of the boundary is the mean value of the coordinates:

x = rand(40, 1).^2;  % More points on the left
y = rand(40, 1).^2;  % More points on the bottom
k = boundary(x, y);
c = mean([x(k), y(k)], 1);  % Center of points of boundary
plot(x, y, 'r.');
hold('on');
plot(x(k), y(k), 'b');
plot(c(1), c(2), '*g');

You see, that this is not the center of mass, but the centroid of points. To get the center of mass:

[CoMx, CoMy] = centroid(polyshape(x(k), y(k)));  % Center of Mass
plot(CoMx, CoMy, '*k');

% or:
[cx, cy] = CenterOfMass(x(k), y(k))

cx = 0.4679

cy = 0.4957

function [cx, cy] = CenterOfMass(x, y)
% This fails, if lines of the polygon intersect.
x = x(:);
y = y(:);
x_ = circshift(x, 1);
y_ = circshift(y, 1);
A  = x .* y_ - x_ .* y;
As = sum(A) * 3;
cx = sum((x_ + x) .* A) / As;
cy = sum((y_ + y) .* A) / As;
end

[Bruno Luong]

"The centroid is the mean value of the coordinates"

I'm not sure if I have the same definition. I would say it is as the mass is ditributed on the boundary, so it can be calculated as the weigthed mean of the center of the segments. The weight is the length of the segment.

But as OP doesn't make any description, I'll hesitate to give that solution.

[Sim]

Thanks both @Jan and @Bruno Luong! I was thinking at the "centroid as the mean value of the coordinates", but there might be other definitions, I do not know about other ones (@Bruno Luong?)...

About the center of mass of the points, I did not think about it.... :-)

...But then, which of the two centers would make more sense / would be more appropriate to characterize the points?

[William Rose]

@Sim,

@Jan has done a very clever thing. He creates an array of points that roughly covers the unit square, so the centroid should be near (.5,.5). The points are distributed in a parabolic way so there are more points near the origin than you'd expect for a simple 2D uniform distribution. This is smart because it creates a data set in which the mean of all the points (green *) is noticeably different from the centroid (black *).

Here is a non-random set of points that also illustrates the difference: a square plate with a skinny notch, and 7 points at the base of the notch:

x = [0 0 1  1  .03 .027 .023 .02 .023 .027 .03  1  1 ]';
y = [0 1 1 .51 .51 .508 .502 .50 .498 .492 .49 .49 0 ]';
pgon=polyshape(x,y);
c = mean([x, y], 1);
[COMx, COMy] = centroid(pgon);
plot(x, y, 'r.');
hold('on');
plot(pgon)
plot(c(1), c(2), '*g');
plot(COMx, COMy, '*k');

@Bruno Luong also has a smart question, which had not occurred to me: Is this surface a filled-in polygon, or is all its mass on the edge?

[Bruno Luong]

My proposition is assumed a unifrorm Mass of the edge (boundary) which gives the result that is more or less invariant to the density of the sample points of the boundary.

x = [0 0 1  1  .03 .027 .023 .02 .023 .027 .03  1  1 ]';
y = [0 1 1 .51 .51 .508 .502 .50 .498 .492 .49 .49 0 ]';
pgon=polyshape(x,y);

%% Point centroid
c = mean([x, y], 1);

%% Region centroid
[COMx, COMy] = centroid(pgon);

%% Boundary centroid
xyw = [x([1:end 1])';
       y([1:end 1])'];
w = sqrt(sum(diff(xyw,2).^2,1));
xym = (xyw(:,1:end-1)+xyw(:,2:end))/2;
bdrc = sum(xym.*w,2) ./ sum(w,2);

plot(x, y, 'c.');
hold('on');
plot(pgon)
h1=plot(c(1), c(2), '*g');
h2=plot(COMx, COMy, '*k');
h3=plot(bdrc(1), bdrc(2), 'or');
legend([h1,h2,h3], 'points', 'region', 'boundary')

[William Rose]

@Bruno Luong, very nice, and I would give it thumbs up if I could

[William Rose]

@Jan's CenterofMass() function is borderline black magic. He is a master of the dark arts of math and Matlab.

[Sim]

@William Rose

@Bruno Luong

Thanks both for your comments, that I found very useful!!

[Sim]

@William Rose Sorry, I forgot to reply to "Is this surface a filled-in polygon, or is all its mass on the edge?"

I have a bunch of points, and I create a boundary to wrap my points. Therefore, I would say that most of the mass (given by my points) lies inside the boundary and not on the boundary / edge.

:-)

[Sim]

Hi again @Jan @Bruno Luong @William Rose

I have tried to make a summary of all your answers (and I got a bit confused about the meaning of the Bruno Luong's "region centroid" and "boundary centroid"):

x = rand(40, 1).^2;  % More points on the left
y = rand(40, 1).^2;  % More points on the bottom
k = boundary(x, y);  % Get the boundary that wraps the points
pgon=polyshape(x,y);

figure('position',[100 100 600 600],'Color',[1 1 1],'Visible','on');

hold on

    % Show the points
    plot(x, y, 'r.');
    
    % Show the boundary
    plot(x(k), y(k), 'b');
    
    % Center 1
    % From Jan: "center of points of boundary" or "centroid of the boundary"
    c = [];
    c = mean([x(k), y(k)], 1);
    h1 = plot(c(1),c(2),'linewidth',2,'MarkerSize',15,'Marker','.','MarkerEdgeColor','g');
    
    % Center 2
    % From Jan: "center of mass"
    CoMx = []; CoMy = [];
    [CoMx, CoMy] = centroid(polyshape(x(k), y(k)));
    h2 = plot(CoMx, CoMy,'linewidth',2,'MarkerSize',15,'Marker','x','MarkerEdgeColor','k');
    
    % Center 3
    % From Jan: "center of mass", called "function [cx, cy] = CenterOfMass(x, y)"
    x_ = []; y_ = []; A = []; As = []; cx = []; cy = [];
    x = x(k);
    y = y(k);
    x_ = circshift(x, 1);
    y_ = circshift(y, 1);
    A  = x .* y_ - x_ .* y;
    As = sum(A) * 3;
    cx = sum((x_ + x) .* A) / As;
    cy = sum((y_ + y) .* A) / As;
    h3 = plot(cx, cy,'linewidth',2,'MarkerSize',15,'Marker','d','MarkerEdgeColor','r');

    % Center 4
    % From Bruno Luong: point centroid
    % From William Rose: no name
    c  = [];
    c = mean([x, y], 1);
    h4 = plot(c(1),c(2),'linewidth',2,'MarkerSize',15,'Marker','^','MarkerEdgeColor','m');

    % Center 5
    % From Bruno Luong: region centroid
    % From William Rose: no name
    COMx = []; COMy = [];
    [COMx, COMy] = centroid(pgon);
    h5 = plot(COMx, COMy,'linewidth',2,'MarkerSize',15,'Marker','>','MarkerEdgeColor','b');
    
    % Center 6
    % From Bruno Luong: boundary centroid
    xyw = []; w = []; xym = []; bdrc = [];
    xyw = [x([1:end 1])';
           y([1:end 1])'];
    w = sqrt(sum(diff(xyw,2).^2,1));
    xym = (xyw(:,1:end-1)+xyw(:,2:end))/2;
    bdrc = sum(xym.*w,2) ./ sum(w,2);
    h6 = plot(bdrc(1), bdrc(2),'linewidth',2,'MarkerSize',15,'Marker','o','MarkerEdgeColor','y');
    
    % plot(pgon)
    legend([h1,h2,h3,h4,h5,h6],...
        'Jan: center of points of boundary',...
        'Jan: center of mass',...
        'Jan: center of mass (CenterOfMass)',...
        'Bruno Luong: point centroid AND William Rose: no name',...
        'Bruno Luong: region centroid AND William Rose: no name',...
        'Bruno Luong: boundary centroid', ...
        'fontsize',15);%,'Location','northeastoutside')

hold off

set([h1,h2,h3,h4,h5,h6],'linestyle','none')

This is the result, with 4 types of centers....

From this plot we can see that:

• the Bruno Luong's "point centroid" is the Jan's "center of points of boundary" (even though the arguments of the mean are slightly different, i.e. "[x, y]" for Bruno Luong and "[x(k), y(k)]" for Jan).. right?

    % From Bruno Luong: point centroid
    c = mean([x, y], 1);
    
    % From Jan: "center of points of boundary" or "centroid of the boundary"
    c = mean([x(k), y(k)], 1);

• the Jan's "center of mass" is the Jan's "center of mass (with the function CenterOfMass)"

Therefore,

• I would take the Bruno Luong's "point centroid" and the Jan's "center of points of boundary" definitions as definition for the "centroid of a boundary of a set of points" as in my initial question (even though the arguments of the mean are slightly different, i.e. "[x, y]" for Bruno Luong and "[x(k), y(k)]" for Jan)
• I would also consider the Jan's definition of "center of mass".
• Still I do not understand what the Bruno Luong's "region centroid" and "boundary centroid" mean (?).

[William Rose]

@Sim,

The point centroid is the average of the locations of all the points.

The boundary centroid is the centroid of a wire of uniform density that runs along the boundary.

The region centroid is the centroid of a plate of uniform density, with the specified boundary.

If you place a lot of boundary points close together in a straight line, the point centroid will be pulled in that direction, but the boundary and region centroids won't be affected, because the wire location and the plate edge are still the same, whether it is just a few points in a line, or many.

If you add a long thin hairpin fold to the wire, the boundary centroid will be pulled in that direction, but the plate centroid will not be affected much, because the "cutout" made by the hairpin has a negligible area.

[Sim]

Thanks a lot @William Rose! This is now clear! :-)

[William Rose]

You're welcome, @Sim. :)

[Sim]

Hi @Jan,

What is the reference about the equations you used in your function?

function [cx, cy] = CenterOfMass(x, y)

.....Maybe one of these two?

• Calculating the area and centroid of a polygon in 2d
• Calculating the area and centroid of a polygon, Written by Paul Bourke, July 1988

[Sim]

Hi @Jan, it looks like your function

% [cx, cy] = CenterOfMass(x(k), y(k))

function [cx, cy] = CenterOfMass(x, y)
% This fails, if lines of the polygon intersect.
x = x(:);
y = y(:);
x_ = circshift(x, 1);
y_ = circshift(y, 1);
A  = x .* y_ - x_ .* y;
As = sum(A) * 3;
cx = sum((x_ + x) .* A) / As;
cy = sum((y_ + y) .* A) / As;
end

performs the same as in

Calculating The Area And Centroid Of A Polygon - Written by Paul Bourke (July 1988):

However, it looks like you divide by 3, while, in this paper, the author divides by 6.

Did you use the same formulas or something else? Or am I missing something? I do not understand.. :-) :-) :-)

[Bruno Luong]

@Sim The area of the polygonal (A in the book) is sum(A)/2 in Jan code.

So sum(A)*3 in Jan's code is equal to 6*area. They are the same. (EDIT typo)

[Sim]

Thanks a lot @Bruno Luong!! :-)