4

(X,Y) 座標の配列/ベクトルで定義されたデカルト平面に点のセットがあるとします。不連続な点のセットが連続している場合、この点のセットは座標平面で「連続」します。つまり、これらのポイントは、以前のアルゴリズムによってポイントの領域が削除された長方形のグリッドとして発生しました。点で囲まれた形状は任意ですが、エッジの円弧を持つ傾向があります。

さらに、固定半径の円を作成できるとしますr。

X,Y指定された点のできるだけ正確に半分を囲む円の中心を見つけるアルゴリズムが必要です。

4

2 に答える 2

0

OK、これを試してみてください（言葉遣いが非常に悪い場合は申し訳ありません：私は英語で数学を学びませんでした）

ステップ 1: 軸を見つける

  • 2r 未満の点のすべてのペアについて、接続線の両側にいくつの点があるかを計算します
  • バランスが最悪のペアを選択
  • これらの 2 点を軸として二等分する線を計算します (「最大凹面の軸」)。

ステップ 2: 中心を見つける

  • ステップ 1 でポイント数が少なかった側 (凹面側) から遠く (>2r) 離れた軸から開始します。
  • 目的のポイントに到達するまで、軸の中心を移動します。これは、sqrt(delta) のステップで上に移動することで実行できます。ここで、デルタは、セット内の 2 つのポイント間の最小距離です。
于 2013-05-19T23:03:55.600 に答える
0

ポイントセットの最小の囲み円のアルゴリズムを調べることができます。

いくらか貪欲なアルゴリズムは、円の半径が r 以下になるまで一度に 1 点ずつ単純に削除することです。

于 2013-05-20T02:17:53.550 に答える