ジオフェンシングのためにポリゴンを埋め込んだ円形のジオフェンス領域を作成するには？

Question

私は、IOS用のポリゴンジオフェンシングを実装する最善の方法を試しています。私はこれを参照しましたquestion

私は最初のアプローチを試みています。私はそのアプローチを実装するためのコードの助けが必要です。

ポリゴンの座標を使用して、円形ジオフェンシング領域を作成する方法は？ ポリゴン座標を埋め込んだ円形領域を作成するアルゴリズムはありますか？

本当にありがとうございます。ありがとう！

Answer 1

あなたが直面している問題は、The Smallest Circleという問題です。

基本的に、ポイントのリストを含む最小の円を探しています。

グーグルでは、直線的な時間内に行うことができます。

アルゴリズムはthusly記載され...

アルゴリズムは、処理点の集合PとPの和集合を囲む最小円の場合と同様に維持し、ランダムな順序でSの点を処理します各ステップで、処理される次の点rがこの円に属するかどうかを検査する。もしそうでなければ、アルゴリズムは包囲する円を、集合PおよびQ + r上のアルゴリズムの再帰呼び出しの結果で置き換える。したがって、円が置換されたかどうかに関わらず、rは集合Pに含まれます。したがって、各点の処理は、点が単一の円に属するかどうかを一定時間テストし、場合によってはアルゴリズムを再帰的に呼び出します。処理対象のi番目の点は、再帰呼び出しを生成する確率 O （I / ） O（1/I）を有することを示すことができ、全体的な時間は、線形従ってあること。

Here is the Wikipedia link about the problem.

あなたはおそらくここからこの問題についてたくさんのより多くのリソースを見つけることができます。

希望に役立ちます。

Here is another site that possibly provides a more complete solution