如何为网格上的圆形单元格区域生成外顶点轮廓路径

需求背景 #

需要为单元格组成的圆形区域生成轮廓，要求路径经过该圆形所有的外顶点，示意图如下：

其中黄色区域是圆形单元格范围，红色标注是存储的坐标点，蓝色标注是需要的路径点位置。

已实现的圆形区域单元格获取代码如下：

public List<Cell> GetSurroundingCellsCircle(int gridX, int gridZ, int distance)
{
    List<Cell> matches = new List<Cell>();
    int EX = distance + gridX;
    int EY = distance + gridZ;
    int SQ = distance * distance;

    for (int x = gridX - distance; x <= EX; x++)
    {
        for (int z = gridZ - distance; z <= EY; z++)
        {
            int c = x - gridX;
            int d = z - gridZ;

            if ((c * c + d * d) < SQ)
            {
                Cell cell = GetCell(x, z);
                if (cell != null)
                    matches.Add(cell);
            }
        }
    }

    return matches;
}

实现步骤 #

1. 筛选边界单元格 #

首先将所有圆形区域内的单元格坐标存入哈希集合，用于快速判定相邻单元格是否属于区域内。
判定规则：只要单元格的上下左右四个方向相邻单元格有任意一个不在圆形区域内，该单元格就是边界单元格。
示例代码：

// 先存储所有圆形单元格的坐标，方便快速查找
HashSet<(int x, int z)> cellSet = new HashSet<(int x, int z)>();
foreach (var cell in circleCells) // circleCells是GetSurroundingCellsCircle返回的结果
{
    cellSet.Add((cell.X, cell.Z));
}

// 四个相邻方向的偏移量
List<(int dx, int dz)> dirs = new List<(int, int)>() { (-1,0), (1,0), (0,-1), (0,1) };
List<Cell> borderCells = new List<Cell>();

foreach (var cell in circleCells)
{
    bool isBorder = false;
    foreach (var dir in dirs)
    {
        int nx = cell.X + dir.dx;
        int nz = cell.Z + dir.dz;
        if (!cellSet.Contains((nx, nz)))
        {
            isBorder = true;
            break;
        }
    }
    if (isBorder)
    {
        borderCells.Add(cell);
    }
}

2. 生成轮廓路径 #

假设每个单元格为边长为1的正方形，坐标为(x,z)的单元格四个顶点为：(x, z)、(x+1, z)、(x+1, z+1)、(x, z+1)。
首先收集所有边界单元格的顶点，然后筛选出仅属于1个圆形区域单元格的顶点（这类就是外顶点），最后以圆心为中心按极角排序即可得到连续的轮廓路径。
示例代码：

// 统计每个顶点被多少个圆形区域内的单元格共享
Dictionary<(float x, float z), int> vertexCount = new Dictionary<(float, float), int>();
// 单元格的四个顶点偏移
List<(float dx, float dz)> vertexOffsets = new List<(float, float)>() { (0,0), (1,0), (1,1), (0,1) };

foreach (var cell in circleCells)
{
    foreach (var offset in vertexOffsets)
    {
        float vx = cell.X + offset.dx;
        float vz = cell.Z + offset.dz;
        if (vertexCount.ContainsKey((vx, vz)))
        {
            vertexCount[(vx, vz)]++;
        }
        else
        {
            vertexCount[(vx, vz)] = 1;
        }
    }
}

// 筛选外顶点：仅被1个单元格共享的顶点就是外顶点
List<(float x, float z)> outerVertices = vertexCount.Where(kv => kv.Value == 1).Select(kv => kv.Key).ToList();

// 按极角排序，生成连续路径，centerX、centerZ就是圆形的中心gridX、gridZ
float centerX = gridX + 0.5f; // 单元格中心偏移，可根据实际坐标规则调整
float centerZ = gridZ + 0.5f;
outerVertices = outerVertices.OrderBy(p => Math.Atan2(p.z - centerZ, p.x - centerX)).ToList();

最终得到的outerVertices就是符合要求的轮廓路径点列表。

内容的提问来源于stack exchange，提问作者Majs