地理圍欄 - 點內部/外部多邊形

Question

我想確定一個多邊形並實現一個算法，該算法將檢查點是在多邊形的內部還是外部。

有誰知道是否有任何類似的算法可用的例子嗎？

Answer 1

只需看看point-in-polygon (PIP) problem。

Answer 2

如果我沒記錯的話，算法是在你的測試點畫一條水平線。計算您相交的多邊形的多少線以達到您的要點。

如果答案很奇怪，你就在裏面。如果答案是偶然的，你就在外面。

編輯：是的，有什麼he說（Wikipedia）：

Answer 3

檢查點是多邊形內或不 -

，不妨考慮頂點A1，A2的多邊形，A3 ，A4，A5。下列步驟應該有助於確定P點是位於多邊形內部還是外部。

計算由邊a1-> a2和連接a2到P和P到a1的矢量形成的三角形的矢量區域。類似地，計算每個可能的三角形的矢量面積，其中一個邊作爲多邊形的一側，另外兩個連接P到那邊。

對於要在多邊形內部的點，每個三角形都需要有正面區域。即使其中一個三角形具有負面區域，點P也不在多邊形中。

爲了計算表示其3個邊的三角形給定矢量的區域，是指http://www.jtaylor1142001.net/calcjat/Solutions/VCrossProduct/VCPATriangle.htm

Answer 4

的問題是容易，如果您的多邊形是凸的。如果是這樣，你可以對每條線做一個簡單的測試，看看該點是在該線的內部還是外部（在兩個方向上都延伸到無窮大）。否則，對於凹多邊形，從你的點向無窮遠（在任何方向）繪製虛射線。計算它跨越邊界線的次數。奇數意味着點在裏面，甚至意味着點在外面。

這最後一個算法比看起來更復雜。當你的虛射線正好碰到多邊形的一個頂點時，你將必須非常小心。

如果您的假想射線沿-x方向走，您可以選擇僅計算包含至少一個點的線，該點的y座標嚴格小於您的點的y座標。這就是你如何讓大多數奇怪的邊緣情況正常工作。

Answer 5

到目前爲止，最好的解釋和執行可以在 Point In Polygon Winding Number Inclusion

發現甚至有一個C++實現在井的最後解釋的文章。該網站還包含一些針對其他基於幾何的問題的優秀算法/解決方案。

我修改並使用了C++實現，並創建了一個C＃實現。你一定要使用繞線數算法，因爲它比邊緣交叉算法更精確，而且速度非常快。

Answer 6

如果您有一個簡單的多邊形（沒有任何線交叉），並且您沒有孔，也可以對多邊形進行三角化，無論如何，您可能要在GIS應用中繪製TIN，然後測試爲每個三角形中的點。如果多邊形的邊數少，但點數多，則速度快。

對於三角形中的一個有趣的觀點看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; 
} 

祿類

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（串latlnglist，串LAT，串LNG） {

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 .... A的順序列表 無邊AB，BC ...跨越任何其他側

確定框Xmin時，的Xmax，YMIN，YMAX

殼體1的測試點P位於盒

殼體2的測試點P的外側位於盒內部：

確定箱子的直徑D {[Xmin，Ymin] - [Xmax，Ymax]}（並加一點額外的以避免與D在一側可能的混淆）

確定所有邊的梯度M

查找梯度山最不同於所有梯度中號

測試線與P在梯度運行山爲零

的距離D.

設置交叉點的計對於每一個側面的AB，BC測試PD從側面 到它的交點，但不包括其末端。如果需要，增加交叉點的數量 。需要注意的是，從P到路口零距離表明，P是在一個側面

奇數計數指示P是多邊形

Answer 12

剛擡起頭（使用的答案，我不能評論），如果內您想要使用多邊形中的點進行地理圍欄，那麼您需要更改算法以使用球形座標。 -180經度與180度經度相同，並且在這種情況下多邊形點將打破。

Answer 13

我翻譯了PHP中的c＃方法，並且我添加了許多註釋來理解代碼。

PolygonHelps說明：
檢查點是在多邊形的內部還是外部。這個程序使用gps座標，當多邊形有一個小的地理區域時它就起作用。


INPUT：
$ poly：點陣列：多邊形頂點列表; [{Point}，{Point}，...];
$點：指向檢查;點：{「lat」=>「x.xxx」，「lng」=>「y.yyy」}



當$ c爲false時，與多邊形的交點數是偶數，所以點在多邊形;
當$ c爲真時，與多邊形的交點數是奇數，所以點在多邊形內;
$ n是多邊形中的頂點數目;
對於多邊形中的每個頂點，方法計算通過當前頂點和前一個頂點的直線，並檢查兩條直線是否有交點。交點存在時，$ 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座標都是負面的。 所有這些算法都會給出錯誤的結果。

最簡單的方法是使用所有點的緯度和長度的絕對值。在那種情況下，揚·科伯斯基的算法是完美的。