用洪水法创建二维圆

Question

我试图生成这样的地形等高线：

​

我的最终目标是基于几个用户定义的点生成等高线(例如:这座山海拔100米，坡度为X)。

现在，我生成高度图的算法是一种径向洪水填埋场，其中每个点设置其当前高度，然后排起其8个邻居(包括对角线)的队列，将其高度设置为当前高度--斜坡的值。高度图是一个二维双倍数组，表示地图上每个x/y点的高度。sqrt_2是2的平方根值，它乘以对角邻域的斜率值来表示它们与当前点的真实距离。每个点也向外传播其斜率(高度向默认高度移动的速率)。EnqueueIfValidPoint只是向points_to_assign队列添加了一个点。我们的想法是从我们知道的某个点开始，慢慢地向默认高度倾斜/梯度(在这种情况下是0)。points_to_assign是一个常规的FIFO队列。

这段代码是用C#语言统一编写的，但是语言并没有改变它背后的逻辑。

​

// Continue the flood fill until we're out of points to assign
while (points_to_assign.Count > 0)
{

    PointToAssign p = points_to_assign.Dequeue();

    // Check if we have already assigned a height to this point
    if (heightmap[p.x_pos, p.y_pos] == unassigned_height)
    {
        assigned_points++;
        // Assign a height to this point
        heightmap[p.x_pos, p.y_pos] = p.height;


        // Height to assign neighbours to, moved towards default floor value
        double slope = p.slope;//GetRandomSlope(p.x_pos, p.y_pos, p.slope);

        double orthogonal_heights = 0;
        if (p.height >= 0)
            orthogonal_heights = Math.Max(0, p.height - (slope));
        else
            orthogonal_heights = Math.Min(0, p.height + (slope));
        // Enqueue neighbours of this point to assign a new height to
        // Below
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos, orthogonal_heights, p.slope);
        // Above
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos, orthogonal_heights, p.slope);
        // Left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos - 1, orthogonal_heights, p.slope);
        // Right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos + 1, orthogonal_heights, p.slope);

        double diagonal_heights = 0;
        if (p.height >= 0)
            diagonal_heights = Math.Max(0, p.height - (slope * sqrt_2));
        else
            diagonal_heights = Math.Min(0, p.height + (slope * sqrt_2));
        // Below and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Below and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos - 1, diagonal_heights, p.slope);
        // Above and left
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos + 1, diagonal_heights, p.slope);
        // Above and right
        EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos + 1, diagonal_heights, p.slope);
    }
}

​

然后，将高度值传递给指定颜色的颜色函数，例如:如果高度介于0和1之间，则将其赋值为白色，如果为1至2，则将其赋值为浅绿色，等等。

不幸的是，这段代码并不完全生成圆圈，而是生成一个八角形。我认为这个问题与编码对角线邻域值有关。

​

有没有人知道如何产生一个圆圈，而不是八角形，使用我的填水策略？

Answer 1

问题是，当你混合你的两种步长类型(对角线和正交)时，你得到了错误的距离。例如，正交步长+对角线步长导致sqrt(5) ~ 2.24的实际距离。但是你的算法给了你1 + sqrt(2) ~ 2.41。这就是为什么圆圈被切断的原因。

你需要做的是计算出离种子点的实际距离。只需将种子点与队列中的项一起存储(或者如果只有一个，则使用此一个)并从距离计算高度。沿袭的东西：

heightmap[p.x_pos, p.y_pos] = distance(p.seedPoint, p) * p.slope + p.seedPoint.height;

您还可以将种子点及其斜率存储在外部，只需在队列中引用它，以节省一些内存。

还可以通过积累x-差和y-差逐步计算欧氏距离，然后只计算sqrt(x-difference^2 + y-difference^2)。但这可能不值得付出这么大的努力。