查找由相鄰網格點構成的多邊形的所有內部網格點

我有Points（int x，int y）的列表。在一起，他們形成區域，我檢查這個區域是否關閉，然後我需要獲得內部區域形成的所有位置在這個區域內。查找由相鄰網格點構成的多邊形的所有內部網格點

例區域：

enter image description here

唯一的想法我已經是這個領域轉換爲載體，檢查每一個點，如果它是多邊形內部與否，計數點的多邊形軸的的交點。

但我認爲這不是最有效的方法。

其他的想法是首先獲得所有外面的點，我從角落開始（如果角點不是點列表的一部分，那麼100％是空的），添加所有空的重複點。然後所有不在外面的點不在高亮列表中。

但同樣，感覺莫名其妙累贅......

來源

2013-02-04 user2039330

聽起來很像[凸包]（http://en.wikipedia.org/wiki/Convex_hull）。 – Dukeling

這些區域是否總是很簡單，或者它們是否可以像字母O那樣有洞？ –

1.你想找到有界數字的區域或其內的點數？ 2.什麼意思是該地區關閉？這是否意味着它的形狀要麼與座標線平行，要麼形成45度。與他們的角度？ –

爲了找到網格多邊形的所有內部網格點，可以利用這些觀察：

針對每個內部網格點（X，Y）還（X，Y + 0.5）和（x軸，y軸0.5）是內點。
由y=n+0.5限定的線具有與網格多邊形

這導致下面的算法簡單交點：

作爲先決條件人們需要所有非水平（即垂直和對角線）多邊形邊緣，實際上每個（第二）中間行只有中心的x座標以升序排列。
在每個第二水平「中線」即y=2n+0.5處掃描網格，其中n來自足夠範圍的整數s.t.多邊形是「覆蓋」的，參見scetch中的藍線。
從左邊開始檢測與多邊形的所有交點（即非水平邊）和形式（m，2n + 0.5）的所有內點，請參見紅色和綠色圓圈（完成後通過迭代邊緣中心的x座標）
現在，內點（m，2n + 0.5）的垂直網格鄰居（m，2n）和（m，2n + 1）是內點，如果它們不在邊界上，請參閱scetch中的綠色點。

AlgoScetch_innerPoints

下面是一些僞代碼（C++ /蟒啓發:-)）：

list<Point> polygon; // given polygon as list of neighbouring grid points 

// get centers of non-horizontal edges organized by line 
map<int, set<float> > edgeCentersX; // for each scan line the x-coords of edges in ascending order 

p_i = polygon[0] 
yMin, yMax = 999999, -999999 
for (i=1; i<polygon.size(); ++i) 
    p_i1 = polygon[i] // next point after p_i 
    if (p_i.x == p_i1.x) 
     continue // horizontal edges can be ignored 
    yMin_i = min(p_i.y, p_i1.y) 
    if (yMin_i % 2 == 1) 
     continue // we only need to look at each second mid-row 
    if (yMin_i < yMin) 
     yMin = yMin_i 
    if (yMin_i > yMax) 
     yMax = yMin_i 
    cx = 0.5*(p_i.x+p_i1.x) 
    edgeCentersX[yMin_i].insert(cx) // store edge center (yMin_i+0.5, cx) 
    p_i = p_i1 

list<Point> innerPoints 
for (y=yMin; y<= yMax; y+=2) 
    inside = false 
    cx_i = edgeCentersX[y][0] 
    for (i=1; i<edgeCentersX[y].size(); ++i) 
     cx_i1 = edgeCentersX[y][i] 
     inside = !inside 
     if (!inside) 
      continue 
     for (x=floor(cx_i)+1; x<cx_i1; ++x) 
      pLower = Point(y,x) 
      if (!polygon.contains(pLower)) 
       innerPoints.append(pLower) 
      pUpper = Point(y+1,x) 
      if (!polygon.contains(pUpper)) 
       innerPoints.append(pUpper)

來源

2013-02-04 14:57:34 coproc

謝謝！看起來很有趣，今晚會和格雷厄姆掃描算法一起測試（如Dukeling所建議的），看看哪些效果更好。你的解決方案看起來更容易，將看看它是否適用於所有情況。 – user2039330

Pick's theorem可能是你正在尋找的公式。它允許相當簡單地計算其角爲網格點（即具有整數座標）的多邊形的面積。

來源

2013-02-04 11:30:54 coproc

對不起，我可能錯誤地問了這個問題，我不需要計算面積數學，我需要得到裏面的點列表。 – user2039330

好吧，裏面的點數正好是Pick公式的輸入之一:-)所以你會留下相同的問題。 – coproc

通過每行從最左邊的點開始和計數紅色多邊形的個數n點到目前爲止在該行。

然後對於每個點p：p是內點當且僅當p不是紅色多邊形點且n是奇數時（例如參見下面的僞代碼）。

List<Point> innerPoints; 
for each row 
{ 
    int n = 0; // red polygon points counter 
    for each Point p in row 
    { 
     if(IsRedPolygonPoint(p)) n++; 

     bool isInnerPoint = !IsRedPolygonPoint(p) && n % 2 == 1; 
     if(isInnerPoint) 
     { 
      innerPoints.Add(p); 
     } 
    } 
}

你可以優化這個例如從每行最左邊的多邊形點開始。

來源

2017-03-09 13:42:53 YonedaLemma

查找由相鄰網格點構成的多邊形的所有內部網格點

回答

相關問題