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. スコアが最も高い中点を選択します。

ポリゴンの内部対角線は、ポリゴンと完全に一致する2つの隣接しない頂点を結ぶ線です。n個の頂点を持つポリゴンのm個の内部対角線のセットは、Hershbergerによるかなり複雑なアルゴリズムを使用してO（m + n log log n ）で生成するか、より単純なアルゴリズムを使用してO（n 2）で生成できます。

アルゴリズムB

  1. ポリゴンを三角形分割します。

  2. 三角形分割の各三角形について、三角形の図心（またはおそらく内心？）を考慮し、最も近いエッジからの距離とポリゴンの図心にどれだけ近いかに基づいてスコアを付けます。

  3. スコアが最も高い三角形の中心を選択します。

n個の頂点を持つ単純なポリゴンは、チャゼルによる単調ポリゴンへの分解に基づくアルゴリズムを使用してO（ n ）で、または「耳のクリッピング」などのより単純なアプローチを使用してO（ n 2 ）で三角形分割できます。

于 2012-12-06T14:20:38.037 に答える