12,999,375 members (43,631 online)
alternative version

#### Stats

28.7K views
32 bookmarked
Posted 8 Jul 2011

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

, 8 Jul 2011
 Rate this:
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

```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);
}```

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.

```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
//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.

```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.

## About the Author

 Student University of Moratuwa Sri Lanka
PhD student specializing in video content analysis. Interested in Image processing, HCI and Digital music production. Computer and technology enthusiast. Love coding and sharing my knowledge.

## Comments and Discussions

 First Prev Next
 Extend to more control points MASheikh27-Jun-14 1:27 MASheikh 27-Jun-14 1:27
 My vote of 5 lazaro3-May-12 7:21 lazaro 3-May-12 7:21
 My vote of 5 manoj kumar choubey20-Feb-12 21:39 manoj kumar choubey 20-Feb-12 21:39
 My vote is 4 Anas.irm24-Jul-11 21:20 Anas.irm 24-Jul-11 21:20
 My vote of 3 toantvo9-Jul-11 17:06 toantvo 9-Jul-11 17:06
 Normally algorithm and just simple for beginning. Thanks for guidance.
 Re: My vote of 3 Ravimal Bandara10-Jul-11 2:47 Ravimal Bandara 10-Jul-11 2:47
 My vote of 5 MicroImaging9-Jul-11 9:32 MicroImaging 9-Jul-11 9:32
 Re: My vote of 5 Ravimal Bandara10-Jul-11 2:46 Ravimal Bandara 10-Jul-11 2:46
 My vote of 5 nayomiranamuka8-Jul-11 20:34 nayomiranamuka 8-Jul-11 20:34
 Re: My vote of 5 Ravimal Bandara9-Jul-11 1:04 Ravimal Bandara 9-Jul-11 1:04
 Last Visit: 31-Dec-99 18:00     Last Update: 24-Jun-17 4:06 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.