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

Question

我问的是允许用浅绿色填充黑色和深绿色区域之间的区域的算法。黑色区域是固定的。绿色是黑色区域之间的痕迹。黑色和深绿色线只能是 4 个方向之一 - 北、西、南和东。

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

所以，我有起点和终点的坐标(终点恰好是绿色接触黑色的时间)。我有 (xstart, ystart) 和 (xfinish, yfinish) 坐标以及连接该坐标的黑色和深绿色线。我的目标是用浅绿色填充中间区域。

如果我找到我的解决方案并且它很短，我也会在这里发布。高度赞赏此算法的任何想法。顺便说一句，它们由一个 1x1 的小矩形组成。所以用高度(或宽度)或 1 的线为区域着色是可以的。

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

谢谢。

附言我的第一个想法是注意有(总是？)偶数条线穿过任何水平线或垂直线。

Answer 1

您将从上到下循环“图像”。

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

然后你给里面所有的方 block 上色。

这是一个 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);
}

输出: