Generating a 2D circle using floodfill

Howdy. I've got a bit of an usual use-case that I could use some help with. Right now, I'm trying to generate topographical contour lines looking something like this:


My eventual goal is to generate contour lines based on a few user-defined points (ex: this hill is at 100m elevation, and has a slope of X).

For now, my algorithm for generating a heightmap is a kind of radial flood fill, where each point enqueues its 8 neighbours (including diagonals). heightmap is a 2D array of doubles representing the height at each x/y point on the map. sqrt_2 is the value of square root of 2, which is a distance we get from the Pythagoras theorem for a diagonal. Each point also propagates outwards its slope (the rate at which the height moves towards the default height. EnqueueIfValidPoint simply adds a point to the points_to_assign queue. The idea is to start at certain points that we KNOW the height of, and slowly slope/gradient towards a default height (0 in this case).

Code (CSharp):

1.             // Continue the flood fill until we're out of points to assign
2.             while (points_to_assign.Count > 0)
3.             {
4.  
5.                 PointToAssign p = points_to_assign.Dequeue();
6.  
7.                 // Check if we have already assigned a height to this point
8.                 if (heightmap[p.x_pos, p.y_pos] == unassigned_height)
9.                 {
10.                     assigned_points++;
11.                     // Assign a height to this point
12.                     heightmap[p.x_pos, p.y_pos] = p.height;
13.  
14.  
15.                     // Height to assign neighbours to, moved towards default floor value
16.                     double slope = p.slope;//GetRandomSlope(p.x_pos, p.y_pos, p.slope);
17.  
18.  
19.                     //float orthogonal_heights = Mathf.MoveTowards(p.height, default_height, slope);
20.                     double orthogonal_heights = 0;
21.                     if (p.height >= 0)
22.                         orthogonal_heights = Math.Max(0, p.height - (slope));
23.                     else
24.                         orthogonal_heights = Math.Min(0, p.height + (slope));
25.                     // Enqueue neighbours of this point to assign a new height to
26.                     // Below
27.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos, orthogonal_heights, p.slope);
28.                     // Above
29.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos, orthogonal_heights, p.slope);
30.                     // Left
31.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos - 1, orthogonal_heights, p.slope);
32.                     // Right
33.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos, p.y_pos + 1, orthogonal_heights, p.slope);
34.  
35.  
36.  
37.                     //float diagonal_heights = Mathf.MoveTowards(p.height, default_height, slope * sqrt_2);
38.                     double diagonal_heights = 0;
39.                     if (p.height >= 0)
40.                         diagonal_heights = Math.Max(0, p.height - (slope * sqrt_2));
41.                     else
42.                         diagonal_heights = Math.Min(0, p.height + (slope * sqrt_2));
43.                     // Below and left
44.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos - 1, diagonal_heights, p.slope);
45.                     // Below and right
46.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos - 1, diagonal_heights, p.slope);
47.                     // Above and left
48.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos - 1, p.y_pos + 1, diagonal_heights, p.slope);
49.                     // Above and right
50.                     EnqueueIfValidPoint(points_to_assign, heightmap, p.x_pos + 1, p.y_pos + 1, diagonal_heights, p.slope);
51.                 }
52.             }

Height values are then passed to a colour function that assigns a colour, ex: if the height is between 0 and 1, assign it white, if it's between 1 and 2, assign it light green, etc. I imagine the problem has to do with encoding the diagonal neighbour values

Unfortunately this code doesn't quite produce circle, and instead produces a octagon.

Does anyone have any idea how to produce a circle, instead of an octagon using my flood fill strategy?

 

If you are ONLY trying to create circles, just iterated over a square grid, every column, every row, every pixel, and at each pixel calculate the distance from the pixel to the center. Then use that number to adjust the color.

 

@imaginaryhuman has the right of it. And if you want ovals, it's a simple adjustment to calculate the distance from the two focii instead of a single center.

 

Yes, circles are the goal (for now). I implemented your suggestion and calculated the distance from that point to the center, and that worked wonderfully. Thanks.

 

I hadn't heard of that technique for ellipses... how do you combine the two distances?

 

You just add up the distances from the two focal points. The interior of the ellipse is wherever that sum is less than some amount.

​

Reference.