Let’s look at the following equations:

1.

2.

From (1) we get that , thus

From (2) we get that , thus

But

And thus …

QED

Skip to content
# PHP & More

## A technical blog about programming in PHP and other languages.

# The Proof That 2=4

# Bézier Curves

## The Definition

## About Tangents

# Tower Of Hanoi Without Recursion

## The Recursive (and Naive) Solution

## The Iterative Solution

### Proof

#### Steps 1 thru 2^{n} – 1

#### Step 2^{n}

#### Steps 2^{n} + 1 Thru 2^{n+1} – 1

# Blogging with StackEdit

## Editing the Post

## Publishing Your Post

# Static Variables in JavaScript

## Adding Static Variables

# StackEdit: Markdown Editor

# Hello, World!

# HTML5 Canvases & Transforms

## Transformations: Linear Algebra Made Easy

## An Example – The Koch Snowflake

Let’s look at the following equations:

1.

2.

From (1) we get that , thus

From (2) we get that , thus

But

And thus …

QED

Advertisements

The Bézier curve is a popular way to draw curves in graphic editors such as GIMP and Inkscape. A curve of degree n is defined using n+1 points, where the first and last are the start and end points of the curve, respectively, and the rest are control points.

For example:

The curve in the image above is a cubic Bézier curve. It has start and end points (filled with blue) and two control points (with no fill).

Each control point is attached by a straight line to a start or an end point, for a reason:

- The control points allows the user to control the curve intuitively.
- The straight line between the start(or end) point and its control point is tangent to the curve at the start(or end) point.

A Bézier curve is defined as the collection of points that are the result of the function

B(t) for every t in [0,1].

A linear Bézier is simply a straight line between to points P_{0} and P_{1}. The function is:

(1 – t)B_{P0} + tB_{P1}

For n>1, Be P_{0}, P_{1} … P_{n} the list of the curve’s points. Then the curve’s function is defined as

B_{P0P1…Pn}(t) = (t – 1)B_{P0P1…Pn-1}(t) + tB_{P1P2…Pn}(t)

Or, in its explicit form:

(Not a very precise definition because 0^{0} is not a number, so use the value 1 instead.)

This equation can be proved easily using the Pascal triangle.

From the explicit definition, you can see that the translation is done by adding the same coordinates to which of the curves start, end and control points.

because:

Rotations and translations are done by a transform matrix. So, if T is a transform matrix:

TB_{P1,P2,…Pn} = B_{TP1,TP2,…TPn}

Now, in a Bézier curve, B_{P0P1…Pn}(t), The line P_{0} – P_{1} is tangent to the curve at point P_{0}, and P_{n} – P_{n-1} is tangent to the curve at point P_{n}

To prove this we’ll have to show that the derivative of a Bézier curve of degree n at the start and end points is a non-zero scalar multiplied by the difference between P_{1} and P_{0}, and between P_{n} and P_{n-1}.

That scalar is `n`

.

For n=1;

B_{P0,P1} = (1 – t)P_{0} + tP_{1}

Let’s derive:

B’_{P0,P1} = -P_{0} + P_{1}

**Good!**

Let’s assume it’s correct for n, and prove for n+1

B_{P0,P1…,Pn+1}(t) = (1 – t)B_{P0,P1…,Pn}(t) + tB_{P1,P2…,Pn+1}(t)

Let’s derive:

B’_{P0,P1…,Pn+1}(t) = -B_{P0,P1…,Pn}(t) + (1-t)B’_{P0,P1…,Pn}(t) + B_{P1,P2…,Pn+1}(t) + tB’_{P1,P2…,Pn+1}(t)

Now, to get the tangent to the curve at p_{0}, let;s assign t=0:

B’_{P0,P1…,Pn+1}(0) = -B_{P0,P1…,Pn}(0) + B’_{P0,P1…,Pn}(0) + B_{P1,P2…,Pn+1}(0) =

= – P_{0} + n(P_{1} – P_{0}) + P_{1} = (n+1)(P_{1} – P_{0})

**Good!**

Now, to get the tangent to the curve at p_{0}, let;s assign t=1:

B’_{P0,P1…,Pn+1}(1) = -B_{P0,P1…,Pn}(1) + B_{P1,P2…,Pn+1}(1) + B’_{P1,P2…,Pn+1}(1) =

= – P_{n} + P_{n+1} + n(P_{n+1} – P_{n}) + P_{1} = (n+1)(P_{n+1} – P_{n})

**QED**

SVG supports Bézier curves of up to the third degree. A path consisting of such curves are good approximations of shapes provided that you have enough points.

If you’ve taken courses in computer sciences, you probably know the Tower Of Hanoi algorithm. The task is to move a tower of discs from the source rod the the destination using an auxiliary rod. Each disc should be placed on a bigger one all the time.

The solution is to move all discs on top of the biggest one to the auxiliary rod, then move the biggest disc to the destination rod and then move all the rest to the destination (according to the rules of course, and one disc at a time).

The function that moves `n`

discs from `src`

to `dst`

using `aux`

looks like:

```
function moveDiscs(n, src, dst, aux){
if (n > 1)
moveDiscs(n-1, src, aux, dst);
print("Move from " + src + " to " + dst);
if (n>1)
moveDiscs(n-1, aux, dst, src);
}
```

We’ll use that function later to prove that the non-recursive algorithm does the same.

A naive iterative solution is to use a binary search and find for each move of a disc, the parameters passed to `moveDiscs`

when `n=1`

. This is crazy! We don’t want time complexity `o(n)`

just to move the first disc.

Let’s look at a better solution:

Repeat the 3 steps in table 1 until all discs are moved, depending on the value of `n`

:

__Table 1:__

If `n` is even |
If `n` is odd |
---|---|

perform a legal move between `src` and `aux` |
perform a legal move between `src` and `dst` |

perform a legal move between `src` and `dst` |
perform a legal move between `src` and `aux` |

perform a legal move between `aux` and `dst` |
perform a legal move between `aux` and `dst` |

Note: perform no more step after all discs have been moved to the destination.

For `n`

= 1, just move a disc from `src`

to `dst`

For `n`

= 2, take a look at the recursive function.

For `n`

≥ 3:

The total number of moves is 2^{n} – 1

Let’s assume our algorithm works for any natural number `n`

and prove for `n`

+1:

Let’s look at the first call to `moveDiscs`

inside itself:

`moveDiscs(n-1, src, aux, dst); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n``

Let’s look how it is performed:

Per our assumption, the sequence for steps 1 thru 2^{n} – 1 is

If `n` is even |
If `n` is odd |
---|---|

perform a legal move between `src` and `dst` |
perform a legal move between `src` and `aux` |

perform a legal move between `src` and `aux` |
perform a legal move between `src` and `dst` |

perform a legal move between `aux` and `dst` |
perform a legal move between `aux` and `dst` |

Because if `n`

is odd, `n+1`

is even and vice versa, we get that the first steps are performed correctly by the iterative algorithm

This is when we move a disc from `src`

to `dst`

If `n`

is even, 2^{n}≡1 mod 3, thus it matches step 1 in *Table 1* for odd `n+1`

.

If `n`

is odd, 2^{n}≡2 mod 3, thus it matches step 2 in *Table 1* for even `n+1`

.

Thus, our iterative algorithm is still correct.

Those steps are performed by the second call to `moveDiscs`

inside itself:

`moveDiscs(n-1, aux, dst, src); // Remember that we prove for `n+1`, so `n-1` in the function actually means `n``

If `n` is even |
If `n` is odd |
---|---|

perform a legal move between `aux` and `src` (step 2 for odd `n+1` ) |
perform a legal move between `aux` and `dst` (step 3 for even `n+1` ) |

perform a legal move between `aux` and `dst` (step 3 for odd `n+1` ) |
perform a legal move between `src` and `aux` (step 1 for even `n+1` ) |

perform a legal move between `src` and `dst` (step 1 for odd `n+1` ) |
perform a legal move between `src` and `dst` step 2 for even `n+1` ) |

In this table we see the steps that follow step 2^{n}.

Thus, the algorithm works correctly for the last part, and thus our whole algorithm is correct.

You can now watch a working Hanoi animation here.

Table Of Contents:

Would you like to add posts to your blog with a cool editor? Do you want to publish in Blogger, WordPress, Tumblr, etc.?

Try StackEdit Click the link you’ve just seen, and start editing a markdown document. Forget about switching from WYSIWYG to HTML and back. Enjoy a split-screen instead: one side is where you type in markdown format, and the other is the WYSIWYG result.

Editing a post is simpler than editing an HTML page, and sometimes even simpler than working with the text editor provided by the blogging site. For example, if you add code to your post, just write it between two lines starting with three back-ticks (back-quotes).

For example:

‘‘‘

var j=3;

‘‘‘

will be displayed as:

`var j=3;`

- To display headers of level H1 or H2, type a line of equal-signs or dashes respectively under tho header text.
- For H1 thru H6, begin the lines with number of pounds equal to the level (#, ##, …, ######).
- Place your
**bold text**between two pairs of asterisks (**bold text**). - Place your
*italic text*between single asterisks or underscores. (_italic_). - Hyperlinks: there are two ways to add them, one is to simply type the URL, for example ‘http://example.com, the other is to type the text in brackets, and the link in parentheses, for example: [Example Site](http://example.com).

You can learn more about markdown syntax, by clicking the syntax icon in from the floating menu at the bottom:

Before publishing, let’s set variables, such as tags. Type your variables, between two lines, consisting of three dashes as follows:

—

variable: value

—

For example:

—

tags: tag1, tag2, tag3

—

You can see which variables you can set, when you decide where to publish your post.

To publish a post, click on the ‘#’ menu, and choose publish as shown in the following image:

After choosing the site to which you want to publish, click OK or Cancel (if you want to set the * interpreted variables*, for example.)

NOTE: It is recommended to upload images to the site before including it in your document.

Now, you can use StackEdit to update your post.

Enjoy!

Written with StackEdit.

How do you declare a static variable in a JavaScript function?

Not with the word “*static*“.

In JavaScript “*function*” is a variable type similar to “*object*“.

The difference is that the reference to a function inside itself is not `this`

but `arguments.callee`

.

An example of using `arguments.callee`

is the following function that returns itself:

```
function func(){
return arguments.callee;
}
```

You can add arguments to `arguments.callee`

. To initialize it the first time, check first if it is not defined. For example:

```
if (typeof(arguments.callee.myStaticVar)!="undefined")
arguments.callee.myStaticVar=0;
```

Following is an example function in [rhino(http://rhino.org) JavaScript(run from the command line):

```
function _example(){
var thisFunction = arguments.callee;
if (!thisFunction.static){
thisFunction.static=0;
}
++thisFunction.static;
print("This function has been called: " + thisFunction.static + " times");
};
```

In this example, you can change the static variable’s value without calling the function using `_example.static = "some value";`

.

To prevent this, encapsulate your function using a function called once, for example:

```
(function(){
function _example(){
var thisFunction = arguments.callee;
if (!thisFunction.static){
thisFunction.static=0;
}
++thisFunction.static;
print("This function has been called: " + thisFunction.static + " times");
};
example=function(){
_example();
}
})();
```

Now, each time `example()`

is called, it will increment the variable`static`

, but the variable cannot be incremented without calling `example`

because `_example`

is private.

Written with StackEdit.

I am a blog post written in Markdown, and sent from the StackEdit editor.

Do you know those files with suffix ‘.md’? They are markdown documents, and they are easy to write and easy to read because they don’t have to contain HTML tags!

Here’s an example of how to add a link:

Type “[The Example Site](http://example.com)” to get the following link:

This tool can export your document as HTML. sponsors can use this tool to export documents as PDF..

Written with StackEdit.

Browsers supporting HTML5 allow you to draw on the browser’s screen without preparing an image file before. Drawing on a canvas is done using the wonderful Javascript language. If you want to draw a 2-dimensional image on canvas element ‘cnv’, get the drawing context using:

var ctx = cnv.getContext("2d")

And use that context to draw everything using the standard functions:

moveTo, lineTo, arc, fillRect, etc.

Learn more about drawing here.

You can use the functions to create more complicated shapes easily thanks to transform functions:

The origin(0,0) of the canvas is defined to be the top-left pixel of the canvas element. And the coordinates are given in number of pixels. This can change by using transforms.

The transformation functions are:

- scale(x,y): this will make every shape x times wider and y time taller.
- translate(x,y): now coordinate (0,0) will be shifted x units to the right, and y units down.
- rotate(angle): will rotete the axes by given angle in radians.
- transform(a,b,c,d,e,f): If you want to use a transformation matrix
- setTransfrom(a,b,c,d,e,f): reset all transform, and perform transform(a,b,c,d,e,f).

a,b,c,d,e,f are values in the matrix:

The values a,b,c,d are used for rotating and scaling. e,f for translating.

Other useful methods of the context are:

- ctx.save() – to save current transform in a stack (Last In First Out).
- ctx.restore() – to retrieve the trnasform from the top of the stack.

The algorithm for drawing the Koch Snowflake can be found in the post Drawing The Koch Snowflake Fractal With GIMP.

Here’s an example in Javascript:

function drawSide(ctx, len){ if (len > 1) { var thirdOfLen = len / 3.; var rotationAngles = [0, -Math.PI / 3, 2 * Math.PI / 3., -Math.PI / 3]; rotationAngles.forEach(function(val){ if (val != 0){ ctx.translate(thirdOfLen, 0); ctx.rotate(val); } ctx.save(); drawSide(ctx, thirdOfLen); ctx.restore(); }); } else { ctx.moveTo(0,0); ctx.lineTo(len,0); //ctx.stroke(); } } ctx.translate(startX, startY); for (i=0; i<3; i++){ ctx.save(); drawSide(ctx, sideLength); ctx.restore(); ctx.translate(sideLength,0); ctx.rotate(2*Math.PI/3); } ctx.stroke(); }

Warning: using ctx.stroke() after every little line you draw might make your code inefficient, and slow down your browser.

Transformation functions are also part of the Processing language.