c# - 网格动态生成搜索过程中重复问题解决的算法

问题描述

假设 513 * 513 的二维数组大小是一个坐标值。

我想通过连接相同值的坐标来动态生成网格。

二维数组的值是随机生成的。

使用 bfs 算法，所有相同值的顶点都被输入。

并且要通过连接三个相邻点来制作网格，在相邻方向的八个点中搜索相同的值需要太长时间。

这似乎已经发生，包括冗余。

我希望您分享解决冗余的想法。

下面是完整的源代码，CreateTriangle() 函数会导致重复。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using System.Linq;

public class SegmentationMeshCreator : MonoBehaviour {
    // This first list contains every vertex of the mesh that we are going to render
    public List<Vector3> newVertices = new List<Vector3>();

    // The triangles tell Unity how to build each section of the mesh joining
    // the vertices
    public List<int> newTriangles = new List<int>();

    // The UV list is unimportant right now but it tells Unity how the texture is
    // aligned on each polygon
    public List<Vector2> newUV = new List<Vector2>();


    // A mesh is made up of the vertices, triangles and UVs we are going to define,
    // after we make them up we'll save them as this mesh

    // Start is called before the first frame update
    private Mesh mesh;

    public Queue<Node> SegNode = new Queue<Node>();


    private bool[,] visit = new bool[513, 513];


    private int[] dx = new int[4] { 0, 1, -1, 0 };
    private int[] dy = new int[4] { 1, 0, 0, -1 };

    // 8 - direction
    private int[,] fx = new int[8, 2] { { -1, 0 }, { -1, 0 }, { 1, 0 }, { 1, 1 }, 
                                        { -1, 0 }, { -1, 0 }, { 0, 1 }, { 0, 1 } };
    private int[,] fy = new int[8, 2] { { -1, -1 }, { 0, -1 }, { -1, -1 }, { -1, 0 },
                                        { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, 1 } };

    public struct Node
    {
        public int x, y, color;

        public Node(int x, int y, int color)
        {
            this.x = x;
            this.y = y;
            this.color = color;
        }
    }

    void bfs(int r, int c, int color, int[][] pixel)
    {
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(new Node(r, c, color));

        while (q.Count > 0)
        {
            Node curNode = q.Dequeue();
            SegNode.Enqueue(curNode);
            for (int i = 0; i < 4; i++)
            {
                int tr = curNode.x + dx[i];
                int tc = curNode.y + dy[i];

                if (tr >= 0 && tr < 513 && tc >= 0 && tc < 513)
                {
                    if (!visit[tr, tc] && pixel[tr][tc] == color)
                    {
                        visit[tr, tc] = true;
                        q.Enqueue(new Node(tr, tc, color));

                        newVertices.Add(new Vector3(tr, tc, 5));
                    }
                }
            }
        }
    }

    void CreateTriangle()    
    {
        int index = 0;
        while (SegNode.Count > 0)
        {

            Node curNode = SegNode.Peek();
            for (int i = 0; i < 8; i++)
            {
                var a = SegNode.Any(o => o.x == curNode.x + fx[i, 0] && o.y == curNode.y + fy[i, 0] && o.color == curNode.color);
                var b = SegNode.Any(o => o.x == curNode.x + fx[i, 1] && o.y == curNode.y + fy[i, 1] && o.color == curNode.color);

                if(a && b)
                {
                    Node nextNode = new Node(curNode.x + fx[i, 0], curNode.y + fy[i, 0], curNode.color);
                    Node nextNode2 = new Node(curNode.x + fx[i, 1], curNode.y + fy[i, 1], curNode.color);

                    newTriangles.Add(SegNode.ToArray().ToList().IndexOf(curNode) + index);
                    newTriangles.Add(SegNode.ToArray().ToList().IndexOf(nextNode) + index);
                    newTriangles.Add(SegNode.ToArray().ToList().IndexOf(nextNode2) + index);
                }
            }
            index++;
            SegNode.Dequeue();
        }
    }

    public void createMesh(int[][] pixel)
    {
        for (int r = 0; r < 513; r++)
        {
            for (int c = 0; c < 513; c++)
            {
                if (!visit[r, c] && pixel[r][c] != 0)
                {
                    newVertices.Add(new Vector3(r, c, 5));
                    bfs(r, c, pixel[r][c], pixel);

                }
            }
        }
        CreateTriangle();


        _ShowAndroidToastMessage("Create a Mesh");

        mesh = GetComponent<MeshFilter>().mesh;

        mesh.Clear();
        mesh.vertices = newVertices.ToArray();
        mesh.triangles = newTriangles.ToArray();
        mesh.uv = newUV.ToArray(); // add this line to the code here
        //mesh.Optimize();
        mesh.RecalculateNormals();
    }

    // Use this for initialization
    void Start () {
           createMesh(pixel);           // int pixel[][]
    }
}

当红点为参考点时，如上图所示，存在重复的问题，即在8路搜索过程中对相同的点多做三个网格。

如果您对我的项目感到好奇，可以参考我之前的问题。

如何在统一中动态创建网格

要在 C# 中使用 Queue.contains() 查找具有相同值的对象，Unity

标签： c#unity3dbreadth-first-search

因为在createMesh()您首先逐行和逐列迭代点，所以我假设您已经为上面的点和左边的x点创建了所有可能的三角形。xx

然后你只需要检查是否x创建了一个三角形，其下方x和右侧的点x。

c# - 网格动态生成搜索过程中重复问题解决的算法

问题描述

解决方案

推荐阅读