给定 voronoi 边列表,如何在合理的时间内获得每个单元格的质心?请注意,我只有 Voronoi 图的边,但我必须确定质心。
Voronoi 图是给定 Delaunay 三角剖分构造的,因此三角剖分也可用于计算。
谢谢!
最佳答案
这algorithm from wikipedia应该管用。它只需要您输入分隔每个单元格的点的坐标。由于保证 Voronoi 单元是非自相交的和凸的,这应该足够了。稍微转码(StackOverflow 做的不是很好)
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
关于algorithm - voronoi 细胞中的质心,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34732437/