algorithm - voronoi 细胞中的质心

Question

给定 voronoi 边列表，如何在合理的时间内获得每个单元格的质心？请注意，我只有 Voronoi 图的边，但我必须确定质心。

Voronoi 图是给定 Delaunay 三角剖分构造的，因此三角剖分也可用于计算。

谢谢!

Answer 1

这algorithm from wikipedia应该管用。它只需要您输入分隔每个单元格的点的坐标。由于保证 Voronoi 单元是非自相交的和凸的，这应该足够了。稍微转码(StackOverflow 做的不是很好)

The centroid of a non-self-intersecting closed polygon defined by ''n'' vertices (x₀,y₀), (x₁,y₁), ..., (x_n−1,y_n−1) is the point (C_x, C_y), 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