迭代多邊形中的每個點

Question

假設我在網格環境中具有某個多邊形的頂點，如何迭代它包含的每個單元格（包括邊上的那些單元格）？

爲了澄清，我有以下的頂點（算作如果左上爲(0, 0)）：

//each point is [x, y] 
var verts = [ 
    [1, 1], 
    [3, 1], 
    [3, 2], 
    [4, 2], 
    [4, 4], 
    [0, 4], 
    [0, 3], 
    [1, 3] 
]; 

這將定義一個多邊形像這樣：

其中每個綠根據上面的頂點，點是我想要迭代的一個點。頂點沿着多邊形邊緣走向的方向沒有任何圖案，它可以圍繞多邊形順時針或逆時針旋轉。但是，他們會處於有序狀態;也就是說，如果您放下筆並按順序移動到每個頂點，而不擡起，並且它將繪製輪廓而不跨越多邊形。

用例是我從通過畫布API加載的PNG中獲得imageData。這PNG被分成「區域」，我需要迭代當前「區域」的每個像素。每個「區域」由上面的頂點數組定義。

我嘗試了類似下面的內容，這將創建一個正方形來遍歷數組中每個4個頂點的集合。

for(var v = 0, vl = verts.length - 4; v < vl; ++v) { 
    //grabbing the minimum X, Y and maximum X, Y to define a square to iterate in 
    var minX = Math.min(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]), 
     minY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]), 
     maxX = Math.max(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]), 
     maxY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]); 

    for(var x = minX; x < maxX; ++x) { 
     for(var y = minY; y < maxY; ++y) { 
      //do my checks on this pixel located at X, Y in the PNG 
     } 
    } 
} 

兩個大問題，雖然：

1. 它可以在多邊形內重複點，
2. 它可以搶分的多邊形外

我能解決第一通過跟蹤我檢查哪些點來發布，所以我不重複檢查。第二個問題只能通過對每個點執行PointInPoly檢查來解決，這會使該解決方案比我想要的要重得多。

EDIT
迭代的整個圖像中的每個像素和施加PointInPoly檢查每個也是不可接受的;它會比上面的算法更慢。

Answer 1

如果您的多邊形是凸的，你可以做到以下幾點：

• 的多邊形表示裏面一側，一面外的每個邊緣創建一個行（這是基於正常的，它可以是取決於卷繞方向）
• 對於已經計算的邊界框內的每個像素，檢查像素是否在線的內側。如果像素位於任何線條的外側，則它位於多邊形之外。如果它在裏面，那麼它就在裏面。

的基本算法就是從這裏開始：https://github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

如果你的多邊形不凸的，那麼我會做的是實際繪製在已知的色彩在畫布上的多邊形，然後應用iterative flood fill algorithm。這就要求你至少知道一個像素位於內部，但這不應該是一個昂貴的測試。但是如果你不能在屏幕外的緩衝區（不熟悉canvas標籤）做到這一點，那麼這可能不適用於JavaScript。