填充两条线之间的区域（不是直线）

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. 变化任意颜色颜色为白色