計算多邊形內的像素

在爲學校分配時，我們需要做一些圖像識別，我們必須找到機器人的路徑。計算多邊形內的像素

到目前爲止，我們已經能夠找到圖像中的所有多邊形，但現在我們需要生成一個像素圖，稍後將用於astar算法。我們已經找到了一種方法來做到這一點，下面顯示，但問題是，這是非常緩慢的，因爲我們通過每個像素，並測試它是否在多邊形內。所以我的問題是，有沒有一種方法可以更快地生成像素圖？

我們有座標列表爲多邊形

功能「的GetMap」之稱，以獲得像素映射

public Point[] getMap() 
{ 
    List<Point> points = new List<Point>(); 
    lock (hull) 
    { 
     Rectangle rect = getRectangle(); 
     for (int x = rect.X; x <= rect.X + rect.Width; x++) 
     { 
      for (int y = rect.Y; y <= rect.Y + rect.Height; y++) 
      { 
       if (inPoly(x, y)) 
        points.Add(new Point(x, y)); 
      } 
     } 
    } 
    return points.ToArray(); 
}

獲取矩形就是用來限制搜索，本身我們不必走完整個圖像

public Rectangle getRectangle() 
{ 
    int x = -1, y = -1, width = -1, height = -1; 
    foreach (IntPoint item in hull) 
    { 
     if (item.X < x || x == -1) 
      x = item.X; 
     if (item.Y < y || y == -1) 
      y = item.Y; 


     if (item.X > width || width == -1) 
      width = item.X; 
     if (item.Y > height || height == -1) 
      height = item.Y; 


    } 
    return new Rectangle(x, y, width-x, height-y); 
}

而atlast這是我們如何檢查，看看是否ap ixel是多邊形

public bool inPoly(int x, int y) 
{ 
    int i, j = hull.Count - 1; 
    bool oddNodes = false; 

    for (i = 0; i < hull.Count; i++) 
    { 
     if (hull[i].Y < y && hull[j].Y >= y 
     || hull[j].Y < y && hull[i].Y >= y) 
     { 
      try 
      { 
       if (hull[i].X + (y - hull[i].X)/(hull[j].X - hull[i].X) * (hull[j].X - hull[i].X) < x) 
       { 
        oddNodes = !oddNodes; 
       } 
      } 
      catch (DivideByZeroException e) 
      { 
       if (0 < x) 
       { 
        oddNodes = !oddNodes; 
       } 
      } 
     } 
     j = i; 
    } 
    return oddNodes; 
}

來源

2010-05-05 Androme

你可能想要尋找一個Plygon Triangulation算法。

另外，請注意，捕獲異常要花費更多的時間來檢查正確的條件。所以我建議你到現有的代碼轉換成：

public bool inPoly(int x, int y) 
    { 
     int i, j = hull.Count - 1; 
     var oddNodes = false; 

     for (i = 0; i < hull.Count; i++) 
     { 
      if (hull[i].Y < y && hull[j].Y >= y 
       || hull[j].Y < y && hull[i].Y >= y) 
      { 
       var delta = (hull[j].X - hull[i].X); 
       if (delta == 0) 
       { 
        if (0 < x) oddNodes = !oddNodes; 
       } 
       else if (hull[i].X + (y - hull[i].X)/delta * delta < x) 
       { 
        oddNodes = !oddNodes; 
       } 

      } 
      j = i; 
     } 
     return oddNodes; 
    }

來源

2010-05-05 09:20:16

好的，謝謝你的小費 – Androme 2010-05-08 20:53:23

謝謝您的回答。它是否適用於所有的多邊形形狀？ – NrNazifi 2013-09-17 07:36:07

上有多邊形命中測試了一些有趣的討論here裏面，但它的聲音對我來說，就好像你可能是一個多邊形填充更好。

來源

2010-05-05 09:04:14 msandiford

感謝參考，它幫助了很多 – smoothumut 2018-02-06 12:09:02

計算多邊形內的像素

回答

相關問題