問題タブ [grahams-scan]

問題

ユーザーは、最大 4 つの緯度と経度の座標を任意の順序で指定できます。彼らは Google マップでそれを行います。Google のPolygonAPI (v3) を使用して、選択した座標は、4 つの座標間の選択された領域を強調表示する必要があります。

質問

緯度と経度の座標の配列を (反) 時計回りに並べ替えるにはどうすればよいですか?

ソリューションと検索

StackOverflow に関する質問

• サイズ変更可能な (交差しない) ポリゴンの描画
• 線が交差しないようにGoogleマップのポリゴン内のポイントをソートする方法は?
• 時計回りに 4 つの点を並べ替える

関連サイト

• http://www.daftlogic.com/projects-google-maps-area-calculator-tool.htm
• http://en.literateprograms.org/Quickhull_%28Javascript%29
• http://www.geocodezip.com/map-markers_ConvexHull_Polygon.asp
• http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

既知のアルゴリズム

• グラハムのスキャン (複雑すぎる)
• Jarvis March アルゴリズム (N ポイントを処理)
• 再帰凸包 (点を削除)

コード

これが私がこれまでに持っているものです：

ありがとうございました。

RealWorldHaskellの第3章をほぼ終了します。最後の運動は私をブロックします。実行中にコードがクラッシュします。誰かが私のコードのどの部分が間違っているか教えてもらえますか？ありがとう。

質問：前の3つの演習のコードを使用して、2Dポイントのセットの凸包に対してグラハムのスキャンアルゴリズムを実装します。凸包とは何か、およびグラハムスキャンアルゴリズムがどのように機能するかについての適切な説明は、ウィキペディアで見つけることができます。

答え：

だから私はグラハム スキャン アルゴリズムを使用して凸包を作成する必要がありますが、問題があります。

ここで、凸のランダムな点を追加します

ここで、開始する最初の最低点を見つけます。

ここで、残りのすべてのポイントを並べ替えます。

ここで凸を描きます。

誰かが私が間違っていることを教えてもらえますか?

グラハムのスキャン凸包アルゴリズムの実装を作成し、テストデータにポイントを使用しました

私のプログラムによると、凸包は

しかし、私は凸包が

https://github.com/shadwstalkr/GrahamScanDemo/でもポイントのセットを試してみましたが、同じ解決策も得られます。多くの不平と不平を言った後、ウィキペディアで「オブジェクト内のすべての点のペアについて、それらを結ぶ直線セグメント上のすべての点もオブジェクト内にある場合、オブジェクトは凸状である」と読みました。

私のポイントと船体を描いた後。私のプログラムはその定義内のオブジェクトを生成したようですが、それは単純に角度で並べ替えるだけで凸包が得られることを意味しませんか?

凸包が実際に何であるかを理解していないので、別の問題を解決しようとしていますか、それとも私の実装と shadwstalkr の両方が間違っていますか?

グラハム スキャン アルゴリズムを使用して、ポイント セットの凸包を見つけています。ポイントを極角で並べ替えようとしていますが、その方法がわかりません (ポイント セットを既に並べ替えています)。 Y 座標）。

私がすでに書いたものは次のようなものです：

CoordX 座標と Y 座標を として持つクラスはどこにありますかdouble。

また、誰かが C++ でこの角度を実装しようとした Stack Overflow の同様の投稿の 1 つを見ましたが、理解できませんqsqrt。Javaでこのようなものはありますか?

誰かが私を助けてくれたらうれしいです。

ウィキペディアの擬似コードからグラハム スキャンを実装しようとしていますが、物事を C# に変換する際に少し問題が発生しています。見ていただいてもよろしいでしょうか？

ここに私が持っているものがあります:

そして、このクラスを利用しています：

コードは爆発するのが好きです。主な理由は、すべてが異なる多数の疑似実装を読んだためであり、物事を十分に説明しているものはありません。配列の境界外エラーが発生しています。これは、coordinatesize、coordinatesize + 1、coordizesize - 1、coordizesize + killme のいずれであるかもわかりません。元は 'N' または 'N' でした。 +1' ですが、ご覧のとおり、私はこの翻訳についてゆっくりと気を失いつつあります。

グラハムスキャンを使用して凸包の周囲を計算するプログラムを作成しており、データポイントのセットで最小の y 座標を見つける必要があります。struct でstd::min_element(vector.begin(), vector.end())オーバーロードされた演算子を使用しています。問題は、いくつかの点が同じ最低の y 座標を共有している可能性があることです。その場合、それらの点の x 値を使用してそれらを比較する必要があります。すべてをループすることなく、他のポイントが min_element と同じ y を共有しているかどうかを確認する簡単なチートはありますか?<point

構造体:

関数呼び出し: