# What is a good algorithm, and framework, to calculate centres of gravity or mass (cog)?

I'd like to take an photograph, subdivide it into a tesselation, either of squares, or (ideally), hexagons, and then find the centre of gravity (or, if you prefer, centre of mass) of each cell of the tesselation.

The output, for any image, would be a matrix of points. For the attached diagram, something like this (in polar coordinates - $(r,\theta)$ ):

(5,5Π/4) (0,0) (1,7Π/4) (1,5Π/4)
(5,3Π/4) (0,0) (5,Π/2)
(0.0) (0,0) (0.0) (0,0)


I've attached an image showing what I mean.

My question, to put it simply, is the best method to use to calculate the cog, in this tessellation... For squares, it'd be easy to calculate the weighted mean for each row, but that would be too rough an approximation. What's a good way to iterate either a general tessellation (ideal), or an hexagonal one?

I have asked this question in the 'Computer Graphics' group, but not had any replies. I thought it might be suited better to the skills here.

There are several alternatives:

Alternative #1: you need to find for each cell of the tessellation the list of pixels contained in the cell. To do that, you can use a rasterization algorithm. You can use my open-source implementation [1]. If performance is an issue, you can also do that with a GPU.

Alternative #2 (the simplest): (if you have many different images to process and if there is a single fixed tessellation): first generate an "image" where each pixel contains the index of the cell that contains the pixel. You need to do that once only (it is completely independent on the input image). Then you can compute the pixels mass and centroids using the following algorithm (where cell(i,j) denotes the pre-computed "image"):

for each i,j
k = cell(i,j)
mass[k] = mass[k] + image(i,j)
centroid[k] = centroid[k] + image(i,j)*(i,j)

for each k
centroid[k] = centroid[k] / mass[k]
convert centroid[k] in polar coordinates (if needed)


where mass[] is an array of scalars and centroid[] an array of 2D points (dimension = number of cells for both).

Alternative #3: If your tessellation is a Voronoi diagram (i.e. if the cells are the set of points that are nearer to a "site" (xi,yi) than to all the other "sites" (xj,yj) for a list of sites:

for each i,j
k = nearest_site(i,j)
mass[k] = mass[k] + image(i,j)
centroid[k] = centroid[k] + image(i,j)*(i,j)

for each k
centroid[k] = centroid[k] / mass[k]
convert centroid[k] in polar coordinates (if needed)


To implement nearest_site(), you can either put all the sites in a Kd-tree, or exploit the structure of your tessellation (for instance, in your particular case, you can find the nearest site by comparing distances to a few sites based on (i,j))

• Dear Bruno, That is absolutely brilliant! It is precisely what I need. Thank you very much indeed. Regards, Peter – Peter Brooks Sep 11 '16 at 1:49