给定一组2D或3D点:

如何找到对象的几何中心?

根据下图,几何中心与中心不同如果以最简单的形式(即均匀的质量密度)计算得出的质量质量。实际上,问题出在计算这些问题上。
常见的一种方法是分别平均X坐标和Y坐标,即找到给定点的平均位置(此处为2D)。可以将其用作表示对象的点集的质心。
如图所示,由于沿着底部边缘的多余顶点,对于一个简单的矩形,质心为(0.5,0.4),而正确答案为(0.5,0.5)。
请注意,给出的示例过于简单。但是,有趣的问题是2D的复杂形状和3D的对象(仅顶点的坐标可用)。
顺便说一句,一种有效的计算方法很有趣。

仅提及我已经检查了一些Web链接,例如Wikipedia,但是我当前的问题是,希望找到一组2D和3D点来代表这些点。因此质心引起了人们的兴趣。给出的点没有任何拓扑信息。您可以将它们视为点云。此处提供的演示清楚地表明,众所周知的坐标平均值(例如,请参见此堆栈溢出Q&A)可能不正确,如示例中所示。



下面是一些比较的实现:



aa =下面接受的答案
=点的凸包,即,金色多边形
cent =质心在Wikipedia中提出,并在aa中作为多边形质心
centl =折线的质心,如aa

中所述
在视觉上,与centl相比,cent看起来更能代表所给的几何形状。另外两个在这里看起来很有希望,但是如果点的分散是不常见的,通常它们会产生偏见。
还要考虑到,尽管凸包使问题变得更简单,但它可能产生的时间又太长了。在空间中没有任何对称定位的短边,也就是说,如果对两种情况都进行简单平均(即不加权),则必须注意:整个点(绿色)或凸壳多边形顶点(蓝色)。


在找到给定点的最小面积矩形中可以找到一个应用程序。.

评论

这样行吗?找到多边形的质心? (StackOverflow)

我不确定您的问题是什么。几何中心或(通常是质心)可以不同于重心(质心)。这是众所周知的事实。此外,还有多种计算几何中心的方法。请参阅:en.wikipedia.org/wiki/Triangle_center,en.wikipedia.org/wiki/Encyclopedia_of_Triangle_Centers&faculty.evansville.edu/ck6/encyclopedia/ETC.html。

重新更新:没有拓扑时,点云就是点云。您的多边形正方形的图形不适用(顺便说一下,您的(0.5,0.4)的“质心”似乎不是由任何标准公式引起的:对称性强烈要求正方形的任何中心点与(0.5 ,0.5),无论其定义如何)。有关寻找二维或更多维点云的代表位置或中心位置的一些想法,请参阅stats.stackexchange.com/questions/1927。

@Developer,我现在看到您的要点,您在“矩形”(实际上是多边形)底部的第5个点对顶点坐标进行简单平均,得出的重心与多边形的重心不同,如wubher的答案所述。

啊哈!即使我一直在寻找这样的东西,我也完全错过了第五个顶点。为了帮助将来的读者,我对问题进行了一些编辑以指出这一点。这的确也触及了问题的核心:沿着边缘插入或删除顶点将改变多边形{line,gon}的表示方式,但不应改变其固有几何特性的计算。这就是为什么顶点的重心与多边形或其边界的重心几乎具有任意关系的原因。

#1 楼

每个多边形至少有四个不同的“中心”:


其顶点的重心。
其边的重心。
其重心为一个
用于标注的GIS特定“中心”(通常使用未记录的专有方法计算)。不同的点。)

“重心”通常是“质心”。这三种类型在假定质量的位置上有所不同:它要么全部在顶点上,要么均匀分布在边上,要么均匀地分布在整个多边形本身。

存在简单的方法来计算所有三个重心。一种方法基于以下基本事实:两个质量的不相交联合的重心是重心的总质量加权平均值。由此,我们可以轻松获得以下内容:


两个(相等加权)顶点的重心是它们的平均值。这是通过分别平均其坐标来获得的。在几何上,它是连接两个顶点的线段的中点。
归纳起来,n个(相等权重)顶点的重心是通过分别平均其坐标来获得的。
线段的重心是其顶点的重心。中点。 (通过对称性可以清楚地看到。)

折线的重心是通过找到每个线段的中点,然后使用线段长度作为权重形成其加权平均值来获得的。 />例如,考虑由(0,0),(6,0),(6,12)点划定的“ L”形。有两段:一个长度为6的中点为((0 + 0)/ 2,(0 + 6)/ 2)=(3,0),另一个长度为12的中点为((6 + 6)/ 2,(0 + 12)/ 2)=(6,6)。因此,它们的长度加权平均坐标为(x,y),且为

)/ 3,(0 + 0 + 12)/ 3)=(4,4)。

(编辑作为另一个示例,考虑问题中的图形,该图形虽然呈正方形,但表示为由点(0,0),(1 / 2,0),(1,0), (1,1),(0,1)。五个边的长度为1 / 2、1 / 2、1、1、1和中点(1 / 4,0),(3 / 4,0),(1 ,(1/2),(1 / 2,1)和(0,1 / 2),因此它们的加权平均值等于

x = (6*3 + 12*6) / (6+12) = 5,  y = (6*0 + 12*6) / (6+12) = 4.

希望,即使仅顶点的重心(如上面的#2计算)为(0.5,0.4)。)


可以通过三角剖分获得多边形的重心它变成三角形。三角形-四边形的重心与其顶点的重心重合。这些重心的面积加权平均值是多边形的重心。三角形区域很容易根据其顶点坐标来计算(例如,根据两个侧面的楔形积来计算)。有关此类面积计算的说明,包括如何利用带符号的(正或负)面积,请参阅我的(旧)课程笔记页面上的“面积”部分。

例如在问题中。我们可以用左侧的三角形(((0,0),(1 / 2,0),(0,1)),((0,1),(1 / 2,0 ),(1,1))位于中间,([(1,1),(1,0),(1 / 2,0))位于右侧,它们的面积分别为1 / 4、1 / 2、1分别为/ 4和其重心(通过平均其顶点获得)分别为(1 / 6,1 / 3),(1 / 2,2 / 3)和(5 / 6,1 / 3)。这些重心的面积加权平均值等于

[(1/2)*(1/4, 0) + (1/2)*(3/4, 0) + (1)*(1, 1/2) + (1)*(1/2, 1) + (1)*(0, 1/2)] / (1/2+1/2+1+1+1)
= (2/4, 2/4) = (0.5, 0.5)


,尽管底部边缘存在第五个顶点。
显然,这些方法中的每一种都是有效的:只需在多边形的“意大利面”表示上进行一次遍历,并在每个步骤中使用(非常少的)恒定时间即可。请注意,在除第一个(纯顶点)之外的所有情况下,需要的信息不仅是顶点坐标列表:您还需要了解图形的拓扑。例如,在“ L”示例中,我们需要知道(0,0)连接到(6,0)而不是(6,12)。

这些都是欧几里得概念。它们可以通过几种方式扩展到球体(或椭圆体)。一个简单明了的人将特征看作是三个(欧几里得)维的单纯复形,计算了适当的重心,然后将其从椭球的中心向外投射回曲面。这不需要新的概念或公式;除了前两个坐标外,您只需要使用第三个(z)坐标即可。 (仍然可以使用楔形乘积的长度找到面积。)

另一种概括认识到欧几里得度量(根据毕达哥拉斯的平方和的平方根)可以更改为其他Lp度量当p> = 1时,取p次方之和的pth根。找到合适的“重心”不再那么简单,因为上面开发的漂亮的加性(重心是图形中较简单部分的重心的加权平均值)通常不再成立。通常,必须获得迭代的近似数值解。它们甚至可能不是唯一的。

可以出于各种目的定义其他中心。三角形有许多不同的中心可以(大致)概括为多边形:外接圆的中心,最大圆的(某些)圆的中心,最小面积边界椭圆的中心等。任何一组都可以包含在各种“外壳”中,例如凸形外壳以及获得的这些外壳的中心。

注意,这些“中心”中的许多不一定位于多边形内部。 (不过,凸多边形的任何合理的中心都将位于其内部。)

各种各样的方法和解决方案表明,应该警惕诸如“几何中心”之类的通用术语,或者仅仅是“中心“:几乎什么都可以。

评论


致社区:像这样来自“ whuber”的好答案只能问一个好问题,因为我熟悉他的偏爱,因此,如果您觉得这个问题很有趣,那么每个人也都愿意投票赞成这个问题;)

–开发人员
2012年4月3日,9:20

我觉得它在某种意义上是有用的,希望给其他竞争者一些时间作为回答的动机。到目前为止,我将其标记为一个无法解释的建设性答案。

–开发人员
2012年4月3日,9:21

您能解释为什么在球体上使用楔形积仍能找到区域吗?球形三角形区域会更合适吗?我找到的最接近的参考文献(除了这个出色的答案!)是:jennessent.com/downloads/Graphics_Shapes_Online.pdf-使用球形三角形的区域。

–詹森·戴维斯(Jason Davies)
2012年12月7日上午10:47

@Jason我很感兴趣:您如何建议使用球形三角形区域来计算球形特征的重心?

– hu
2012年12月7日14:20在

@whuber球面多边形被分解为球面三角形,并且每个三角形的重心通过平均其顶点的笛卡尔坐标来计算。我建议多边形重心是这些三角形的加权平均值,其中权重是球形三角形区域,而不是您在答案中建议的平面区域(假设我正确理解了楔积)。

–詹森·戴维斯(Jason Davies)
2012年12月7日在16:05