Center of mass in voronoi cells

0
votes

Given a list of voronoi edges, how can I get the center of mass of each cell in a reasonable time?, note that I have only the edges of the Voronoi diagram, but I have to identify the center of mass.

The Voronoi diagram is constructed given the Delaunay triangulation, so that triangulation is also available for calculations.

Thanks!

2
algorithmcomputational-geometryvoronoi
Do you know the edges of the cells, or just a set of edges on the whole diagram? - Tamas Hegedus
@hege_hegedus I don't kwno the edges of the cells - Valentina Ramirez
I am assuming, if you know the edges, that you know their vertices? - tucuxi
But, the complexity will be O(n^2), there's a way to do it in O(n) or O(n log n)? - Valentina Ramirez

2 Answers

3
votes

This algorithm from wikipedia should work. It only requires you to input the coordinates of the points that delimit each cell. Since Voronoi cells are guaranteed to be non-self-intersecting and convex, this should be enough. Transcoding a bit (StackOverflow doesn't do nice math)

The centroid of a non-self-intersecting closed polygon defined by ''n'' vertices (x0,y0), (x1,y1), ..., (xn−1,yn−1) is the point (Cx, Cy), given by

Cx = 1/(6*A) * sum((x[i] + x[i+1]) * (x[i]*y[i+1] - x[i+1]*y[i])
Cy = 1/(6*A) * sum((y[i] + y[i+1]) * (x[i]*y[i+1] - x[i+1]*y[i])

With A the area, calculated as

A = 1/2 * sum(x[i]*y[i+1] - x[i+1]*y[i])

Where all those sum represent Σ from i=0 to i=n-1

-1
votes

First determine all the edges for a particular cell then then for that cell take the x component average separate then the y component average separate then that linear combination is the 'center of mass' of a cell. Then just do the same for each cell in the Voronoi diagram.