填充兩條線之間的區域（不是直線）

Question

我在問關於允許用淺綠色填充黑色和深綠色區域之間的區域的算法。黑色區域是固定的。綠色是黑色區域之間的痕跡。 黑色和深綠色的線條可能只有4個方向中的1個 - 北，西，南和東。

我對算法有一些想法（而不是算法），但認爲它很容易出錯。

所以，我有開始和結束的座標（完成時正好是綠色接觸黑色時）。我有（xstart，ystart）和（xfinish，yfinish）座標以及連接該座標的黑色和深綠色線條。我的目標是填充淺綠色的區域。

如果我找到我的解決方案，它很短，我也會在這裏發佈。 此算法的任何想法是高度讚賞。 順便說一句，這些都是由一個小矩形1x1組成。所以可以用高度（或寬度）或1的線來着色該區域。

一旦我找到算法，我會嘗試在這裏發佈它（如果這不是某人的算法）或給出鏈接。

謝謝。

P.S.我的第一個想法是注意橫貫任何水平或垂直線的偶數行（總是？）。

Answer 1

你會循環從上到下的「形象」。

對於每一行，您都會從左向右循環，從「outside」開始。每次當你穿過你正在看的當前線的垂直線時，你就會翻轉「外側/內側」位。

然後你着色裏面的所有廣場。

這裏有一個LINQPad程序演示：

const int scale = 20; 

void Main() 
{ 
    var polyline = new[] 
    { 
     new Point(4, 0), 
     new Point(4, 5), 
     new Point(10, 5), 
     new Point(10, 10), 
     new Point(6, 10), 
     new Point(6, 3), 
     new Point(15, 3), 
     new Point(15, 8), 
     new Point(14, 8), 
     new Point(14, 7), 
     new Point(16, 7), 
     new Point(16, 0), 
    }; 

    int maxY = polyline.Max(point => point.Y); 
    int maxX = polyline.Max(point => point.X); 

    var bitmap = new Bitmap((maxX + 1) * scale, (maxY + 1) * scale); 
    var previousPoint = polyline[0]; 

    using (var g = Graphics.FromImage(bitmap)) 
    { 
     // TODO: y=0 should be y = minY - 1 
     for (int y = 0; y < maxY + 1; y++) 
     { 
      bool isInside = false; 
      var xCoordinatesOfCrossingLines = new HashSet<int>(
       from index in Enumerable.Range(0, polyline.Length) 
       let p1 = polyline[index] 
       let p2 = polyline[(index + 1) % polyline.Length] 
       where p1.X == p2.X 
       where (p1.Y <= y && p2.Y > y)  // must cross the y-slice in downwards 
         || (p2.Y <= y && p1.Y > y) // or upwards direction 
       let x = p1.X 
       group x by x into xGroup   // if we somehow have 2 (or an even number of) lines overlapping, don't count them 
       where xGroup.Count() % 2 != 0  // so we will only except distinct x values that occur 1, 3, 5, etc. times 
       select xGroup.Key); 

      // TODO: x=0 should be x = minX - 1 
      for (int x = 0; x < maxX + 1; x++) 
      { 
       // Every time we hit a vertical line, we flip the "is inside" bit 
       if (xCoordinatesOfCrossingLines.Contains(x)) 
        isInside = !isInside; 

       // Colorize all the squares inside 
       if (isInside) 
        g.FillRectangle(Brushes.Green, new Rectangle(
         ScalePoint(new Point(x, y), scale), 
         new Size(scale, scale))); 
      } 
     } 
     for (int index = 1; index <= polyline.Length; index++) 
     { 
      g.DrawLine(Pens.Black, ScalePoint(previousPoint, scale), ScalePoint(polyline[index % polyline.Length], scale)); 
      previousPoint = polyline[index % polyline.Length]; 
     } 
    } 
    bitmap.Dump(); 
} 

public Point ScalePoint(Point p, int scale) 
{ 
    return new Point(p.X * scale, p.Y * scale); 
} 

輸出：

Answer 2

這是一個標準的洪水填充或光柵填充算法。我猜想它是在30多年前解決的。您可以在任何標準教科書或網絡上找到它。這是一個起點的鏈接：https://en.wikipedia.org/wiki/Flood_fill。

基本上你會走一行填充像素或光柵線在一邊，如果他們沒有填寫已經。在每次穿越之後，您切換到另一側。讓它工作很容易。快速獲取是困難的。

如果你使用任何類型的主管圖形庫從Windows GDI通過的OpenGL到它已經內置了GPU的着色器代碼

一些代碼在這裏是創意來源：http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

Answer 3

我解決了，爲了做到 「完美」 的位圖圖形的追蹤一些密切相關的問題。所謂「完美」，我的意思是跟蹤完美地遵循位圖邊界（而不是推斷成角度的直線和曲線的最佳方法）。一旦你有一個向量邊界，轉換回像素只是多邊形渲染 - 實際上是一個簡單的例子，因爲所有的邊緣是水平或垂直的，並在像素之間的邊界。

我計劃使用相關思想從其他矢量圖形生成矢量圖形（例如，生成一個精確填充非零寬度多邊形邊的內部填充），但還沒有完成，所以沒有更新了筆記。您也可以從這種方法中受益，即將線條作爲矢量形狀使用，而不是像已經渲染的像素那樣處理。

我在我的4shared賬戶here上有一張長長的文檔，上面有一些漂亮的圖片。我會盡量保持在那裏。

快速總結 - 核心是定義一組像素長的像素間邊界，因此，隨着邊緣的跟隨，它會從仍然需要遵循的集合中移除。然後選擇一個起始點，順時針旋轉邊界，直到你循環回到起始點，然後重複，直到你走出界限爲止。

對我來說，一個技術問題是我需要處理多色圖像，這意味着每個像素邊界都會沿着兩個方向 - 每個方向一次（因爲每邊都有一個填充區域）。我懷疑你是否需要這樣 - 你的黑色和綠色的線條就是這個目的的邊界，所以你可以假裝它們是相同的顏色。

另一個技術性涉及線，交叉，孔和纏繞規則，並且看起來你做關心這一點。

Answer 4

這裏是一個辦法做到這一點： -

1. 從任何空缺點
2. floodfill做，如果洪水期間填寫，如果遇到圖像的邊界，然後填充所有點在此時，floodFill與任意顏色。
3. 否則如果floodfill由黑色或綠色線，然後用淺綠
4. 變化任意顏色顏色爲白色