1

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!

Valentina Ramirez
  • 103
  • 8

2 Answers2

3

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

tucuxi
  • 17,561
  • 2
  • 43
  • 74
  • The problem is, that I can't get the vertices of each polygon given a list of edges – Valentina Ramirez Jan 11 '16 at 22:59
  • But I have to do it in a reasonable time. I want to know if exists some property using the Delaunay triangulation to construct the polygons or something like that. – Valentina Ramirez Jan 11 '16 at 23:09
  • @ValentinaRamirez:You can find the vertices of the polygons from the list of edges when you loop through all edges and find the distances between the site and the midpoint of edges. Sort the list ascending and add the first two edges to the voronoi polygon with the site in the center. – Micromega Jan 11 '16 at 23:35
  • @ValentinaRamirez: A VD is the edge closest to a site then any other site. – Micromega Jan 11 '16 at 23:42
  • @ValentinaRamirez you can [see](https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Delaunay_Voronoi.svg/180px-Delaunay_Voronoi.svg.png) that Delaunay and Voronoi are strongly related: if you have Delaunay, between each two Delaunay vertices you will find a Voronoi edge. Also, each Delaunay vertex is guaranteed to lie exactly within one Voronoi cell. This gives you an easy way of locating Voronoi edges for each V-cell, and therefore the V-cell's vertices. – tucuxi Jan 12 '16 at 00:20
-1

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.

ryanroberts
  • 21
  • 7
  • This method works for triangles. It does not work for polygons with 4 or more vertices. A simple counter-example is a polygon with vertices (1,0), (2,0), (3,1), (0,1). The average y value is `y=1/2`, but the center of mass is at `y=7/12`. – user3386109 Jan 12 '16 at 00:00