3

2D デカルト空間の単純な凸多角形を考えてみましょう。このように反時計回りにソートされた頂点座標のリストが与えられた場合[[x0, y0], ..., [xn, yn]]。多角形の中心 (すべての頂点から等距離にある多角形内の点) をどのように計算できますか?

また、ポリゴンが 3D デカルト空間に配置され、その法線ベクトルがどのデカルト軸にも平行でない 2 番目のケースを考えてみましょう。ポリゴンを回転させずに中心を計算するにはどうすればよいでしょうか?

C/C++、Fortran、MATLAB、Python を読むことができますが、擬似コードも大歓迎です。

編集

私の質問が適切に設定されていなかったことに今気づきました。ごめんなさい。私が探していたのは、ポリゴンの重心 (つまり、均一な密度と均一な重力場を仮定しながら、段ボールの切り抜きがバランスをとる点) であるようです。

4

2 に答える 2

10

センターの定義は一般的に意味がありません。

これを確認するには、平面上に整列していない 3 つの点を描画し、3 つの点すべてを通過する唯一の円を計算します。明らかに、三角形の中心はこの円の中心でなければなりません。

次に、円上にない 4 番目の点を描き、4 辺の多角形を形成します。センターって何？すべての頂点から等距離にある平面内の点はありません。

また、頂点から等距離の点を使用する三角形の場合でも、ポリゴンの外側や遠く離れた点が得られる可能性があり、数値的にも不安定であることに注意してください (任意の ε>0 および M>0 が与えられた場合、いつでも三角形を構築できます。 ε 未満の距離だけの頂点の特定の移動は、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同じ式を使用して追加するだけです。

一般的な (必ずしも凸状ではなく、必ずしも単純に接続されているとは限らない) 多角形の場合、有用であるとわかったが計算するのは簡単ではない「中心」は、境界から最大距離にある (内の) 内側の点です (言い換えれば、「最も内側の」ポイント)。

この場合、離散 (ビットマップ) 表現とガウス距離変換を使用することにしました。

于 2013-08-19T05:58:14.723 に答える
4

まず、多角形の場合、重心は常に重心から頂点までの長さが等距離であることを意味するとは限りません。ほとんどの場合、これはおそらく真実ではありません。xそうは言っても、座標の平均と座標の平均を見つけるだけで重心を見つけることができますy。Matlab の場合:centroidx = mean(xcoords)とcentroidy = mean(ycoords)は重心の座標です。本当にもっと必要な場合は、これを参照してください。

于 2013-08-19T03:02:44.167 に答える