問題タブ [grahams-scan]

グラハム スキャン アルゴリズムを実装する必要があります。これは私のコードです：

ソートセクションでは機能しません。関数 _arctan2() および _sqrt() は大きな値を返します。つまり、sqrt は -1464986461 を返します。なぜそれが起こるのですか？その結果、ポイントはアルファによってソートされませんが、未知の方法でソートされます。ポイントの順序を手動で設定すると、アルゴリズムが適切に機能します。

うまくいかない方法を教えてください。

Convex hull とそれを実装する Graham Scan について研究していたのですが、みんなスタックを使っていることに気付きました。では、アルゴリズムでスタックが正確に使用される理由、スタックを使用する利点は何ですか?

Jarvis: このアルゴリズムは、h 個の極値ポイントを持つ n 個の入力ポイントに対して、最悪の場合に O(nh) 時間を必要とします。

Graham: 最悪のシナリオでは O(nlogn) です。

2 つのアルゴリズムを使用する CGAL のリファレンスを入手します。

つまり、h が logn より小さい場合、Jarvis はデータセット (2 次元としましょう) に対して高速になる可能性があります。しかし、私は実際にそれを見たいと思っていますが、この目的のためのデータセットを見つけることができません. 誰か知っていますか？

グーグルはこのリンクを生成します。これは、私が上記で主張していることを実際にサポートしています。

グラハムのスキャンまたはその他のアルゴリズムを線形時間で使用して、2 つのもつれた凸包 (このような) をマージして凸包を形成する方法は?

ソートする必要があるパスのエッジを形成する座標のリストがあります。グラハムスキャンを使用しようとしており、次のサンプルをいくつか試しました。

1. GrhamsScan.cs
2. ConvexHull.cs
3. 凸包アルゴリズム

これらのコードは、私が持っているいくつかのテスト ケースで失敗し、何が問題なのかわかりません。

編集：

これらの座標は、接線の一部であると想定されています。座標がソートされていない場合、接線は、嵐が進行するにつれて直線または曲線になる可能性のある適切なパスではなく、危険にさらされます。

嵐の進路を形成する円の接線を作成しています。例を次に示します。

編集#02

接線を形成する点が整っている場合、正しい形状 (最後の半円は無視してください) は次のようになります。

テストケース:

テストケース#01

テストケース#02

テストケース#03

浮動小数点座標の信頼できる並べ替えアルゴリズムを見つけることができ、その間に点を削除しないリソース、アルゴリズム、またはコードを親切に案内してください。スピードが優先ではなく、正確さが優先されます。

すべての入力に感謝します。ありがとう

現在、Convex HUll と連携して Graham's Scan に取り組んでいます。私は学生なので、自分でやろうとしていますが、答えを見つけるために複数のサイトをふるいにかけています。要するに、ファイルから 1 つとランダムに生成された 1 つのコンストラクターが動作しているので、ポイントの配列を作成できます。次のステップは、極角でソートするクイックソートを実装することです。これは、比較クラスを介して行われます。比較クラスは私が立ち往生しているところです。角度の比較を行うためにドット比較とクロス比較を使用するように言われていますが、かなり迷っています。

それがすべてです。行き詰まる前に、比較メソッドでちょっとしたことをしました。

quickSort と partition メソッドは非常に標準的なものですが、これらを追加して、皆さんがすべてを幅広く見ることができるようにします。

クイックソートメソッドを実行する前に、基本的に Compare クラスを起動して実行する必要があることはわかっていますが、ドット/クロス比較の使用方法さえまったくわからないので、本当に迷っています。

誰かが喜んで助けてくれるなら、私はとても感謝しています！ご覧いただきありがとうございます。素晴らしい夜をお過ごしください。