ジオフェンシングポイント内/外ポリゴン

Question

ポリゴンを決定し、ポイントがポリゴンの内側か外側かをチェックするアルゴリズムを実装したいと思います。

類似のアルゴリズムを使用できる例があるかどうかは知っていますか？

Answer 1

point-in-polygon (PIP) problemをご覧ください。

Answer 2

正しく覚えていれば、アルゴリズムはテストポイントに水平線を引くことです。あなたのポイントに達するために交差するポリゴンの線の数を数えます。

答えが奇妙な場合、あなたは内部です。答えが偶数であれば、あなたは外にいる。

編集：うん、何he（Wikipedia）言った：

Answer 3

チェックポイントは、多角形の内側であるかどうか -

は、A2、A3を頂点A1を持つ多角形を考えてみましょう、a4、a5。以下のステップのセットは、点Pがポリゴンの内側か外側にあるかを確認するのに役立つはずです。

エッジa1-> a2によって形成される三角形のベクトル領域と、a2をPとPとをa1に結ぶベクトルを計算します。同様に、一方の側をポリゴンの側とし、他方の2つをその側に接続する可能性のある三角形のベクトル領域を計算します。

ポイントがポリゴンの内側にある場合、各三角形は正の面積を持つ必要があります。三角形の1つが負の領域を有していても、点Pはポリゴンからはみ出している。

あなたの多角形が凸状である場合は、問題がより容易であるhttp://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Answer 4

を参照して、その3辺を表すベクトル所与の三角形の面積を計算するために。そうであれば、各行に対して簡単なテストを行い、その点がその線の内側か外側にあるか（両方向で無限に伸びているかどうか）調べることができます。それ以外の場合は、凹面ポリゴンの場合は、ポイントから無限に（任意の方向）仮想線を描きます。境界線を何回横切るかを数えます。奇妙なことは、ポイントが内側にあることを意味し、ポイントが外側にあることを意味します。

この最後のアルゴリズムは見た目よりもトリッキーです。仮想線がポリゴンの頂点の1つに正確に当たったときに何が起こるかについて非常に注意する必要があります。

仮想線が-x方向に向いている場合、y座標が厳密にポイントのy座標より小さい少なくとも1つの点を含む行だけをカウントすることができます。これは、奇妙なエッジケースのほとんどを正しく動作させる方法です。

Answer 5

は、これまでで最高の説明と実装は、物品を説明したほかの末尾にC++の実装もあり Point In Polygon Winding Number Inclusion

で見つけることができます。このサイトには、他のジオメトリベースの問題に対するいくつかの素晴らしいアルゴリズム/ソリューションも含まれています。

私はC++の実装を変更して使用し、C＃の実装も作成しました。あなたは間違いなく、それがエッジ交差アルゴリズムよりも正確であり、非常に高速であるので、巻線番号アルゴリズムを使用したいと思います。

Answer 6

あなたは、単純なポリゴンを（行のどれも交差しない）持っていて、穴を持っていない場合は、テスト、その後、あなたはおそらくTINを描画するためにGISアプリでとにかくやろうとしているポリゴンを、三角測量することができます各三角形の点についてポリゴンのエッジ数は少ないが、多数のポイントがある場合は速いです。三角形で興味深い点について

link text

参照それ以外の場合は間違いなくエッジ交差は、データが生成される場合には限られた精度のGPSを形成する縁部上の点と実際の問題を有し、巻ルールはなくエッジ交差している使用可能性が非常に高い。

Answer 7

は、C＃にウェブを検索し、様々な実装をしようとし、C++からそれらを移植した後、私は最終的にまっすぐ私のコードを持って：

 public static bool PointInPolygon(LatLong p, List<LatLong> poly) 
    { 
     int n = poly.Count(); 

     poly.Add(new LatLong { Lat = poly[0].Lat, Lon = poly[0].Lon }); 
     LatLong[] v = poly.ToArray(); 

     int wn = 0; // the winding number counter 

     // loop through all edges of the polygon 
     for (int i = 0; i < n; i++) 
     { // edge from V[i] to V[i+1] 
      if (v[i].Lat <= p.Lat) 
      {   // start y <= P.y 
       if (v[i + 1].Lat > p.Lat)  // an upward crossing 
        if (isLeft(v[i], v[i + 1], p) > 0) // P left of edge 
         ++wn;   // have a valid up intersect 
      } 
      else 
      {      // start y > P.y (no test needed) 
       if (v[i + 1].Lat <= p.Lat)  // a downward crossing 
        if (isLeft(v[i], v[i + 1], p) < 0) // P right of edge 
         --wn;   // have a valid down intersect 
      } 
     } 
     if (wn != 0) 
      return true; 
     else 
      return false; 

    } 

    private static int isLeft(LatLong P0, LatLong P1, LatLong P2) 
    { 
     double calc = ((P1.Lon - P0.Lon) * (P2.Lat - P0.Lat) 
       - (P2.Lon - P0.Lon) * (P1.Lat - P0.Lat)); 
     if (calc > 0) 
      return 1; 
     else if (calc < 0) 
      return -1; 
     else 
      return 0; 
    } 

をisLeft機能は私に丸めの問題を与えていたと私は私がしたことを認識せずに時間を費やし間違った変換をしているので、その機能の最後にブロックされている場合、私はラメのために私を許してください。

ところで、これは元のコードとの記事です： http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Answer 8

私は簡単でより効率的なソリューションがあると思います。ここで

は、C++のコードです。私はそれをC＃に変換するのは簡単なはずです。

int pnpoly(int npol, float *xp, float *yp, float x, float y) 
{ 
    int i, j, c = 0; 
    for (i = 0, j = npol-1; i < npol; j = i++) { 
    if ((((yp[i] <= y) && (y < yp[j])) || 
     ((yp[j] <= y) && (y < yp[i]))) && 
     (x < (xp[j] - xp[i]) * (y - yp[i])/(yp[j] - yp[i]) + xp[i])) 
     c = !c; 
    } 
    return c; 
} 

Answer 9

C＃コード

bool IsPointInPolygon(List<Loc> poly, Loc point) 
{ 
    int i, j; 
    bool c = false; 
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) 
    { 
     if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) 
       || ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) 
       && (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt) 
        /(poly[j].Lt - poly[i].Lt) + poly[i].Lg)) 

      c = !c; 
     } 
    } 

    return c; 
} 

のLocクラス

public class Loc 
{ 
    private double lt; 
    private double lg; 

    public double Lg 
    { 
     get { return lg; } 
     set { lg = value; } 
    } 

    public double Lt 
    { 
     get { return lt; } 
     set { lt = value; } 
    } 

    public Loc(double lt, double lg) 
    { 
     this.lt = lt; 
     this.lg = lg; 
    } 
} 

Answer 10

asp.Net C＃で完全なソリューション、あなたはここで完全な詳細を見ることができ、あなたはどのように見ることができます緯度と経度を使ってポリゴンの内側か外側かを調べる（lat、lon）か？ Article Reference Link

プライベート静的ブールcheckPointExistsInGeofencePolygon（文字列LNG、LATストリングlatlnglist、列） {

List<Loc> objList = new List<Loc>(); 
    // sample string should be like this strlatlng = "39.11495,-76.873259|39.114588,-76.872808|39.112921,-76.870373|"; 
    string[] arr = latlnglist.Split('|'); 
    for (int i = 0; i <= arr.Length - 1; i++) 
    { 
     string latlng = arr[i]; 
     string[] arrlatlng = latlng.Split(','); 

     Loc er = new Loc(Convert.ToDouble(arrlatlng[0]), Convert.ToDouble(arrlatlng[1])); 
     objList.Add(er); 
    } 
    Loc pt = new Loc(Convert.ToDouble(lat), Convert.ToDouble(lng)); 

    if (IsPointInPolygon(objList, pt) == true) 
    { 
      return true; 
    } 
    else 
    { 
      return false; 
    } 
} 
private static bool IsPointInPolygon(List<Loc> poly, Loc point) 
{ 
    int i, j; 
    bool c = false; 
    for (i = 0, j = poly.Count - 1; i < poly.Count; j = i++) 
    { 
     if ((((poly[i].Lt <= point.Lt) && (point.Lt < poly[j].Lt)) | 
      ((poly[j].Lt <= point.Lt) && (point.Lt < poly[i].Lt))) && 
      (point.Lg < (poly[j].Lg - poly[i].Lg) * (point.Lt - poly[i].Lt)/(poly[j].Lt - poly[i].Lt) + poly[i].Lg)) 
      c = !c; 
    } 
    return c; 
} 

Answer 11

ポリゴンを点対A、B、Cの順次リストとして定義されている.... サイドAB、BC ...

：他側

ボックスXminと、をXmax、Yminと、Ymaxの

テストポイントPは、テスト点Pがボックス内にあるボックス

ケース2の外側にある

ケース1を決定横切りますボックスの「直径」Dを決定する。（そして、Dminとの混同を避けるために少し余分を加える。）

すべての辺の勾配Mを決定する。

勾配マウント全て勾配から最も異なるM

試験線は勾配山でPから辺のそれぞれについてD.

がゼロ

に交差点の数を設定された距離を実行して下さいAB、BC側のPDと交差点があるかどうかを調べます。 開始から終了までは含みません。必要に応じて交点の数を増やす 場合、Pから交差点までゼロ距離はPがサイド

ONであることを示している奇数カウントが（私はコメントすることはできませんと答えを使って）Pが多角形の内部にある

Answer 12

ジャストヘッドアップしていることに注意してくださいジオフェンシングにポリゴンポイントを使用する場合は、球座標を使用するようにアルゴリズムを変更する必要があります。経度-180は経度180と同じであり、ポリゴンのポイントはこのような状況で壊れます。

Answer 13

私はPHPでC＃メソッドを翻訳しました。コードを理解するために多くのコメントを追加しました。

ポリゴンの説明：
ポイントがポリゴンの内側か外側かを確認します。この手順では、gps座標を使用し、ポリゴンの地理的エリアがわずかである場合に機能します。


INPUT：
$ poly：Pointの配列：ポリゴンの頂点リスト。 [{Point}、{Point}、...];
$ point：チェックするポイント。


$ cをfalseにすると、ポリゴンとの交点の数が偶数であるため、点が外にあります。点：{"lat" => "x.xxx"、 "lng" => "y.yyy"}ポリゴン;
$ cが真の場合、ポリゴンとの交点の数が奇数なので、点はポリゴンの内側です。
$ nはポリゴンの頂点の数です。
ポリゴンの各頂点について、線の現在の頂点と前の頂点を計算し、2つの線が交点を持つかどうかをチェックします。
交点が存在すると$ cが変化します。
したがって、メソッドは、ポイントがポリゴンの内側にある場合はtrueを返し、そうでない場合はfalseを返します。

class PolygonHelps { 

    public static function isPointInPolygon(&$poly, $point){ 

     $c = false; 
     $n = $j = count($poly); 


     for ($i = 0, $j = $n - 1; $i < $n; $j = $i++){ 

      if (((($poly[$i]->lat <= $point->lat) && ($point->lat < $poly[$j]->lat)) 
       || (($poly[$j]->lat <= $point->lat) && ($point->lat < $poly[$i]->lat))) 

      && ($point->lng < ($poly[$j]->lng - $poly[$i]->lng) 
           * ($point->lat - $poly[$i]->lat) 
          /($poly[$j]->lat - $poly[$i]->lat) 
           + $poly[$i]->lng)){ 

       $c = !$c; 
      } 
     } 

     return $c; 
    } 
} 

Answer 14

私は地球の南に住んでいる人々を助けるために一つの細部を加えます!! ブラジルにいる場合（私の場合）、私たちのGPSコードはすべてネガティブです。 これらのすべてが間違った結果をもたらします。

すべての点の緯度と経度の絶対値を使用するのが最も簡単な方法です。その場合、Jan Koberskyのalgoは完璧です。