Python：查找计算多边形“内部质心”（X，Y）的方法

Question

Python：查找计算多边形“内部质心”（X，Y）的方法

4

我有一个多边形（转换成了Shapely对象）。我的目标是计算“内部重心”（也称为“表面上的点”）（返回x，y值）和“重心”（返回x，y值），如下图所示：

enter image description here

from shapely.geometry import Polygon

ref_polygon = Polygon(points)
# get the x and y coordinate of the centroid
ref_polygon.centroid.wkt
'POINT (558768.9293489187300000 6361851.0362532493000000)'

我的问题是，是否有程序员已经开发了一个用Python计算内部重心或者知道一些可以实现这个功能的模块。

提前感谢。

使用的点（多边形的顶点）为：

points = [(560036.4495758876, 6362071.890493258),
          (560036.4495758876, 6362070.890493258),
          (560036.9495758876, 6362070.890493258),
          (560036.9495758876, 6362070.390493258),
          (560037.4495758876, 6362070.390493258),
          (560037.4495758876, 6362064.890493258),
          (560036.4495758876, 6362064.890493258),
          (560036.4495758876, 6362063.390493258),
          (560035.4495758876, 6362063.390493258),
          (560035.4495758876, 6362062.390493258),
          (560034.9495758876, 6362062.390493258),
          (560034.9495758876, 6362061.390493258),
          (560032.9495758876, 6362061.390493258),
          (560032.9495758876, 6362061.890493258),
          (560030.4495758876, 6362061.890493258),
          (560030.4495758876, 6362061.390493258),
          (560029.9495758876, 6362061.390493258),
          (560029.9495758876, 6362060.390493258),
          (560029.4495758876, 6362060.390493258),
          (560029.4495758876, 6362059.890493258),
          (560028.9495758876, 6362059.890493258),
          (560028.9495758876, 6362059.390493258),
          (560028.4495758876, 6362059.390493258),
          (560028.4495758876, 6362058.890493258),
          (560027.4495758876, 6362058.890493258),
          (560027.4495758876, 6362058.390493258),
          (560026.9495758876, 6362058.390493258),
          (560026.9495758876, 6362057.890493258),
          (560025.4495758876, 6362057.890493258),
          (560025.4495758876, 6362057.390493258),
          (560023.4495758876, 6362057.390493258),
          (560023.4495758876, 6362060.390493258),
          (560023.9495758876, 6362060.390493258),
          (560023.9495758876, 6362061.890493258),
          (560024.4495758876, 6362061.890493258),
          (560024.4495758876, 6362063.390493258),
          (560024.9495758876, 6362063.390493258),
          (560024.9495758876, 6362064.390493258),
          (560025.4495758876, 6362064.390493258),
          (560025.4495758876, 6362065.390493258),
          (560025.9495758876, 6362065.390493258),
          (560025.9495758876, 6362065.890493258),
          (560026.4495758876, 6362065.890493258),
          (560026.4495758876, 6362066.890493258),
          (560026.9495758876, 6362066.890493258),
          (560026.9495758876, 6362068.390493258),
          (560027.4495758876, 6362068.390493258),
          (560027.4495758876, 6362068.890493258),
          (560027.9495758876, 6362068.890493258),
          (560027.9495758876, 6362069.390493258),
          (560028.4495758876, 6362069.390493258),
          (560028.4495758876, 6362069.890493258),
          (560033.4495758876, 6362069.890493258),
          (560033.4495758876, 6362070.390493258),
          (560033.9495758876, 6362070.390493258),
          (560033.9495758876, 6362070.890493258),
          (560034.4495758876, 6362070.890493258),
          (560034.4495758876, 6362071.390493258),
          (560034.9495758876, 6362071.390493258),
          (560034.9495758876, 6362071.890493258),
          (560036.4495758876, 6362071.890493258)]

- Gianni Spear

2

你有“内部质心”这个定义吗？ - Chronial

亲爱的@Chronial，我正在测试两个多边形之间的几何相关性。该公式使用重心作为参考：该方法检查多边形A的重心是否落在多边形B内，反之亦然。我希望使用“内部重心”以避免不规则形状（在我的情况下大多数情况下）的问题。 - Gianni Spear

亲爱的@aquavitae，谢谢你，但我更喜欢在软件之外工作（我知道GRASS并且喜欢它）。 - Gianni Spear

@Gianni，我不太确定你的目标是什么。但你是在寻找多边形内的任意一个点还是具有特定属性的点？ - Chronial

@Chronial 在线阅读中，“内部重心”也被定义为“平衡点”。一些应用程序使用“内部重心”，因为对于非常奇特的区域形状（如马蹄铁形状），质心点可能会被放置在区域之外。 - Gianni Spear

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gareth Rees · Accepted Answer

“内部重心”这个术语在计算几何学中并没有明确定义，但从你的帖子中可以清楚地看出，你想计算一个点，它位于多边形内部（与附近边缘有一定的间隔），并且离真正的重心相对较近。

以下是几个可尝试的想法：

算法A

1. 生成多边形的所有内部对角线。 2. 对于每个内部对角线，考虑其中点，并根据其到最近边缘的距离以及到重心的接近程度给其打分。 3. 选择得分最高的中点。

An internal diagonal是指连接多边形两个非相邻顶点且完全位于多边形内部的线段。具有n个顶点的多边形的m条内对角线集可以使用一个相当复杂的算法由Hershberger提出在O(m + n log log n)时间内生成，或者使用更直接的算法在O(n^2)时间内生成。

算法B：

1. 将多边形三角化。 2. 对于三角剖分中的每个三角形，考虑其重心（或者可能是内心？），并根据其到最近边缘的距离以及其靠近多边形重心的程度给其打分。 3. 选择得分最高的三角形中心。

一个有n个顶点的简单多边形可以使用基于分解为单调多边形由Chazelle提出的算法在O(n)内进行三角剖分，或者使用更简单的方法，如 "耳截断" 在O(n²)内进行。