Marching square 算法中的模棱两可的情况

Question

如果我们将 Wikipedia article on Marching square 考虑在内，我们会发现案例 #5 和案例 #10 被认为是不明确的案例。

我已经按如下方式实现了 Marching Square，但我不明白为什么会出现模棱两可的情况：

public class LinesRectangle
{
    public Graphics Graphics { get; set; }
    public Color Color { get; set; }
    public Pen Pen { get; set; }
    public int Thickness { get; set; }

    public LinesRectangle()
    {
        Color = Color.Blue;
        Thickness = 2;
        Pen = new Pen(Color, Thickness);
    }

    public void DrawLines(int x, int y, int width, int code)
    {
        int height = width;

        Graphics.DrawRectangle(Pen, new System.Drawing.Rectangle(x, y, width, height));

        int x1 = 0, y1 = 0;
        int x2 = 0, y2 = 0;

        switch (code)
        {
            case 0:
            case 15:
                break;
            case 1:
            case 14:
                x1 = x; y1 = y + height/2;
                x2 = x + width/2; y2 = y + height;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 2:
            case 13:
                x1 = x + width/2; y1 = y + height;
                x2 = x + width; y2 = y + height/2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 3:
            case 12:
                x1 = x; y1 = y + height / 2;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 4:
            case 11:
                x1 = x+width/2; y1 = y;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 5:
                x1 = x ; y1 = y + height/2;
                x2 = x + width/2; y2 = y;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                x1 = x + width / 2; y1 = y + height;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 6:
            case 9:
                x1 = x + width / 2; y1 = y;
                x2 = x + width/2; y2 = y + height;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 7:
            case 8:
                x1 = x; y1 = y + height / 2;
                x2 = x + width / 2; y2 = y;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 10:
                x1 = x + width / 2; y1 = y;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                x1 = x; y1 = y + height / 2;
                x2 = x + width / 2; y2 = y + height;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
        }
    }
}

您可以在这里看到每个案例都是单独处理的。

输出：

谁能告诉我我错过了什么？

驱动程序：

public enum What
{
    lines, surface, both
}

public partial class DrawingForm : System.Windows.Forms.Form
{
    public int [,] Data { get; set; }

    public void Print(int[,] data, int xn, int yn)
    {
        for (int j = 0; j < yn; j++)
        {
            for (int i = 0; i < xn; i++)
            {
                Console.Write(data[i, j] + ", ");
            }
            Console.WriteLine();
        }
    }
    public int[,] normalize(int[,] data, int xn, int yn)
    {

        for (int j = 0; j < yn; j++)
        {
            for (int i = 0; i < xn; i++)
            {
                if (data[i, j] > 1)
                {
                    data[i, j] = 0;
                }
                else
                {
                    data[i, j] = 1;
                }
            }
        }

        return data;
    }

    public int[,] marching_square(int x, int y, int[,] data, int isovalue, What what)
    {
        int xn = x;
        int yn = y;

        data = normalize(data, xn, yn);

        int[,] bitMask = new int[xn - 1, yn - 1];

        for (int j = 0; j < yn - 1; j++)
        {
            for (int i = 0; i < xn - 1; i++)
            {
                StringBuilder sb = new StringBuilder();
                sb.Append(data[i, j]);
                sb.Append(data[i + 1, j]);
                sb.Append(data[i + 1, j + 1]);
                sb.Append(data[i, j + 1]);

                bitMask[i, j] = Convert.ToInt32(sb.ToString(), 2);
            }
        }

        return bitMask;
    }

    public DrawingForm()
    {
        InitializeComponent();
    }

    private void MainForm_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
    {
        int[,] data = new int[,] {
                                  { 1,1,1,1,1 },
                                  { 1,2,3,2,1 },
                                  { 1,3,1,3,1 },
                                  { 1,2,3,2,1 },
                                  { 1,1,1,1,1 }
                                  };

        int[,] bitMask = marching_square(5, 5, data, 0, What.lines);

        Graphics g = this.CreateGraphics();

        LinesRectangle rect = new LinesRectangle();
        rect.Graphics = g;
        
        for (int j = 0; j < 4; j++)
        {
            for (int i = 0; i < 4; i++)
            {
                rect.DrawLines(i*50, j*50, 50, bitMask[i,j]);
            }
        } 
    }
}

编辑：如果是以下数据（如@JeremyLakeman所指出）：

{ 2,1,2,1,2 },
{ 1,2,1,2,1 },
{ 2,1,2,1,2 },
{ 1,2,1,2,1 },
{ 2,1,2,1,2 }

我的程序产生了以下输出：

Answer 1

您的示例不包含任何模棱两可的情况。您希望使用以下输入得到什么输出；

{ 2,1,2,1,2 },
{ 1,2,1,2,1 },
{ 2,1,2,1,2 },
{ 1,2,1,2,1 },
{ 2,1,2,1,2 }

1 周围的圆圈？围绕2的圆圈？对角线？

编辑;

来自您的代码；

            case 5:
                x1 = x ; y1 = y + height/2;
                x2 = x + width/2; y2 = y;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                x1 = x + width / 2; y1 = y + height;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;
            case 10:
                x1 = x + width / 2; y1 = y;
                x2 = x + width; y2 = y + height / 2;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                x1 = x; y1 = y + height / 2;
                x2 = x + width / 2; y2 = y + height;
                Graphics.DrawLine(Pen, x1, y1, x2, y2);
                break;

您可以交换这些案例标签。您可以选择一个，删除另一个，然后合并案例。您可以查看更多周围的像素来选择一个。您可以掷出一个随机数来选择绘制方式。

但你没有。你武断地决定你总是这样画那些案例。

Answer 2

哦伙计，我理解你。令人惊讶的是，这是个好问题！

当您决定“值高于等值”是黑色还是白色以及“值低于等值。

让我解释一下我的意思。如果您手动执行算法，您可以获得以下结果。在遵循 wiki 上描述的算法时，您所做的唯一选择是决定在绘制节点时使用什么颜色。

{ 1, 1, 1 },
{ 1, 2, 1 },
{ 1, 1, 1 }

没有模棱两可的情况所以选择无关紧要 - 结果图像将是无论'1'是“黑点”还是“白点”都一样。

但是让我们看一下例子有模棱两可的情况:

{ 1, 2, 1 },
{ 2, 1, 2 },
{ 1, 2, 1 }

如果“1”为白色，算法将在中点周围提供一个圆圈，如果“1”被选择为黑色，则相同的算法将在中点附近提供 4 个圆弧。

我认为选择时刻在 normalize 函数中

 if (data[i, j] > 1)

如果您将“>”更改为“<”，您将在不明确的情况下更改图像。对于非模棱两可的情况，它不会改变任何东西。如果您查看方法思想而不是算法，则歧义更容易理解。查看 saddle point - 绘制轮廓时存在歧义，因为一方面鞍点是最小值，另一方面是最大值 - 取决于测量方向。

希望这有助于消除困惑。

编辑： 我在评论中进行了详细说明，但为了可见性，我在此处复制它

Marching square 算法中的模棱两可的情况

Ambiguous cases in Marching square algorithm

c#

algorithm

contour

marching-cubes