ビューポートのスケールに応じて、空間内の個々のポイントとしてレンダリングするか、代表的なポリゴンとしてレンダリングするかを決定できるように、2 次元ポイントのセットのサイズを特徴付ける方法が必要です。セットの凸包を計算して代表的なポリゴンを生成するアルゴリズムは既にありますが、そのサイズを特徴付ける方法が必要です。1 つの明白な尺度は、セットの直径である凸包上のポイント間の最大距離です。しかし、境界ポリゴンがどれほど狭いかを把握するために、直径に垂直な断面のサイズにもっと興味があります。ソートされた頂点のリストと最も遠い点のインデックス(理想的にはPythonで)を考えると、これを行う簡単な方法はありますか?
または、代わりに、一連の点の楕円を囲む最小領域の半径を計算する簡単な方法はありますか? この問題に対するいくつかのアプローチを見てきましたが、すぐに Python に変換できるものは何もないので、すぐに使用できるものを本当に探しています。
以下を計算できます。
その直径に垂直な断面のサイズ
次の手順で:
aを見つけます。bd = (a - b).normalized()これら2つの間の方向ベクトルを見つけます行列を使用して、この方向ベクトルが水平になるように軸を回転させます。
[ d.x, d.y]
[-d.y, d.x]
この新しい座標系のポイントの最小および最大 y 値を見つけます。違いはあなたの「幅」です
これは「幅」の特に適切な定義ではないことに注意してください。より良い定義は次のとおりです。
多角形の境界と共通する点が少なくとも 1 つあるが、多角形の内部とは共通しない 2 つの異なる平行線間の最小垂直距離
サイズのもう 1 つの有用な定義は、船体上の点と中心点の間の平均距離の 2 倍です。
center = sum(convexhullpoints) / len(convexhullpoints)
size = 2 * sum(abs(p - center) for p in convexhullpoints) / len(convexhullpoints)