標準的なアルゴリズムでは、デカルト座標の集合の船体が必要と仮定しているので、標準の凸包アルゴリズムは（経度、緯度）点では機能しません。緯度経度のポイントはではなくデカルトで、反経絡（+/- 180度）で経度が「ラップアラウンド」するためです。つまり、経度179の2度東は-179です。球の表面上の（経度、緯度）点の凸包
あなたのポイントのセットが反経絡に跨っている場合、間違って世界中に広がっている擬似外殻を計算します。
私は標準的な凸包アルゴリズムを使ってこれを修正するか、適切な "地球球"のハルアルゴリズムを指し示すことができますか？
ここで私はそれについて考えていますが、反メルェンを跨ぐよりも面白いケースがあります。地球を囲む点の「バンド」を考えてみましょう。その凸包は東西境界を持たないでしょう。さらに、{（0,0）、（0,90）、（0、-90）、（90,0）、（-90,0）、（180,0）}の凸包は何ですか？ - それは地球の表面全体を含むように見えるので、どの点がその周囲にあるのですか？
標準凸包アルゴリズムはラッピングに負けていない（、ラップアラウンドなどの座標） - 地球の表面上の座標の近似ですが、より根本的な問題です。球体の表面は、ユークリッド空間ではないので、ユークリッド空間はユークリッド空間ではないので、ユークリッド空間はユークリッド空間であると仮定する凸包法（ユークリッド空間） t、please）は動作しません。
球の表面は、elliptic geometryのコンセプトに従います。ここで、線は大きな円であり、対角線の点は同じ点と見なされます。あなたはすでに、楕円空間にユークリッドの凸包概念を適用しようとすることから生じる問題を体験し始めました。
あなたには、geodesic convexityという定義を採用し、測地線凸包ルーチンを実装する方法があります。それはかなり毛深いです。そして、あなたの（一般的にユークリッドの）期待に沿う結果を生み出すことはできません。多くの場合、3つの任意の点について、凸包は球の表面全体であることが分かります。
年齢によって航海者や地図作成者が採用するアプローチは、球の表面の一部（あなたのすべてのポイントを含む部分）をユークリッド空間（地図投影の対象です）に投影することですその上の広範な文献への言及をあなたに迷惑をかける）、投影された点の凸包を理解する。興味のある領域を平面上に投影し、ラップアラウンドしないように座標を調整します。たとえば、フランスに興味がある場合は、30degを追加してすべての経度を調整して、全国が+ ve数で調整されるようにすることができます。
私が書いている間に、@ 3Dの凸包アルゴリズムを使った@ Li-aung Yipの答えで提案されたアイデアは、私を誤ったものにしています。サーフェスポイントのセットの3D凸包は、球の内側にある点、エッジ、および面を含みます。これらは文字通り球の2D表面上には存在せず、難易度は2Dのかなり正しさのない概念から3Dのかなり間違ったものに変わるだけです。さらに、私はウィキペディアの記事から、閉じた半球（すなわち、その赤道を含むもの）が球の表面の幾何学的形状に凸ではないことを指摘しました。
私は主に、思考のための食物として3D凸包アルゴリズムの応用を提案しました。OPが彼が使用しようとしているデータに関するより多くの情報（ある国の中のポイント、世界中のすべての首都のリスト）を提供できるなら、それは助けになるかもしれません。 –
すばらしい答えをありがとう。測地学的凸凹は非常に興味深いものであり、非ユークリッドの文脈への凸性の他の一般化もそうである。しかし、私の直ちに必要とするのは、緯度/経度の点に単純な線形変換を適用して、反経絡を超えないようにするだけで十分です。 –
データを緯度経度データとみなす代わりに、3D空間で考慮して3D convex hull algorithmを適用できますか？ 3D凸包を解析することによって、あなたが望む2D凸包を見つけることができます。
これは、（3次元ではあるが）デカルト座標系の凸包のアルゴリズムによく似ており、座標の折返しには問題ありません。
代わりに、この論文があります：あなたが扱っている同じ問題のいくつかに対処するようですComputing the Convex Hull of a Simple Polygon on the Sphere (1996)が
PDFへのリンクありがとうございますが、完全な論文ではなく、講演の要約（PDF自体）のようです。 –
3Dハルのアイデアに関しては、すべての（定義によって）3D点が球の表面上にあるため、結果の3D凸包にそれらが含まれているとは限りません。そのような船体はいかなる情報にも寄与しない。 –
はい、すべての点が凸包の一部になりますが、3D凸包が特定の形状（すなわち半球）を持つことがあると考えてください。半球の「端」にある点の集合を見つけると便利です。 –
すべてのポイントが半球内にある場合（つまり、地球の中心を通るカットプレーンをすべて片側に置くカットプレーンを見つけることができれば）、中央の別名gnomicと呼ばれるgnomonic投影を行うことができます地球の中心を切断平面に平行な平面に投影します。 すべての大きな円はプロジェクションの直線になり、プロジェクションの凸包は地球上の正しい凸包にマップされます。 「Gnomonic Projection」セクションhereの緯度線を見ると、緯度/経度の点数が間違っていることがわかります（経度線はまっすぐのままです）。
（球体としての地球の扱いはそれほど正しいわけではありませんが、2番目の近似式です）より現実的な地球（例：WGS84）の真の最短距離の点は一般的には。中心を通る平面は、彼らがたぶんふりあなたが球を得るものよりも良い近似を与える）
FutureNerd：。
あなたは絶対的に正しいです。自分のアプリケーションでMaxy-Bとまったく同じ問題を解決しなければならなかった。最初の反復として、（lng、lat）を（x、y）として扱い、標準の2Dアルゴリズムを実行しました。すべてのデータが連続した米国にあったので、これは誰も近づかない限りうまくいきました。しかし、2回目の繰り返しとして、私はあなたのアプローチを使ってそのコンセプトを証明しました。
ポイントは同じ半球になければなりません。明らかに、この半球の選択は重要ではありません（最初に推測したように、ポイントの中心ではありません）。説明するために、（0,0）、（-60,0）、赤道に沿って（+60,0）、北極に（0,90）。しかし、あなたは「中心」を定義することを選択しますが、それらの中心は対称によって北極にあり、4つの点はすべて北半球にあります。しかし、第4の点をアイスランド（-19,64）と置き換えることを検討してください。今や彼らの中心は北極にはなく、アイスランドに向かって非対称に描かれています。しかし、4つのポイントはすべて、まだ北半球にある。さらに、北半球によって独特に定義された北半球は、彼らが共有する唯一の半球である。したがって、この「極」を計算することは、代数的ではなくアルゴリズム的になります。偉大な、示唆に富む質問に対して https://github.com/VictorDavis/GeoConvexHull
1：
はPythonコードのための私のリポジトリを参照してください。 –
ここをクリックしてください：http://stackoverflow.com/a/9612324/817828 – TreyA