填充两条线之间的区域(不直线)

Question

​

我要问的是，算法允许用浅绿色填充介于黑色和深绿色之间的区域。黑区是固定的。绿色是黑色区域之间的痕迹。黑色和深绿色线可能仅为北、西、南和东四个方向中的一个。

我对这个算法有一些想法(还不是算法)，但我认为它容易出错。

所以，我有开始和结束的坐标(finish正好是绿色接触黑色的时候)。我有(xstart，ystart)和(xfinish，yfinish)坐标，以及连接这个坐标的黑色和深绿色线。我的目标是用浅绿色填充中间的区域。

如果我找到了我的解决方案，而且它很短，我也会在这里张贴。任何关于这个算法的想法都会受到高度赞赏。顺便说一下，are由一个小的长方形1x1组成。因此，可以用一条高度(或宽度)或1的线来着色这个区域。

一旦我找到算法，我将尝试张贴在这里(如果这不是某人的算法)或提供一个链接。

谢谢。

我的第一个想法是把注意力放在(总是？)横过任何水平线或垂直线的偶数线。

Answer 1

你会把“图像”从上到下循环。

对于每一行，您将从左到右循环，从“外部”开始。每次你碰到一条垂直线越过你正在看的当前线，你就翻转“外部/内部”位。

然后你把里面所有的方块都涂上颜色。

下面是一个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多年前解决的。你可以在任何标准教科书或网络上找到它。这里有一个指向起点的链接：填充。

基本上，你走的线填补像素或栅格线在一边，如果他们还没有被填补。每次过马路后，你就转到另一边去。让它起作用很容易。弄得快一点很难。

如果你正在使用任何有能力的图形库，从Windows到OpenGL到GPU着色器代码，它已经内置了。

这里有一些代码作为思想的来源：http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

Answer 3

为了完成位图图形的“完美”跟踪，我解决了一些密切相关的问题。所谓“完美”，我的意思是，跟踪完全遵循位图的边界(而不是通常更优越的方法推断出有角的线和曲线)。一旦你有一个矢量边界，转换回像素只是多边形渲染-实际上是一个简单的情况，因为所有的边缘是水平的或垂直的，并在像素之间的边界。

我计划使用相关的想法，从其他矢量图形生成矢量图形(例如，生成一个填充，精确填充非零宽度多边形边缘的内部)，但还没有这样做，所以还没有更新注释。通过将线条作为矢量形状而不是已经呈现的像素处理，您可能也会从这种方法中获益。

我有一个冗长的文件与一些漂亮的照片在我的4共享帐户这里。我会尽量把它留在那里的。

快速总结-核心是定义一组像素长的像素之间的边界，这样，随着边缘的遵循，它将从仍然需要遵循的集合中删除。然后选择一个起点，顺时针地沿着边界走，直到你回到起点，然后重复，直到你用完了要遵循的边界。

对我来说，一个技术性的问题是，我需要处理多色图像，这意味着每个像素边界在每个方向上被跟踪两次(因为每个方向都有一个填充区域)。我怀疑你是否需要这样做--你的黑色和绿色线条只是为了这个目的而设的界限，所以你可以假装它们是相同的颜色。

另一个技术问题是与交叉线，洞和缠绕规则有关，看起来你确实很关心这个问题。