如何在2D和3D空间中计算多边形的中心

Question

考虑2D笛卡尔空间中的简单凸多边形.如果给出以这样的逆时针方向排序的顶点坐标列表[[x0, y0], ..., [xn, yn]].你怎么能计算多边形的中心(多边形内部与所有顶点等距的点)？

还要考虑第二种情况,其中多边形放置在3D笛卡尔空间中,其法向量不平行于任何笛卡尔轴.如何在不旋转多边形的情况下计算中心？

我可以阅读C/C++,Fortran,MATLAB和Python,但是任何伪代码也都很受欢迎.

编辑

我现在意识到我的问题没有得到很好的解决.我对此感到抱歉.似乎我所寻找的是多边形的质心(即,在假设均匀密度和均匀重力场的情况下纸板切口将平衡的点).

Answer 1

你对中心的定义一般没有意义.

要看到这一点,只需在平面上绘制三个非对齐点,并计算一个唯一的圆圈,通过所有三个点.显然,您的三角形中心必须是此圆的中心.

现在绘制第四个不在圆上并形成四边形多边形的点.中心是什么？平面中没有与所有顶点等距的点.

另请注意,即使三角形使用与顶点等距离的点也可以给出外部和远离多边形的点,并且在数值上也不稳定(给定任何ε> 0且M> 0,您始终可以构建一个三角形,其中a顶点的特定移动小于ε的距离使中心移动大于M的距离.

常用的"中心"是易于计算的所有顶点的平均值,边界的平均值,质心或甚至只是轴对齐边界框的中心.但是,如果多边形不是凸面,则所有这些都可以落在多边形之外,但在您的情况下,它们可能会起作用.

最简单的合理的(因为它不依赖于坐标系)是顶点的重心(Python中的代码):

xc = sum(x for (x, y) in points) / len(points)
yc = sum(y for (x, y) in points) / len(points)

关于它的不好之处在于,仅仅分割多边形的一侧会给你一个不同的中心(换句话说,它取决于顶点,而不是取决于由多边形限定的点集).最简单的取决于多边形是IMO边界的重心:

sx = sy = sL = 0
for i in range(len(points)):   # counts from 0 to len(points)-1
    x0, y0 = points[i - 1]     # in Python points[-1] is last element of points
    x1, y1 = points[i]
    L = ((x1 - x0)**2 + (y1 - y0)**2) ** 0.5
    sx += (x0 + x1)/2 * L
    sy += (y0 + y1)/2 * L
    sL += L
xc = sx / sL
yc = sy / sL

对于它们两者来说,对3d的扩展是微不足道的...只需z使用相同的公式添加.

在一般(不一定是凸起的,不一定是简单连接的)多边形的情况下,我发现有用的"中心"但是计算起来并不容易的是(a)与边界最大距离的内点(在换句话说,"最内在"的观点.

在这种情况下,我使用离散(位图)表示和高斯距离变换.