15,124,353 members
Articles / Multimedia / GDI+
Article
Posted 8 Jul 2011

49.8K views
3K downloads
34 bookmarked

# Midpoint Algorithm (Divide and Conquer Method) for Drawing a Simple Bezier Curve

Rate me:
4.78/5 (19 votes)
8 Jul 2011CPOL3 min read
A simple program that helps to understand the midpoint algorithm for constructing a Bezier curve.

## Introduction

A Bezier curve is a parametric curve frequently used in computer graphics and related fields. In vector graphics, Bezier curves are used to model smooth curves that can be scaled indefinitely. There are many ways to construct a Bezier curve. This simple program uses the midpoint algorithm of constructing a Bezier curve. To show the nature of the divide and conquer approach in the algorithm, a recursive function has been used to implement the construction of the piece of Bezier curve.

## Constructing a Bezier Curve

This program builds a Bezier curve based on three points that can be adjusted manually. The below animation shows what exactly happens in the code while we construct a Bezier curve with two iterations of the midpoint method.

The points that are shown in red are the initial points. After giving the initial points, it calculates the mid points of each line that lies between the three initial points. These newly calculated mid points are shown in green. The points that turn their color to blue will be on the final Bezier curve. The order of the color changing is identical to the order of calculating points for the Bezier curve in the code. The Bezier curve that is approximated using the given points and two iterations is shown by a set of straight lines with the color red.

## Using the Code

### Classes

• Class `BezierCurve`: The class that is responsible for constructing the Bezier curve.
• Class `CustomCanvas`: The class that is responsible for the graphical view and points manipulation of the curve.

### Functions

C#
```private void CreateBezier(PointF ctrl1, PointF ctrl2, PointF ctrl3)
{
bezierPoints = new List<PointF>();
bezierPoints.Clear();
bezierPoints.Add(ctrl1); // add the first control point
PopulateBezierPoints(ctrl1, ctrl2, ctrl3, 0);
bezierPoints.Add(ctrl3);// add the last control point
}```

This function takes three points as parameters and then populates the list of points of the curve. The point `ctrl1` (point in the starting end of the curve) is obviously in the curve so it is added to the list without doing any calculation. Then it invokes the function `PopulateBezierPoints` to calculate the rest of the points on the curve. Finally, the point `ctrl3` is added to the list because obviously it is the point at the other end of the curve.

C#
```private void PopulateBezierPoints(PointF ctrl1, PointF ctrl2,
PointF ctrl3, int currentIteration)
{
if (currentIteration < iterations)
{
//calculate next mid points
PointF midPoint1 = MidPoint(ctrl1, ctrl2);
PointF midPoint2 = MidPoint(ctrl2, ctrl3);
PointF midPoint3 = MidPoint(midPoint1, midPoint2);
//the next control point
currentIteration++;
PopulateBezierPoints(ctrl1, midPoint1,
midPoint3, currentIteration);//left branch
bezierPoints.Add(midPoint3);
//add the next control point
PopulateBezierPoints(midPoint3, midPoint2, ctrl3, currentIteration);
//right branch
}
}```

This function takes the three initial points with the `currentIteration` number as the parameter. This function is recursively called and at the beginning, the current iteration number is zero. The number of iterations in the algorithm should be set before invoking this function.

This function simply gets the midpoint of the first two points, the midpoint of the last two points from the given three points, and the midpoint of the above two new midpoints if `currentIteration` is less than the number of `iterations` that is to be iterated in the algorithm (the value of the variable `iterations` is the value that has been selected by the user from the user interface). After calculating the three new midpoints, we get a pair of three points. One set of points in this pair is to construct the left part of the curve and the other set of points is for constructing the right part of the curve. According to the order of invoking this recursive function, it adds the points in the curve from the left part to the right part of the curve to the list. You can refer to the above animation to get a better idea of the order of execution of this function.

C#
```private PointF MidPoint(PointF controlPoint1, PointF controlPoint2)
{
return new PointF(
(controlPoint1.X + controlPoint2.X) / 2,
(controlPoint1.Y + controlPoint2.Y) / 2
);
}```

This function takes two points as parameters and returns the midpoint of them.

## How to Use

The program allows you to specify the three initial points and the number of iterations. Then you can observe the smoothness and the number of points on the Bezier curve. In addition to that, you can move the initial points by dragging them.

## Remarks

Use of a recursion function for constructing a Bezier curve is not practical when the curve becomes more complex and smoother. In a such case, we have to use some efficient methods to construct a Bezier curve.

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## Comments and Discussions

 First Prev Next
 Extend to more control points MASheikh27-Jun-14 2:27 MASheikh 27-Jun-14 2:27
 My vote of 5 Lazaro Lima3-May-12 8:21 Lazaro Lima 3-May-12 8:21
 My vote of 5 Manoj Kumar Choubey20-Feb-12 22:39 Manoj Kumar Choubey 20-Feb-12 22:39
 My vote is 4 Anas.irm24-Jul-11 22:20 Anas.irm 24-Jul-11 22:20
 My vote of 3 toantvo9-Jul-11 18:06 toantvo 9-Jul-11 18:06
 Re: My vote of 3 Ravimal Bandara10-Jul-11 3:47 Ravimal Bandara 10-Jul-11 3:47
 My vote of 5 MicroImaging9-Jul-11 10:32 MicroImaging 9-Jul-11 10:32
 Thank you for bringing this algorithm i have never heard of to my attention.
 Re: My vote of 5 Ravimal Bandara10-Jul-11 3:46 Ravimal Bandara 10-Jul-11 3:46
 My vote of 5 nayomiranamuka8-Jul-11 21:34 nayomiranamuka 8-Jul-11 21:34
 Re: My vote of 5 Ravimal Bandara9-Jul-11 2:04 Ravimal Bandara 9-Jul-11 2:04
 Last Visit: 31-Dec-99 19:00     Last Update: 7-Dec-21 4:26 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.