11

重複の可能性：
ブルートフォース検索とは別に、凸包で最大の三角形を見つける方法

私は頂点のそれぞれがそれらの点の1つにある領域ごとに最大の三角形を見つけたいランダムな点のセットを持っています。

これまでのところ、最大の三角形の頂点は点群 (または凸包) の外側の点にのみあることがわかったので、それを行う関数をプログラムしました (nlogn 時間でグラハム スキャンを使用)。

しかし、それは私が立ち往生しているところです。これらのポイントから最大の三角形を見つける方法を理解できる唯一の方法は、凸包アルゴリズムが通常大多数のポイントを追い出すため、平均的なケースではまだ許容できる n^3 時間でブルート フォースを使用することです。ただし、点が円上にある最悪のシナリオでは、この方法は惨めに失敗します。

これをより効率的に行うアルゴリズムを知っている人はいますか?

注：CGALにはこのアルゴリズムがあることは知っていますが、その方法については詳しく説明していません。私はライブラリを使用したくありません。これを学び、自分でプログラムしたいです (また、他の実装が共線点を拾うグラハムスキャンのように、操作したい方法に正確に微調整できるようにします)私はほしくない）。

4

5 に答える 5

1

これが役立つかどうかはわかりませんが、凸包から2つのポイントを選択し、2つのポイントの接続線が、最大のポイントまたは最小のy座標を持つものは、最初に選択された2つのポイントとともに、最大の面積を持つ三角形を形成します。

もちろん、考えられるすべてのベースラインについて1つのポイントをテストしたら、リストから削除できます。

于 2010-06-24T12:38:18.930 に答える
0

これをO（n 2 log n）に下げる方法について考えます。計算幾何学については何も知らないので、コミュニティwikiとマークします。これを自由に改善してください。

セットが完全に線の片側にくるように、各点についてその点を通る線の傾きの範囲を見つけることによって、凸包を前処理します。次に、この関係を反転します。葉のノードに点がある勾配の区間木を作成します。勾配を使用してクエリを実行すると、それらの点を通る接線があるような点が見つかります。

凸包上に3つ以上の同一線上の点のセットがない場合、各勾配には最大で4つの点（各側に2つ）がありますが、同一線上の点の場合は、中間点を無視できます。

ここで、凸包上のすべての点のペア（P、Q）を反復処理します。三角形PQRが最大の面積を持つような点Rを見つけたいと思います。PQを三角形の底辺として、線PQからできるだけ離れたRを見つけることにより、高さを最大化する必要があります。PQに平行なRを通る線は、すべての点が線の片側にあるようにする必要があります。これにより、事前に構築された区間木を使用して、時間O（log n）で有界数の候補を見つけることができます。

これを実際にさらに改善するには、ポイントのペアのセットで分枝限定法を実行します。三角形の高さの上限（たとえば、2つのポイント間の最大距離）を見つけ、距離が乗算されたポイントのペアを破棄します。この上限によって、これまでに見つかった最大の三角形よりも小さくなります。

于 2010-06-17T20:53:39.553 に答える
0

ここでは回転キャリパー法が当てはまると思います。

于 2010-06-17T20:54:44.640 に答える
0

私の頭の上から、おそらく、ポイントのコレクションをグループにグリッド化/分割することを含む何かを行うことができますか? たぶん...ポイントを3つのグループに分けて（この場合の最善の方法はわかりませんが）、各グループ内の他のポイントよりも他の2つのグループに近いポイントを破棄するために何かをします残りのポイントを使用して、各グループに 1 つの頂点を持つ最大の三角形を見つけますか? これにより、実際にはすべての点が円上にある場合がはるかに簡単になります。これは、各グループに含まれる弧の中心近くにある点に注目するだけでよいためです。他の2つのグループ。

ただし、これが特定の三角形/点の分布に対して適切な結果をもたらすかどうかはわかりません。グループ化および/または頂点の選択が最適でないため、結果の三角形が最適な領域ではない場合があります。そんな感じ。

とにかく、それは問題に対する私の考えです。少なくとも、それに取り組む方法についてのアイデアを提供できたことを願っています。

于 2010-06-17T20:47:14.433 に答える
-1

凸包から一点ずつ落としてみてはどうでしょうか。凸包から始めて、隣接する点の各トリプル (p1p2p3、p2p3p4 など) によって形成される三角形の面積を計算します。面積が最小の三角形を見つけ、その三角形を形成する 3 つのポイントの中央をドロップします。(つまり、面積が最小の三角形が p3p4p5 の場合は、P4 を削除します。) これで、N-1 個の点を持つ凸多角形ができました。3 つのポイントが残るまで、同じ手順を繰り返します。これには O(N^2) 時間かかります。

これがうまくいかない病理学的なケースがあっても、私はまったく驚かないでしょうが、ほとんどのケースではうまくいくと思います. (つまり、私はこれを証明していませんし、引用する情報源もありません。)

于 2010-06-17T21:08:54.273 に答える