How can I draw a Hilbert Curve Fractal recursively using C# GDI+ Graphics and Windows Forms?
I am working on a project in which I need to use recursion to draw a Hilbert Curve fractal in a Windows Forms application in C#. I must use GDI+ graphics for this, but I am new to GDI+ graphics. Below is my entire code for the Form class that actually draws the curve. At the end of this post, I have included photos demonstrating my erroneous output and the expected output.
The DrawRelative() function is supposed to draw the next line segment from the current [x,y] coordinates to the new [x,y] coordinates, which are calculated by adding the xDistance and yDistance values passed into the DrawRelative() function to the xCurrent and yCurrent class properties.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace HilbertCurveFractal
{
public partial class FractalDisplay : Form
{
public int MaxDepth { get; set; }
public int CurveType { get; set; }
public int xCurrent { get; set; }
public int yCurrent { get; set; }
public int xLength { get; set; }
public int yLength { get; set; }
public FractalDisplay(int DepthValue, int SelectedCurve)
{
InitializeComponent();
MaxDepth = DepthValue;
CurveType = SelectedCurve;
xCurrent = 250;
yCurrent = 250;
xLength = 0;
yLength = 2;
}
private void FractalDisplay_Load(object sender, EventArgs e)
{
this.DoubleBuffered = true;
if (CurveType == 1) // Run the Hilbert Curve Generator
{
GenerateHilbertCurve(MaxDepth, xLength, yLength);
}
else if (CurveType == 2) // Run the Koch Curve Generator
{
}
else if (CurveType == 3) // Run the Sierpinski Curve Generator
{
}
else
{
MessageBox.Show("Error! - No Curve Type Selected. Ending Program.");
Application.Exit();
}
}
private void GenerateHilbertCurve(int depth, int xDistance, int yDistance)
{
//if (depth == 0) // Base Case
//{
// return;
//}
//else { }
if (depth > 0)
{
GenerateHilbertCurve(depth - 1, yDistance, xDistance);
}
else { }
// Draw Part of Curve Here
DrawRelative(xDistance, yDistance);
if (depth > 0)
{
GenerateHilbertCurve(depth - 1, xDistance, yDistance);
}
else { }
// Draw Part of Curve Here
DrawRelative(yDistance, xDistance);
if (depth > 0)
{
GenerateHilbertCurve(depth - 1, xDistance, yDistance);
}
else { }
// Draw Part of Curve Here
DrawRelative((- 1 * xDistance), (-1 * yDistance));
if (depth > 0)
{
GenerateHilbertCurve(depth - 1, (-1 * yDistance), (-1 * xDistance));
}
else { }
}
// Create a New Paint Event Handler
private void DrawRelative(int xDistance, int yDistance)
{
xLength = xDistance;
yLength = yDistance;
this.Paint += new PaintEventHandler(HilbertCurve_Paint);
}
// Perform the Actual Drawing
private void HilbertCurve_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
{
// Discover where the new X and Y points will be
int xNew, yNew;
xNew = xCurrent + xLength;
yNew = yCurrent + yLength;
// Paint from the current position of X and Y to the new positions of X and Y
e.Graphics.DrawLine(Pens.Red, xCurrent, yCurrent, xNew, yNew);
// Update the Current Location of X and Y
xCurrent = xNew;
yCurrent = yNew;
}
}
}
The first photo (below) is the incorrect output from the Hilbert Curve function given a MaxDepth of 1.
The second photo (below) represents what I should be getting from this set of functions (given a MaxDepth value of 1 passed in).
Because it seems like the algorithm for recursion is coded correctly, I suspect that I am not using the GDI+ graphics in the proper way, or my class properties are being updated/set incorrectly somewhere in the recursive calls. What can I do to fix my drawing algorithm? Thank you in advance.
To be honest, I didn't initially understand the implementation you have for generating the points for the Hilbert curve. I'm familiar with a couple of different approaches, neither of which look like that.
But, that's an entirely different question. Your main issue at hand is really just that you don't understand how the drawing mechanism in Winforms works. Briefly: there's a Paint event, which your code should handle by drawing what needs to be drawn. Subscribing to the Paint event doesn't cause anything to happen; it's just a way of registering to be notified when drawing is supposed to occur.
Typically, one would use the Designer to subscribe to the event, by navigating to the "Events" tab of the Properties pane for an object in the Designer (e.g. your Form) and selecting the appropriate event handler (or double-clicking in the empty box next to the event to have the Designer automatically insert an empty handler for you to fill in). You can also, when handling the Paint event in your own object, simply override the OnPaint() method.
In either case, the correct technique is to establish the prerequisites for drawing, then call Invalidate() which causes the framework to then raise the Paint event, at which time you can actually draw what you want to draw.
Note that between commenter TaW and me, we have suggested two different approaches to drawing: I suggested pre-computing all of the necessary data for drawing, and then just draw that when the Paint event is raised; TaW has suggested calling the recursive method from the Paint event handler, and drawing directly as you traverse the recursive algorithm.
Both techniques are fine, but of course there are pros and cons to either, having mostly to do with the classic trade-off of time and space. With the former technique, the cost to generate the curve is incurred only once, when the parameters for the curve change. Drawing occurs more quickly, because all the code has to do is draw the pre-existing data. With the latter technique, there is no need to store the data, as each new point generated is used immediately, but of course this means all of the points have to be regenerated every time the window is redrawn.
For this particular application, in practice I don't think it matters much. At typical screen resolutions, you won't be able to make out the features of the curve long before you start to hit the limits of data storage for the points to draw. Similarly, the execution of the algorithm is so fast that there's really no harm in recalculating the points each time the window needs to be redrawn. Just keep in mind that these are trade-offs you may have to judge more closely in other scenarios.
Okay, so what's all that mean? Well, when I converted it to something that used the Graphics class correctly, I couldn't get your implementation to draw a Hilbert curve, so I changed that part of the code to use an implementation I know works. You can find a detailed discussion on how this particular implementation works here: Hilbert Curve
Concepts & Implementation
Below, I have provided two different versions of that particular Hilbert curve implementation, the first using the "retained" approach (i.e. generate the data, then draw it), and the second using the "immediate" approach (i.e. generate the data every time you want to draw the window, as the drawing is occurring):
"Retained" method:
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
DoubleBuffered = true;
}
private PointF[] _points;
private void FractalDisplay_Load(object sender, EventArgs e)
{
Redraw();
}
private void Redraw()
{
List<PointF> points = new List<PointF>();
GenerateHilbert(0, 0, 1, 0, 0, 1, (int)numericUpDown1.Value, points);
_points = points.ToArray();
Invalidate();
}
private void GenerateHilbert(PointF origin, float xi, float xj, float yi, float yj, int depth, List<PointF> points)
{
if (depth <= 0)
{
PointF current = origin + new SizeF((xi + yi) / 2, (xj + yj) / 2);
points.Add(current);
}
else
{
GenerateHilbert(origin, yi / 2, yj / 2, xi / 2, xj / 2, depth - 1, points);
GenerateHilbert(origin + new SizeF(xi / 2, xj / 2), xi / 2, xj / 2, yi / 2, yj / 2, depth - 1, points);
GenerateHilbert(origin + new SizeF(xi / 2 + yi / 2, xj / 2 + yj / 2), xi / 2, xj / 2, yi / 2, yj / 2, depth - 1, points);
GenerateHilbert(origin + new SizeF(xi / 2 + yi, xj / 2 + yj), -yi / 2, -yj / 2, -xi / 2, -xj / 2, depth - 1, points);
}
}
// Perform the Actual Drawing
private void HilbertCurve_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
{
if (_points != null)
{
float scale = Math.Min(ClientSize.Width, ClientSize.Height);
e.Graphics.ScaleTransform(scale, scale);
using (Pen pen = new Pen(Color.Red, 1 / scale))
{
e.Graphics.DrawLines(pen, _points);
}
}
}
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
Redraw();
}
protected override void OnClientSizeChanged(EventArgs e)
{
base.OnClientSizeChanged(e);
Invalidate();
}
}
"Immediate" method:
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
DoubleBuffered = true;
}
private void Redraw()
{
Invalidate();
}
private PointF GenerateHilbert(PointF origin, float xi, float xj, float yi, float yj, int depth,
PointF? previous, Graphics graphics, Pen pen)
{
if (depth <= 0)
{
PointF current = origin + new SizeF((xi + yi) / 2, (xj + yj) / 2);
if (previous != null)
{
graphics.DrawLine(pen, previous.Value, current);
}
return current;
}
else
{
previous = GenerateHilbert(origin, yi / 2, yj / 2, xi / 2, xj / 2, depth - 1, previous, graphics, pen);
previous = GenerateHilbert(origin + new SizeF(xi / 2, xj / 2), xi / 2, xj / 2, yi / 2, yj / 2, depth - 1, previous, graphics, pen);
previous = GenerateHilbert(origin + new SizeF(xi / 2 + yi / 2, xj / 2 + yj / 2), xi / 2, xj / 2, yi / 2, yj / 2, depth - 1, previous, graphics, pen);
return GenerateHilbert(origin + new SizeF(xi / 2 + yi, xj / 2 + yj), -yi / 2, -yj / 2, -xi / 2, -xj / 2, depth - 1, previous, graphics, pen);
}
}
// Perform the Actual Drawing
private void HilbertCurve_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
{
float scale = Math.Min(ClientSize.Width, ClientSize.Height);
e.Graphics.ScaleTransform(scale, scale);
using (Pen pen = new Pen(Color.Red, 1 / scale))
{
GenerateHilbert(new PointF(), 1, 0, 0, 1, (int)numericUpDown1.Value, null, e.Graphics, pen);
}
}
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
Redraw();
}
protected override void OnClientSizeChanged(EventArgs e)
{
base.OnClientSizeChanged(e);
Invalidate();
}
}
In both examples I've made some other changes which are not strictly needed for the purpose of illustrating the techniques, but which are still useful:
- The curve itself is computed in unit space (i.e. a square of side length of 1), and then drawn by scaling the drawing to fit the window.
- Where it makes sense, individual coordinates are passed as whole
PointFvalues instead. This simplifies reuse of the values and adding new offsets to the X and Y values. - Since the drawing is now scaled to the window, the window is redrawn if its size changes.
- For simplicity, this
Formis self-contained, with aNumericUpDownControlthat determines the recursion depth. I didn't include instantiation of this control; I presume you can add the appropriate control yourself in the Designer, to make the above compile.
Addendum:
I've had a chance to look over the other examples on the Internet of the algorithm that you tried to implement. Now that I understand what the basic mechanism of the algorithm is, I was able to fix your version so that it works (the main problem was that you were using instance fields to store the deltas for the algorithm, but also using the same fields to initialize the algorithm, so once the algorithm ran once, subsequent executions wouldn't work). So for the sake of completeness, here is a second "retained" version of the code, using your preferred algorithm instead of the one I used above:
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
DoubleBuffered = true;
}
private PointF _previousPoint;
private PointF[] _points;
private void FractalDisplay_Load(object sender, EventArgs e)
{
Redraw();
}
private void Redraw()
{
List<PointF> points = new List<PointF>();
// Start here, to provide a bit of margin within the client area of the window
_previousPoint = new PointF(0.025f, 0.025f);
points.Add(_previousPoint);
int depth = (int)numericUpDown1.Value;
float gridCellCount = (float)(Math.Pow(2, depth) - 1);
// Use only 95% of the available space in the client area. Scale
// the delta for drawing to fill that 95% width/height exactly,
// according to the number of grid cells the given depth will
// produce in each direction.
GenerateHilbert3(depth, 0, 0.95f / gridCellCount, points);
_points = points.ToArray();
Invalidate();
}
private void GenerateHilbert(int depth, float xDistance, float yDistance, List<PointF> points)
{
if (depth < 1)
{
return;
}
GenerateHilbert(depth - 1, yDistance, xDistance, points);
DrawRelative(xDistance, yDistance, points);
GenerateHilbert(depth - 1, xDistance, yDistance, points);
DrawRelative(yDistance, xDistance, points);
GenerateHilbert(depth - 1, xDistance, yDistance, points);
DrawRelative(-xDistance, -yDistance, points);
GenerateHilbert(depth - 1, -yDistance, -xDistance, points);
}
private void DrawRelative(float xDistance, float yDistance, List<PointF> points)
{
// Discover where the new X and Y points will be
PointF currentPoint = _previousPoint + new SizeF(xDistance, yDistance);
// Paint from the current position of X and Y to the new positions of X and Y
points.Add(currentPoint);
// Update the Current Location of X and Y
_previousPoint = currentPoint;
}
// Perform the Actual Drawing
private void HilbertCurve_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
{
if (_points != null)
{
float scale = Math.Min(ClientSize.Width, ClientSize.Height);
e.Graphics.ScaleTransform(scale, scale);
using (Pen pen = new Pen(Color.Red, 1 / scale))
{
e.Graphics.DrawLines(pen, _points);
}
}
}
private void numericUpDown1_ValueChanged(object sender, EventArgs e)
{
Redraw();
}
protected override void OnClientSizeChanged(EventArgs e)
{
base.OnClientSizeChanged(e);
Invalidate();
}
}
As before, I've modified your implementation slightly, so that the drawing is scaled to fit within the window at all depths. This involves drawing into the unit square and then setting the transform appropriately according to the window size.
In addition to fixing the basic usage of Graphics, and the issue with the xLength and yLength fields, I also fixed a minor bug in your code (where you were recursing one level too deep) and cleaned up the recursion a bit (there's no need to repeat the depth check…just do it once, at the beginning of the recursive method).
It is of course possible to implement this in the "immediate" style as well. I think between this new code example, and the "immediate" method example above, I can leave that exercise to the reader. :)
- When did C allow casting constants and variables to struct for assignment?
- Why in C can I initialize more values than the size of an array?
- Using c to create a file and write+read to it, what went wrong?
- Does write system call need the data to be read to give >-1 return?
- Difference between fgetc() and read() function in C
- How can I get to know the IP address for interfaces in C?
- read fails with EFAULT
- In this case, how to achieve modularity and information hiding at the same time?
- Are global variables always initialized to zero in C?
- OpenGL function calls seemingly affecting unrelated data
- What Values of Variables x and y Will Produce Incorrect Results When Testing for Overflow After Subtraction of x-y in the Following Program?
- How to write a general-type queue library in c?
- Which gcc and g++ version support which standard of c and c++?
- How to dereference a member in a struct whose definition is not visible?
- How to name a type in a meaningful way?
- What are Vectors and < > in C?
- Why does 1.0/100.0 == 0.1/10.0 give True?
- How to organize the receive msg and user current input in C network such that it's clean
- Using inclusive scan syntax in OpenMP in the C language
- Unable to understand context in book "OOP in C" by Axel Schreiner
- variable-length array in struct with TI compiler in C (socket programming)
- A faster way to test 32bpp DDBs for a valid Alpha channel
- How can I compile the zephyr example-application as a freestanding application?
- Why does my forked process sometimes overwrite data in a file?
- _Generic in C needs typecasting?
- Declaring/defining an unused variable changes the output from an unrelated variable
- How to use gdb to explore the stack/heap?
- How can I read an input string of unknown length?
- Confused by difference between expression inside if and expression outside if
- Fast Arc Cos algorithm?