問題タブ [convex-hull]

標準の凸包アルゴリズムは、（経度、緯度）ポイントでは機能しません。これは、標準のアルゴリズムでは、デカルトポイントのセットのハルが必要であると想定しているためです。緯度-経度はデカルト座標ではありません。経度は反子午線（+/- 180度）で「ラップアラウンド」するためです。つまり、経度179の東2度は-179です。

したがって、ポイントのセットが反子午線にまたがる場合は、世界中に誤って伸びる偽の船体を計算します。

これを修正するために標準の凸包アルゴリズムで適用できるトリックの提案、または適切な「地球球」の船体アルゴリズムへのポインタはありますか？

今考えてみると、反マーディアンにまたがるよりも、考慮すべき興味深い事例があります。地球を取り囲む点の「バンド」を考えてみましょう。その凸包には東西の境界がありません。またはさらに、{（0,0）、（0、90）、（0、-90）、（90、0）、（-90、0）、（180、0）}の凸包は何ですか？-それは地球の表面全体を含んでいるように見えるでしょう、それでどの点がその周囲にありますか？

元の投稿：

凸多角形の最も外側の頂点を見つけようとしています（多角形の外側の点Pに関連して）。今のところ、私は長方形だけに関心があります（ただし、任意の凸多角形で機能するアルゴリズムが必要です）。

私の計画は、外部点Pから中心点Cまでの線を作成することです。この参照線から、点Pから点1、2、3、4までの線を作成します。ポイント2と4は、基準線から最大（最も正）と最小（最も負）の角度を持つため、最も外側の頂点として識別されます。

これは仕事に最適なアルゴリズムですか？参照角度から角度を計算するにはどうすればよいですか（できればJavaで）？

明確化のための更新：

線を引きました（赤の参照線）。ご覧のとおり、Pから2までの線は、基準線の一方の側に最大の角度を作成し、 Pから4までの線は、もう一方の側の最大の角度を作成します。したがって、これらは最も外側の頂点です。

入力のすべての点が凸包上にある場合、quickhull アルゴリズムでパフォーマンスの低下を回避するにはどうすればよいですか?

だから私は凸包アルゴリズムについて学んでいて、単純なブルートフォースからグラハム スキャンまでのすべてのアルゴリズムを書き上げています。

これは私のブルートフォース O(n^4) アルゴリズムです。最初に、すべてのポイントが船体の一部であると想定します。可能な三角形ごとに、三角形の内側にあるすべての点を削除します。最終的に、排除されなかったポイントは船体の一部になります。

Javaコードは次のとおりです（修正済み：Thomashのソリューションを使用）

これらの点を視覚的に見てみましたが、正しいようですが、凸包ポリゴンを描画するための点の順序を確立する方法がわかりませんか? どんな助けでも大歓迎です。

Open-CV 2.4 Android-Java:

私はこのような輪郭（MatofPointのリスト）を検索しました：

次に、凸包( MatofInt のリストでなければなりません)

凸包は MatofInt を必要としますが、drawcontours は MatofPoint を必要とします。

事前にThx..

編集：@OpenCV4Android

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

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

しかし、私は凸包が

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

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

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

CLRSから凸包を見つけるためにGraham Scan Algorithmを読んでいました。凸包の CLRS で指定されたアルゴリズムは ::

この行を理解できません (アルゴリズムのステップ 2):

2 つ以上の点が p0 に対して同じ極角を持っている場合、そのような最も遠い点を除くすべての点は、p0 と最も遠い点の凸結合であるため、考慮から完全に除外します。

1. これは何を意味するのでしょうか？複数の点が Po に対して同じ極角を持っている場合はどうすればよいですか?

また、私は構造を作ったとしましょう

2. C++ STL ライブラリを使用して並べ替えステップを実装するにはどうすればよいですか? つまり、でコンパレータ関数をどのように定義すればよいsort(P+1, P+N, comparator)ですか?

OpenCv を使用して指先を検出していますが、いくつか障害があります。私のプロジェクトでは、findContours、convexHull、convexityDefects メソッドが機能しません。質問するのは初めてです。みんなありがとう！

私のコードは以下の通りです：

これは私の手の写真です：

http://www.billwang.net/bbs/oldattach/2006/12/29/billwang_5315954-038-embed.jpg

*最大は画像内の私の最大の輪郭です

しかし、convexityDefectsは、「アサーションに失敗しました（hull.checkVector（1、CV_32S）> 2）」というエラーを表示します。誰かが私を助けてください、私はCソリューションの使用に頼りたくありません。

編集済み

それをconvexityDefectsに渡す前にタイプで作成しようとしましたvector<vector<int>>が、convexityDefectsで「アサーションに失敗しました（ptnum> 3）..」というエラーが発生します。