<p>I have never done this so this is just my best guess. I think you are on the track with the slope but I'm going to expand it little with some calculus. If you parameterize your curve by some variable t:</p>

<p>x(t) = ...</p>

<p>y(t) = ...</p>

<p>Then you can compute dx/dt and dy/dt which is how much x or y changes as you change t. This runs into some problems on a general purpose curve though. For example dx/dt might be a function of t. This means that the rate of change of x itself is changing as you move along the curve. But then you can also find dx/dt^2 (rate of change of the rate of change) and so on. This method is known as forward differencing.</p>

<p>Then what you can do is have an x, y starting point and draw a pixel there. Then you add the first order difference (dx/dt, dy/dt) to x and y. Then you add the second order difference to the first order difference and so on.</p>

<p>Here is a link I found on forward differencing:
<a href="http://www.nptel.ac.in/courses/122104018/node103.html" rel="nofollow noreferrer">http://www.nptel.ac.in/courses/122104018/node103.html</a></p>

<p>I haven't read it but it looks promising.</p>

<p>--edit--</p>

<p>Here's an example that was derived in my computer graphics class:
Some of the algebra can be tricky so it may or may not be correct.</p>

<pre><code>Q(t) = a*t^3 + b*t^2 + c*t + k
0 &lt; t &lt; 1
segment size d
num segments: 1/d

Q1(t) = Q(t + d) - Q(t)
= 3*a*d*t^2 + 3*a*t*d^2 + a*d^3 + 2*b + d + b*d^2 + c*d

Q2(t) = Q1(t + d) - Q1(t)
= b*a*t*d^2 + 6*a*d^3 + 2*b*d^2

Q3(t) = Q2(t + d) - Q2(t)
= b*a*d^3      &lt;==== no longer depends on t!
</code></pre>

<p>Iterate:</p>

<pre><code>init variables:
Q  = Q(0)  = k
Q1 = Q1(0) = a*d^3 + b*d^2 + c*d
Q2 = Q2(0) = b*a*d^3 + 2*b*d
Q3 = Q3(0) = b*a*d^3

repeat 1/d times:
    drawLine(Q, Q + Q1)
    Q  += Q1
    Q1 += Q2
    Q2 += Q3
</code></pre>

<p>Q is just for one of the x or y variables. You could have a QX, QX1, ... and QY, QY1, ... and forward difference them both in the same loop. Then draw using (QX, QY) and (QX + QX1, QY + QY1). You could also extend this into as many dimensions as you like.</p>

CC BY-SA 3.0
2017-12-14T03:34:27.413Z
Although I just realized that you were asking about the midpoint algorithm so I haven't really answered the question at all but I hope my post is helpful.
Chuck
CC BY-SA 3.0
2017-12-14T13:57:47.453Z
Your post is really helpful. I see where I went wrong. So I guess I either need to split up my curve, or do what you said and consider the derivatives. Thanks for the link, by the way, I'll make sure to read it when I have some time.
Daniel Kareh
CC BY-SA 3.0
2017-12-14T14:41:14.690Z
Its not really a derivative in the formal sense but it is very similar to the idea. Essentially you want to keep finding higher order differences until you get one that does not depend on t and so you would just be adding a constant every time. When you apply forward differencing you get a series of unconnected points. What you should really be doing is drawing straight lines between them. Here are some possibly helpful links on parametric equations: [1](http://tutorial.math.lamar.edu/Classes/CalcII/ParametricEqn.aspx) [2](http://jccc-mpg.wikidot.com/parametric-equations)
Chuck
CC BY-SA 3.0
2017-12-14T23:30:41.177Z
Okay, so that code example definitely helped me understand it. My question now is what if you can never differentiate the function into a constant, such as the sine function?
Daniel Kareh
CC BY-SA 3.0
2017-12-15T05:00:56.863Z
Yes that's a good catch, I was thinking about that as well. It seems that this might not work so well when functions involve things like sin, log, etc. One thing to keep in mind though is that this not a derivative. Its `f(x + d) - f(x)` So  you might possibly be able to simplify with some [identities](http://www.sosmath.com/trig/Trig5/trig5/trig5.html) while remembering that d is a constant (however I was not able to). I got as far as `sin(x + d) - sin(x) = sin(x)cos(d) + cos(x)sin(d) - sin(x)` and gave up.
Chuck
CC BY-SA 3.0
2017-12-15T05:01:03.713Z
In certain cases you may be able to come up with some sort of approximation or clever trick, see [here](https://math.stackexchange.com/questions/2063396/cubic-spline-between-circles) and [here](https://mathnow.wordpress.com/2009/11/06/a-rational-parameterization-of-the-unit-circle/).
Chuck
CC BY-SA 3.0
2017-12-14T03:32:46.393Z
2017-12-14T15:05:30.660Z
2017-12-14T15:05:30.660Z
Chuck
<p>I've been exploring the <a href="https://en.wikipedia.org/wiki/Midpoint_circle_algorithm" rel="nofollow noreferrer" title="Midpoint circle algorithm">Midpoint algorithm</a> for drawing lines and curves, and I have a quick question: How should you determine the <strong>fast direction</strong> for a curve? I've seen that if the shape is simple, you can draw one section and repeat the rest, but what if the shape does not have this property?</p>

<p>Right now I'm just using the derivative(slope), so I wonder if this is correct or cheaty? :P</p>

<curve><2d-graphics><midpoint>
Midpoint Algorithm Fast Direction
Daniel Kareh
# Midpoint Algorithm Fast Direction

(Asked by: username_0 on 2017-12-14)

I've been exploring the [Midpoint algorithm](https://en.wikipedia.org/wiki/Midpoint_circle_algorithm "Midpoint circle algorithm") for drawing lines and curves, and I have a quick question: How should you determine the **fast direction** for a curve? I've seen that if the shape is simple, you can draw one section and repeat the rest, but what if the shape does not have this property?

Right now I'm just using the derivative(slope), so I wonder if this is correct or cheaty? :P

**Tags:** curve, 2d-graphics, midpoint


---

## 1 answers

### Answer by username_1 on 2017-12-14. Score: 0 | Accepted answer

I have never done this so this is just my best guess. I think you are on the track with the slope but I'm going to expand it little with some calculus. If you parameterize your curve by some variable t:

x(t) = ...

y(t) = ...

Then you can compute dx/dt and dy/dt which is how much x or y changes as you change t. This runs into some problems on a general purpose curve though. For example dx/dt might be a function of t. This means that the rate of change of x itself is changing as you move along the curve. But then you can also find dx/dt^2 (rate of change of the rate of change) and so on. This method is known as forward differencing.

Then what you can do is have an x, y starting point and draw a pixel there. Then you add the first order difference (dx/dt, dy/dt) to x and y. Then you add the second order difference to the first order difference and so on.

Here is a link I found on forward differencing:
<http://www.nptel.ac.in/courses/122104018/node103.html>

I haven't read it but it looks promising.

--edit--

Here's an example that was derived in my computer graphics class:
Some of the algebra can be tricky so it may or may not be correct.

```
Q(t) = a*t^3 + b*t^2 + c*t + k
0 < t < 1
segment size d
num segments: 1/d

Q1(t) = Q(t + d) - Q(t)
= 3*a*d*t^2 + 3*a*t*d^2 + a*d^3 + 2*b + d + b*d^2 + c*d

Q2(t) = Q1(t + d) - Q1(t)
= b*a*t*d^2 + 6*a*d^3 + 2*b*d^2

Q3(t) = Q2(t + d) - Q2(t)
= b*a*d^3      <==== no longer depends on t!

```

Iterate:

```
init variables:
Q  = Q(0)  = k
Q1 = Q1(0) = a*d^3 + b*d^2 + c*d
Q2 = Q2(0) = b*a*d^3 + 2*b*d
Q3 = Q3(0) = b*a*d^3

repeat 1/d times:
    drawLine(Q, Q + Q1)
    Q  += Q1
    Q1 += Q2
    Q2 += Q3

```

Q is just for one of the x or y variables. You could have a QX, QX1, ... and QY, QY1, ... and forward difference them both in the same loop. Then draw using (QX, QY) and (QX + QX1, QY + QY1). You could also extend this into as many dimensions as you like.

> **Comments:**
> **username_1**: Although I just realized that you were asking about the midpoint algorithm so I haven't really answered the question at all but I hope my post is helpful.  
> **username_0**: Your post is really helpful. I see where I went wrong. So I guess I either need to split up my curve, or do what you said and consider the derivatives. Thanks for the link, by the way, I'll make sure to read it when I have some time.  
> **username_1**: Its not really a derivative in the formal sense but it is very similar to the idea. Essentially you want to keep finding higher order differences until you get one that does not depend on t and so you would just be adding a constant every time. When you apply forward differencing you get a series of unconnected points. What you should really be doing is drawing straight lines between them. Here are some possibly helpful links on parametric equations: [1](http://tutorial.math.lamar.edu/Classes/CalcII/ParametricEqn.aspx) [2](http://jccc-mpg.wikidot.com/parametric-equations)  
> **username_0**: Okay, so that code example definitely helped me understand it. My question now is what if you can never differentiate the function into a constant, such as the sine function?  
> **username_1**: Yes that's a good catch, I was thinking about that as well. It seems that this might not work so well when functions involve things like sin, log, etc. One thing to keep in mind though is that this not a derivative. Its `f(x + d) - f(x)` So  you might possibly be able to simplify with some [identities](http://www.sosmath.com/trig/Trig5/trig5/trig5.html) while remembering that d is a constant (however I was not able to). I got as far as `sin(x + d) - sin(x) = sin(x)cos(d) + cos(x)sin(d) - sin(x)` and gave up.  
> **username_1**: In certain cases you may be able to come up with some sort of approximation or clever trick, see [here](https://math.stackexchange.com/questions/2063396/cubic-spline-between-circles) and [here](https://mathnow.wordpress.com/2009/11/06/a-rational-parameterization-of-the-unit-circle/).  

---

