4

関連：ポリゴンの分解-凸多角形を形成するための凹点の削除

私は次のことを行うためのアルゴリズムを探しています：

入力は2Dポイントの配列です（P0 … PN -1）。配列の長さNは変化します（3≤N<∞）任意のM≤Nに対して、頂点がP0 …PM -1
の順序 である凸多角形が存在する場合と存在しない場合があります。

エッジは必ずしもアレイ内の隣接するペアではないことに注意してください。

この凸多角形が存在するような最大Mを見つけるための最も効率的なアルゴリズムは何ですか？

私の現在のアルゴリズムは非常に非効率的です。M = 3、M = 4、M = 5などでテストし、船体を計算してから、すべてのP0 … P ​​M-1が船体の頂点であることをテストします。そうでない場合は、ループから抜けてM-を返します。 1.1。

例1：[(-2,2), (2,2), (-2,-2), (-1,1)]
例＃1の図
結果：3（最初の3つのポイントは三角形を形成しますが、P 3 =(-1,1)を追加するとポリゴンが非凸になるため）

例2：[(-2,2), (2,2), (-2,-2), (1,-1)]
例2の図
結果：4（配列内の4つのポイントすべてから凸四角形を作成できるため）

例3の更新[(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)] 代替テキスト
： 結果：4。

この例は、提供されたすべての点の凸包を取得して、そのサブセットである接頭辞を見つけるだけでは不十分である理由を示しています。(3,-3)最初の5つのポイントで構成される凸多角形の一部にすることはできません。これは、前のポイント(2,-1)が船体上に存在しなくなるためです。しかし、それは(3,-3)6つのポイントすべての船体にあり、そうではないにもかかわらず、拒否されなければならないということ(2,-1)です。

無効な入力の例：

  • [(-1,-1), (0,0)]（ポイントが少なすぎる）
  • [(-1,-1), (0,0), (1,1), (1, -1)]（最初の3つのポイントは同一線上にあります。アルゴリズムがこれを処理できるとは思いません。）
4

4 に答える 4

2

これは O(m lg m) 時間で実行できます。

  • X座標でキー付けされた検索ツリーに上部ハルと下部ハルのポイントを保存します。
  • 新しいポイントが到着したら、その X 値をカバーする上下の線分を見つけます (ツリーを検索します)。
  • 新しい点が 2 つの線の間にある場合、それは船体上にはありません。あきらめる。
  • それ以外の場合は、ポイントを上部ハルまたは下部ハル (線分が近い方) に挿入します。
  • ポイントを挿入すると、隣接するポイントが内側のコーナーに変わった場合、それらはハル上にありません。あきらめる。
  • 新しい左端のポイント、垂直ポイントなどのエッジ ケースに対処します。
  • 必要な数のポイントが処理されるまで続行します。
于 2011-01-14T20:54:56.907 に答える
2

これには、非常に単純な O(m log m) ソリューションがあります。

少なくとも 3 つの点があり、最初の 3 点が同一線上にない場合:

  1. 最初の 3 点の三角形で点 P を見つけます。

  2. 3 点を P に対する角度 (反時計回り) で並べ替えます。(このソートされたリストが凸包になります)

  3. リストの最後ではありませんが、ソートされたリストで次のポイントの位置を見つけます。

  4. ポイントを挿入するとポリゴンが凹になる場合は、6 に進みます。 (これは、新しい隣接する 2 つのターンと現在のターンを確認するだけで確認できます)

  5. ポイントを挿入して 3 に進みます。

  6. 終わり。

ここで処理しなければならない主なエッジ ケースは、リストが実際には循環しているため、挿入がリストの末尾の 1 つである場合です。これを処理する簡単な方法の 1 つは、各点に対してその角度とその角度 +- 2pi で挿入することです。

于 2011-01-14T21:46:44.690 に答える
0

二分探索のようなものを試してみるとどうなるでしょうか。プレフィックス全体が凸多角形を形成するたびに、プレフィックスのサイズを 2 倍にします。失敗するたびに、プレフィックスのサイズを現在のサイズと以前のサイズの中間に縮小します。

于 2011-01-14T19:44:27.407 に答える