標準の凸包アルゴリズムは、（経度、緯度）ポイントでは機能しません。これは、標準のアルゴリズムでは、デカルトポイントのセットのハルが必要であると想定しているためです。緯度-経度はデカルト座標ではありません。経度は反子午線（+/- 180度）で「ラップアラウンド」するためです。つまり、経度179の東2度は-179です。
したがって、ポイントのセットが反子午線にまたがる場合は、世界中に誤って伸びる偽の船体を計算します。
これを修正するために標準の凸包アルゴリズムで適用できるトリックの提案、または適切な「地球球」の船体アルゴリズムへのポインタはありますか？
今考えてみると、反マーディアンにまたがるよりも、考慮すべき興味深い事例があります。地球を取り囲む点の「バンド」を考えてみましょう。その凸包には東西の境界がありません。またはさらに、{（0,0）、（0、90）、（0、-90）、（90、0）、（-90、0）、（180、0）}の凸包は何ですか？-それは地球の表面全体を含んでいるように見えるでしょう、それでどの点がその周囲にありますか？
標準の凸包アルゴリズムは、地球の表面上の座標のラップアラウンドではなく、より根本的な問題によって打ち負かされます。球の表面（地球の非球形度を忘れましょう）はユークリッド空間ではないため、ユークリッド幾何学は機能せず、基礎となる空間がユークリッドであると仮定する凸包ルーチン（そうでないものを見せてください） t、お願いします）動作しません。
球の表面は、線が大円であり、対蹠点が同じ点と見なされる楕円幾何学の概念に準拠しています。ユークリッドの凸性の概念を楕円空間に適用しようとすることから生じる問題をすでに経験し始めています。
オープンなアプローチの1つは、測地凸性の定義を採用し、測地凸包ルーチンを実装することです。それはかなり毛深いように見えます。また、（通常はユークリッドの）期待に一致する結果が得られない場合があります。多くの場合、3つの任意の点で、凸包は球の表面全体であることがわかります。
ナビゲーターや地図製作者が古くから採用している別のアプローチは、球の表面の一部（すべての点を含む部分）をユークリッド空間（地図投影の対象であり、私はあなたに迷惑をかけません）に投影することです。その上にある広範な文献を参照して）、投影された点の凸包を理解します。関心のある領域を平面に投影し、座標が回り込まないように調整します。たとえば、フランスに興味がある場合は、国全体が+ veの数値で調整されるように、30度を追加してすべての経度を調整できます。
私が書いている間、@ Li-aung Yipの回答で提案された、3D凸包アルゴリズムを使用するというアイデアは、私を誤った方向に導いてくれます。一連のサーフェスポイントの3D凸包には、球の内側にあるポイント、エッジ、および面が含まれます。これらは文字通り球の2D表面には存在せず、2Dでの完全に正しくない概念との格闘から3Dでのかなり間違った概念への取り組みを変えるだけです。さらに、私が参照したWikipediaの記事から、閉じた半球（つまり、その「赤道」を含む半球）は球の表面の形状が凸状ではないことを学びました。
データを緯度経度データと見なす代わりに、3D空間でデータを考慮し、3D凸包アルゴリズムを適用できますか？次に、3D凸包を分析することにより、必要な2D凸包を見つけることができる場合があります。
これにより、デカルト凸包のよく移動するアルゴリズムに戻り（3次元ではありますが）、座標のラップアラウンドに問題はありません。
あるいは、この論文があります：あなたが扱っているのと同じ問題のいくつか（座標ラップアラウンドなど）を扱っているように見える球上の単純なポリゴンの凸包の計算（1996） 。
すべてのポイントが半球内にある場合（つまり、地球の中心を通り、すべてを片側に配置する切断面を見つけることができる場合）、中央の別名心射方位図法を中心から行うことができます。切断面に平行な面にアースします。次に、すべての大円が投影で直線になるため、投影の凸包は地球上の正しい凸包にマッピングされます。ここの「心射方位図法」セクションの緯度線を見ると、緯度/経度の点がどれほど間違っているかがわかります（経度線はまっすぐなままであることに注意してください）。
（地球を球として扱うことはまだ完全には正しくありませんが、それは良い2番目の近似です。より現実的な地球（たとえばWGS84）を横切る真の最小距離パス上のポイントは、一般に、たぶん、彼らがそうするふりをすると、球で得られるものよりも良い近似が得られます。）
FutureNerd：
あなたは絶対に正しいです。私のアプリケーションでは、Maxy-Bとまったく同じ問題を解決する必要がありました。最初の反復として、（lng、lat）を（x、y）として扱い、標準の2Dアルゴリズムを実行しました。すべてのデータが米国本土にあるため、誰も近づきすぎない限り、これは問題なく機能しました。ただし、2回目の反復として、私はあなたのアプローチを使用し、概念を証明しました。
ポイントは同じ半球になければなりません。結局のところ、この半球を選択することは簡単ではありません（私が最初に推測したように、それはポイントの中心だけではありません）。説明のために、次の4つのポイントを考えてみましょう：（0,0）、（-60,0）、 （+60,0）赤道に沿って、（0,90）北極。ただし、「中心」を定義することを選択した場合、それらの中心は対称性によって北極上にあり、4つの点はすべて北半球にあります。ただし、4番目のポイントをたとえば（-19、64）アイスランドに置き換えることを検討してください。現在、それらの中心は北極ではなく、アイスランドに向かって非対称に描かれています。ただし、4つのポイントはすべて北半球にあります。さらに、北極によって一意に定義されている北半球は、彼らが共有する唯一の半球です。したがって、この「極」の計算は、代数ではなくアルゴリズムになります。
Pythonコードについては、私のリポジトリを参照してください： https ://github.com/VictorDavis/GeoConvexHull
この質問は少し前に答えられましたが、私の研究の結果を要約したいと思います。
球形の凸包は、基本的に非対蹠点に対してのみ定義されます。すべての点が同じ半球上にあると仮定すると、2つの主な方法で凸包を計算できます。
参考までに、Pythonで私は自分自身の実装に取り組んでいます。これは現在、北半球のポイントに対してのみ機能します。
MathOverflowに関するこの質問も参照してください。
球形の凸包のすべてのエッジは大円として表示/処理できます（最終的に、ユークリッド空間の凸包のすべてのエッジは（線分ではなく）線として処理できます）。これらの大円のそれぞれは、球を2つの半球に切断します。したがって、それぞれの大円を制約として考えることができます。凸包内にある点は、各制約によって定義された各半球上にあります。
元のポリゴンの各エッジは、凸包の候補エッジです。それが実際に凸包のエッジであるかどうかを確認するには、ポリゴンのすべてのノードが、問題のエッジの2つのノードを通過する大円によって定義される半球上にあるかどうかを確認する必要があります。ただし、ポリゴンの凹状ノードを超える新しいエッジを作成する必要があります。
しかし、むしろショートカット/ブルートフォース攻撃をしましょう。ポリゴン内のノードのすべてのペアの間に大円を描きます。これを両方向で行います（つまり、AをBに接続する大円とBをAに接続する大円）。したがって、Nノードのポリゴンの場合、N^2の大円になります。これらの大円のそれぞれは、候補制約（つまり、凸多角形の候補エッジ）です。これらの大円の一部は元のポリゴンのエッジと重なりますが、ほとんどは重なりません。ここで、もう一度覚えておいてください。各大円は、球を1つの半球に拘束する拘束です。次に、元のポリゴンのすべてのノードが制約を満たしているかどうかを確認します（つまり、すべてのノードが大円で定義された半球上にあるかどうか）。はいの場合、この大円は凸包の端です。もしも、
これの美しさは、緯度と経度を単位球を指すカルテシアンベクトルに変換すると、実際には内積と外積が必要になることです-外積によって球上の2点を通過する大きな円が見つかります-大円と点の内積が0より大きい（または等しい）場合、点は大円によって定義される半球上にあります。したがって、エッジの数が多いポリゴンの場合でも、このブルートフォース法は問題なく機能するはずです。 。