4

我有一个多边形（在Shapely对象中转换）。我的目标是按照图形示例计算“内部质心”（也称为“表面上的点”）（返回 x,y 值）和“质心”（返回 x,y 值）：

在此处输入图像描述

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)]
4

1 回答 1

9

术语“内质心”在计算几何中不是一个定义明确的术语，但从您的帖子中可以清楚地看出您想要计算一个位于多边形内部的点（在它和附近边缘之间有一些边距），并且这相当接近真实的质心。

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

算法 A

  1. 生成多边形的所有内部对角线。

  2. 对于每个内部对角线，考虑中点，并根据它与最近边缘的距离以及与质心的接近程度为其打分。

  3. 选择得分最高的中点。

多边形的内部对角线是连接两个完全位于多边形内的不相邻顶点的线。由于 Hershberger的缘故，可以使用相当复杂的算法在 O( m + n log log n ) 中生成具有n 个顶点的多边形的m个内部对角线集，或者使用更直接的算法在 O( n2 )中生成。

算法 B

  1. 对多边形进行三角剖分。

  2. 对于三角剖分中的每个三角形，考虑三角形的质心（或者可能是内心？），并根据它与最近边的距离以及与多边形质心的接近程度为其打分。

  3. 选择得分最高的三角形中心。

具有n个顶点的简单多边形可以使用基于Chazelle分解为单调多边形的算法在 O( n )中进行三角剖分，或者使用“剪耳”等更简单的方法在 O( n2 ) 中进行三角剖分。

于 2012-12-06T14:20:38.037 回答