填充两行之间的区域（不笔直）

Haradzieniec 发表于 Dev

哈拉季涅尼奇

在此处输入图片说明我在问有关允许用浅绿色填充黑色和深绿色区域之间的区域的算法。黑色区域是固定的。绿色是黑色区域之间的痕迹。黑色和深绿色的线只能是4个方向中的1个-北，西，南和东。

我对算法（不是算法）有一些想法，但认为它容易出错。

因此，我具有起点和终点的坐标（终点恰好是绿色触摸黑色时的坐标）。我有（xstart，ystart）和（xfinish，yfinish）坐标，以及连接该坐标的黑色和深绿色线条。我的目标是在两者之间的区域填充浅绿色。

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

找到算法后，我将尝试将其发布到此处（如果不是某人的算法）或提供链接。

谢谢你。

PS我的第一个想法是要注意（总是吗？）横穿任何水平或垂直线的线数是偶数。

拉瑟·卡尔森（Lasse V.Karlsen）

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

对于每一行，您将从左至右循环，从“外部”开始。每次击中一条垂直线越过您正在查看的当前线时，都将“外部/内部”位翻转。

然后为内部的所有正方形着色。

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

输出：

LINQPad输出