Help! Getting a “nice” reverse engineered Bézier curve

Commenter Timo wants to know how to get a nice shape for a reverse engineered Bézier curve.

The question started from calculating the control points of a cubic Bézier curve if you’re given 4 points that lie on the curve, assuming the first and last given points were also the first and last control points. I wrote a similar article for a quadratic Bézier curve too.

To sum up, you have 1 degree of freedom when working on a quadratic Bézier curve. In the case of a cubic Bézier curve, you have 2 degrees of freedom, meaning 2 variables in the calculation that you have to decide on. Now this posed a problem, because there are an infinite number of solutions. How do you decide on a numeric value?

Well, for a quadratic Bézier curve, the simplest and obvious option is to choose the second given point (since the first and last control points are determinable) to be at the halfway mark. For a cubic Bézier curve, the second and third given points are chosen to be at the 1/3 and 2/3 mark along the curve respectively. Now this may or may not be suitable, but it does give you something to start with.

I want to state right now, that I had not been doing formal mathematics for a while. There is a limit to what I know, and I’m not an expert. I just know enough to figure out how to solve problems. Sometimes, it’s not enough. Keep that in mind.

“Nice curve” is subjective

Now Timo’s problem is getting a better shaped cubic Bézier curve from those calculations. Since the 4 given points are fixed, and the first and last control points are also fixed, the only thing you can manipulate are the second and third control points. Which in turn means deciding on values of u and v to get a “nice” cubic Bézier curve in the end.

This, “niceness”, is a subjective criteria. How do you determine if a cubic Bézier curve looks nice? Remember that we don’t have the control points yet. So we don’t know how the curve looks like. So we don’t even know if manipulating the second and third control point to not be at 1/3 and 2/3 will result in a nice curve. It’s a chicken and egg problem.

Apportioned chord length

During the correspondence with Timo, some solutions were discussed. The next simplest set of values to try for u and v are calculated based on the given points.

Let d1 be the distance between the first and second given point.
Let d2 be the distance between the second and third given point.
Let d3 be the distance between the third and last (fourth) given point.

Then let u = d1/(d1 + d2 + d3) and v = (d1 + d2)/(d1 + d2 + d3). This should result in a curve that’s “better shaped” than the (u,v) pair (1/3, 2/3). When I wrote that article for the cubic curve version, this was the next default set of values for u and v, but I didn’t want to add too much more. Well, nobody asked, so I left it as it was.

It turns out that Don Lancaster already wrote about it. He called it “apportioned chords” method.
http://www.tinaja.com/glib/nubz4pts1.pdf

Inflection points

Then Timo had another problem. He wanted the second and third given points to also lie at the “loop tips”. What are loop tips? After some clarification, I believe Timo is referring to the inflection points on the curve. An inflection point

is a point on a curve at which the curvature (second derivative) changes signs. The curve changes from being concave upwards (positive curvature) to concave downwards (negative curvature), or vice versa.

A cubic Bézier curve can have 0, 1 or 2 inflection points. If it’s a straight line, it has 0. If it’s U-shaped, it has 1. And if it zigzags, it has 2. And Adrian Colomitchi proved that there are at most 2 inflection points on a cubic Bézier curve.

UPDATE: The following diagram is wrong. Please refer to this article for the correct version. I was thinking of points where the second derivative was zero, not when it changed signs (as defined above).

Inflection points

As you can see, inflection points don’t necessarily have to coincide with the given points.

By the way, I used Paint.NET for the illustration. I took a screenshot of me drawing the curve, still with the given points visible (noted by the small squares). Paint.NET appears to have succeeded in doing the very thing Timo wants, to render a cubic Bézier curve using 4 given points. Of course, I’m assuming the image editor is using cubic Bézier curves…

The math paper

I found another reference with a more explicit mathematical formulation to help Timo.
http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

As of this writing, page 3 of that paper explicitly shows the calculation needed to find the inflection points of a cubic Bézier curve, if they exist. Let me emphasise that again. The curve might have 2 inflection points, only 1 inflection point, or none at all (a straight line, the trivial version of a Bezier curve, has no inflection points).

Maximum curvature

Then Timo found another forum posting for the fast calculation of maximum curvature. An inflection point would have the “maximum curvature”. The problem with that solution is that it assumes we have the control points.

So my suggestion was to do iteration. Use my method to get a set of control points. Perhaps use the apportioned chords to start off with a good set of control points. Then apply the maximum curvature solution to find the inflection points and the associated values of t. With those values of t, pump them back into my method to find a new set of control points. Pump those control points into the maximum curvature solution to find inflection points and their t values. Iterate till the t values between iterations are within acceptable margins of error.

Caveat: I don’t know if this combination of 2 algorithms in an iterative manner will converge. I have not tested this. Use at your own risk.

Scaling up to 3 dimensions

Anyway, Timo found another solution himself (he didn’t say what though). He still needed to handle that cusp point. What cusp point, you ask? It’s in page 3 of that paper I mentioned above. That paper is for 2 dimensional cubic Bézier curves. The degree of the curve is independent of the degree of the dimensions. Timo wants to know how the 3 dimensional case will look like.

Now, the method of finding inflection points is to do a cross product of the first derivative and second derivative of the cubic Bézier curve equation. The Bézier curve is parametrised into

x(t) = ax * t^3 + bx * t^2 + cx * t + dx
y(t) = ay * t^3 + by * t^2 + cy * t + dy

and using the Bézier basis matrix, the coefficients are

ax = -x0 + 3*x1 – 3*x2 + x3
bx = 3*x0 – 6*x1 + 3*x2
cx = -3*x0 + 3*x1
dx = x0

ay = -y0 + 3*y1 – 3*y2 + y3
by = 3*y0 – 6*y1 + 3*y2
cy = -3*y0 + 3*y1
dy = y0

Set the cross product to 0. The inflection points are found at values of t when you solve that equation:

x’ * y” – x” * y’ = 0

where x’ and x” are the first and second derivatives of x(t). Similarly for y’ and y”. The solution is in that paper I mentioned before.

This is if the curve is in 2D. The cross product of 2D vectors is a scalar. And we set the scalar to 0 to solve for t. The cross product of 3D vectors is a vector, and so we’re solving with a zero vector.

So with
z(t) = az * t^3 + bz * t^2 + cz * t + dz
for the third dimension, we have

x’ = 3 * ax * t^2 + 2 * bx * t + cx
y’ = 3 * ay * t^2 + 2 * by * t + cy
z’ = 3 * az * t^2 + 2 * bz * t + cz

x” = 6 * ax * t + 2 * bx
y” = 6 * ay * t + 2 * by
z” = 6 * az * t + 2 * bz

The cross product is the determinant of the following
Cross product

where i, j, k are the unit vectors. I’ll leave it to you to find out the formula for the determinant of a 3 by 3 matrix.

So we’re going to solve this:
0 = (y’ * z’’ – z’ * y’’) * i – (x’ * z’’ – z’ * x’’) * j + (x’ * y’’ – y’ * x’’) * k
where 0 is the zero vector.

This implies that

y’ * z’’ – z’ * y’’ = 0
x’ * z’’ – z’ * x’’ = 0
x’ * y’’ – y’ * x’’ = 0

This time the zeroes are scalars. We now have 3 times the number of equations to solve when compared to the 2D case. This means there are potentially 6 values of t for the inflection points to check. Hopefully, there will be repeated values of t. Hopefully, the number of unique values of t is 2 or less (remember Adrian’s proof?).

If a t value is repeated, it’s probably an inflection point. What if we get 6 unique values? Is a 6-unique-value case even possible? I don’t know. You’ll have to interpret the values in the best way you can, based on some assumptions and arguments.

What do you think?

So after reading through that entire article, what do you think? Comments on the methods I described? Do you have a new method? Your thoughts on whether this problem is even solvable? That I’m a complete idiot?

Let me know in a comment. Or better, write a blog post and tell me about it. Because if it took me that long to explain the solutions, your solution is probably just as long. It’s a Bézier curve. A picture might be appropriate.

Percentage contribution over the long-term

Two business partners

Some time ago, I received an unusual request for help from a stranger via email. It was something of a financial nature, and I felt incapable of answering it fully. So I turned to Christopher, my engineer friend who’s also versed in finance, for help. I felt that the stranger’s request was quite personal, and I wasn’t sure if the stranger wanted the request to be publicised here on the blog. So to protect the innocent, I will wrangle the original problem to be most indecipherable. However, the solution given by Christopher was worth mentioning.

On to the problem then. We shall stick only to money as the sole source of contribution. Emotional and effort labour are just as important, but it’s difficult to quantify them mathematically. We’ll even ignore time labour. It’s not fair, but the world sometimes operate that way, so we’ll just accept it as best as we can.

Suppose there are 2 partners in a new business. Each of them contributes a different amount of money each month to the business, and may even contribute variably across each month. The money is used to maintain the business (for example, settle any bank loans, pay salaries, web site hosting costs, marketing expenses, product creation costs, utility bills and so on). After say 3 years, they want to sell off the business and liquidate their assets in it.

How much should each business partner take from that lump sum of money (from selling the business), based solely on their monetary contribution over the years?

The main problem of using a simple summation of their monetary contributions and calculating a percentage based on that, is inflation. $100 contributed in the 1st month is worth more than $100 contributed in the 37th month (4th year, 1st month).

Christopher suggested abiding by a yearly rate for the purpose of inflation, in particular, using government bonds as the rate. To add stability to the rate, he suggested using the 10-year bond rate. The currency also matters. For our example, we’ll use the United Kingdom pound. Where you get that rate is up to you, as long as you feel it’s legitimate and correct, and that everyone agrees to using that rate. I got mine from Bloomberg (suggested by Christopher):

http://www.bloomberg.com/markets/rates/uk.html

Government bond rate
[note: the above was correct as of time of writing this article. You are advised to go visit the Bloomberg site for the updated numbers. Or some other trusted site you know because you’re probably more financially powerful than me.]

The rate is 3.51% for the 10-year yield.

The mathematical formulation

Let’s give our business partners names, Arianna and Ben.

Let s(i) be the “sum” at end of year i
Let x(i) be contribution of Arianna in year i
Let y(i) be contribution of Ben in year i
Let b(i) be bond interest rate in year i (3.51% is changed to 0.0351 without the percent).

Then s(i+1) = [1 + b(i)] * [s(i) + x(i) + y(i)]

Let cx(i) be sum contribution of Arianna, and cy(i) be sum contribution of Ben at end of year i.

Then cx(i+1) = [1 + b(i)] * [cx(i) + x(i)]
and cy(i+1) = [1 + b(i)] * [cy(i) + y(i)]

Then contribution percentage at end of year i of Arianna is
100 * cx(i) / s(i)

Contribution percentage at end of year i of Ben is
100 * cy(i) / s(i)

A short example (with numbers)

And a note. The numbers were picked out of thin air. I am not saying a man is better than a woman in the business arena. I need some numeric variation, and I just took it as the man contributing more. And the fact that I don’t want to search the stock photos for generic businessy settings with 2 people in them for hours. For some reason, it’s very hard to find a photo with 2 business people of the same gender. Then you wouldn’t be able to guess which one was which. I originally had Andy and Ben starring in my example.

Anyway…

Let’s say, in the 1st month, Arianna and Ben contribute £100 and £150 respectively. In the 2nd month, £200 and £100 respectively. In the 3rd month, £0 and £250 respectively. For the 1st year, Arianna and Ben contribute £1200 and £1800 respectively, for a grand total of £3000.

So at the start of the 2nd year, we look at the rate and say we find it’s 3.5%. Then we inflate their contributions by 3.5% to £1242 (1.035 * 1200) and £1863 (1.035 * 1800) respectively. We also inflate the sum total from £3000 to £3105.

Arianna and Ben continue to contribute to the business in the 2nd year. And at the end of the 2nd year, Arianna and Ben contributed £2100 and £1900 respectively (total £4000).

At the start of the 3rd year, we find the rate to be 3.52%. Here’s where it’s different. First we add the respective contributions to the previous inflated amounts. So we have £3342 (£1242 + £2100), £3763 (£1863 + £1900) and £7105 (£3105 + £4000) for Arianna, Ben and the sum total respectively. Then we inflate them by 3.52% to get £3459.64, £3895.46 and £7355.10.

For the 3rd year, Arianna and Ben contribute £2400 and £2600 respectively. And at the start of the 4th year, the rate is 3.51%.

Adding the sum contributions first, we get £5859.64, £6495.46 and £12355.10 for Arianna, Ben and sum total respectively. Inflating the numbers by 3.51%, we get £6065.31, £6723.45 and £12788.76. At this point, our business partners want to sell off their business, and they want to know what’s their percentage contribution.

So Arianna contributed 100 * 6065.31 / 12788.76 = 47.43%.
Ben contributed 100 * 6723.45 / 12788.76 = 52.57%

Further notes

I didn’t take care of rounding issues and decimal places in the example. I’ll leave that to you as an exercise. The most accurate method will be to store the values as they are, and only take them out for calculations at the final stage. Storing intermediate results might skew the accuracy if done over many iterations.

The other point is that you are free to calculate on a monthly basis instead of a yearly basis. The assumption is that the rate stays stable throughout the year, so a yearly rate is usable. If you’re inflating on a monthly basis, the contribution values will shoot up very quickly. They will not have any semblance to their original values. I want you to remember that the values are used to calculate the final percentage contribution, not the absolute contribution.

Contributing $40 out of $100 is 40%. Contributing $673.20 out of $1683 is also 40%. It’s relative.

[note to self: why didn’t I think of using a currency with $, the generic dollar sign? I had to go pick the pound, and then had to replace all the monetary values in the example with the correct currency symbol…]

[UPDATE: the stranger found another of my article on percentage calculations. It must have made sense, because the stranger took that to mean I could help with the problem the stranger was facing. Yes, I’m using “the stranger” so you don’t even know the gender. How’s that for anonymity?]

[leading image by nyul]

Reverse engineering quadratic Bézier curves

I wrote an article on cubic Bézier curves almost 3 years ago. And there had been emails and comments sporadically during that period. The latest one was from a lady, so I decided to write something about it (yes, I’m biased).

The recurring (if you count 2 or 3 as recurring) question is about quadratic Bézier curves. I provided a method for calculating the 4 control points of a cubic Bézier curve, given 4 points that the curve has to pass through. The question is, how do you calculate the 3 control points of a quadratic Bézier curve, given 3 points that the curve has to pass through? The 1st and 3rd points are also the end points of the curve.

As with the cubic version, there are infinitely many solutions. The question I posed above missed out a crucial element which would give a unique solution. How far along the curve is the 2nd point? Let’s look at the quadratic Bézier equation first:

B(t) = (1-t)^2 * p0 + 2(1-t)t * p1 + t^2 * p2

where p0, p1 and p2 are the control points, and t in [0,1]

Suppose you have 3 points that the curve has to pass through. The 1st and 3rd points are also the 1st and 3rd control points (substitute t=0 and t=1 into the equation to see why that is so). That leaves the 2nd control point to be calculated. If you didn’t know, the inner control points of a Bézier curve don’t necessarily fall on the curve itself (and usually don’t).

Since you know the 3 points that pass through the curve, and the 1st and 3rd control points are known, let the points be p0, f and p2, where f is the point on the curve when t=u. Stating the value of u is the crucial element for a unique solution. In the case of a quadratic Bézier curve, the value off the top of my head is 1/2. Meaning the 2nd known point is assumed to fall about halfway along the curve. You may have a different opinion based on the problem you’re trying to solve.

So let’s substitute into the equation, shall we? At the 2nd known point f, we have

f = (1-u)^2 * p0 + 2(1-u)u * p1 + u^2 * p2

Rearranging the terms, we have

p1
= [f – (1-u)^2 * p0 – u^2 * p2] / 2(1-u)u
= 1/(2(1-u)u) * f – (1-u)/2u * p0 – u/2(1-u) * p2

Remember that u is determined by you (1/2 is a good value if you have no other information otherwise). p0, f, and p2 are the 3 known points that pass through the curve (f is the point where t=u). So the only unknown is p1, the 2nd control point.

And I can “cancel” the (1-u) and u terms in the simplification because u is strictly between 0 and 1. In particular, u cannot be equal to 0 or 1.

There you have it. A unique solution to finding the control points of a quadratic Bézier curve.

An example

But hey, I’m feeling generous. I’ll do up a solution with real values.

Suppose you have 3 points [1,1], [2,3], [4,2] that pass through a quadratic Bézier curve. The 1st and 3rd points, [1,1] and [4,2] are the 1st and 3rd control points respectively. That leaves calculating the 2nd control point such that the curve pass through [2,3] when t=0.5 (let’s assume [2,3] is halfway along the curve).

Let’s look at the final stage of our 2nd control point calculation

p1
= 1/(2(1-u)u) * f – (1-u)/2u * p0 – u/2(1-u) * p2
= 1/(2*(1-0.5)*0.5) * [2,3] – (1-0.5)/(2*0.5) * [1,1] – (0.5)/(2*(1-0.5)) * [4,2]
= 2 * [2,3] – 0.5 * [1,1] – 0.5 * [4,2]
= [4,6] – [0.5,0.5] – [2,1]
= [1.5,4.5]

So the final control points are [1,1], [1.5,4.5] and [4,2].

Quadratic Bezier curve

Curve tension

But wait, there’s bonus material! The lady also asked about curve tension. I’m not sure if that’s the correct term. Basically, she wanted to know how to skew the 2nd control point towards the 1st or 3rd control points.

This one’s easy. Just adjust your u value. If you assume u=0.2, then the 2nd control point is skewed towards p0, the 1st control point. If you assume u=0.8, then the 2nd control point is skewed towards p2, the 3rd control point.

So to skew towards p0, let u be closer to 0. To skew towards p2, let u be closer to 1.

Remember, u is decided by you, unless the problem you’re solving states otherwise.

A square described in any rotational orientation with 1 equation

What started out as an innocent question meant to poke me became an interesting math problem to ponder. You might want to read the original question and the answers presented. The final question was, can a square be described in any rotational orientation (based on the 2D Cartesian plane) with just 1 equation?

The answer is a resounding YES.

Meet Roie, who proposed this solution:

maximum {|r cos(theta-theta_0)|,|r sin(theta-theta_0)|} = c

This is basically modified from the max-abs solution by Mike Anderson:

max(abs(x),abs(y)) = c

You move from Cartesian coordinates to polar coordinates. Once you’re in polar plane, you can rotate by changing one variable (the angle). I actually wrote something about converting between Cartesian and polar coordinates for the use of image rotations. I can’t believe I forgot about that…

Roie also gave sample (GNU Octave or MATLAB) code:

theta0 = 0.5;
x = ones(201,1) * (-10:0.1:10);
y = x’;
z = max(abs(sqrt(x.^2+y.^2) .* cos(atan(y./x)-theta0)),abs(sqrt(x.^2+y.^2) .* sin(atan(y./x)-theta0)));
contour(z)
axis square

Unfortunately, I am unable to verify that. Fortunately, Cees Meijer confirmed it for me. He introduced me to FreeMat, a free open source software that works like MATLAB. Unfortunately, I cannot install the Windows version because I need an x64 executable (I’m on Windows 7 64-bit), and FreeMat currently only has x86 version (32-bit).

Oh well, if it works, then I can finally do matrix multiplications in one line of code. So there, Will.

Answered: Can you describe a square with 1 equation?

First, I want to say how humbled I am by the people who read this blog. You are awesome.

You might want to read the original post where the question came from. So, can you describe a square with only 1 equation? 3 readers gave their opinions, and they are all correct (meaning they’re smarter than me). I will present their answers first, then present my engineer friend’s answer, and then mine (which is worthless, and didn’t work out the way I wanted).

The first answer was from Mike Anderson, who gave this:

max(abs(x),abs(y)) = c

max(abs(x),abs(y)) = c

That actually took me a while to understand. And is actually the more complicated answer. But it’s exactly the answer my friend was looking for, which is an upright square. We’ll assume the centre of the square to be the origin. The absolute function reduces the working Cartesian plane to just the first quadrant (if it works in the first quadrant, it works in the other quadrants). The maximum function ensures that either the x-value or y-value (or both) is equal to c (half the width of the square).

What if the absolute function is not in action? Then if -c < x < c, then y must be either -c or c (because of the maximum function). Therefore there are 2 horizontal parallel lines. Similarly vice versa, creating 2 vertical parallel lines. And there’s your square. This is brilliant.

The second answer was from Christopher Tay, who gave this:

|x| + |y| = C

which is the L1 norm.

L1 norm square

The norm of a matrix is the magnitude of the matrix. In this case, the matrix is actually a 2 dimensional vector. The pipe character | surrounding the x and y values mean we’re taking the absolute value.

This one is interesting. It means that the larger the value of x, the smaller y has to be to compensate, so that the sum of x and y is C. This see-sawing effect created a triangular shape for each quadrant. Which when formed together, becomes a square (tilt your head 45 degrees to see it better).

Then Chris McAloney came in with this:

abs(x) + abs(y) = c

This equation is equivalent to the L1 norm form. Chris also pointed out that the squares formed by the previous 2 equations differ from each other by a rotation of PI/4 (radians) or 45 degrees.

So there are 2 solutions! My engineer friend was shocked when I told him. I had to admit, I was gloating just a little when I told him my readers solved his problem…

One small point to note. The constant c in each equation is specific to each equation. As in if you supplied the same constant to each equation, the width of the squares formed are different. Let me illustrate:

Square comparison

The square formed by the max-abs way has a width of 2c.

The square formed by the L1 norm way has a width of sqrt(2)*c.

The engineer’s answer

So what’s my friend’s answer? He said the answer might anger some mathematicians. He also said the answer might demonstrate a fundamental difference between how engineers and mathematicians think. And his answer is…

x^10000 + y^10000 = 1

Or basically x and y to the power of a sufficiently large number. The result is not exactly a square, but it looks sufficiently like a square.

And that was his point. That engineers take “good enough” and practicality as priority. If a wooden beam is in the correct position, and is supporting the weight of the roof, who cares if it’s 1 nanometre off the intended position?

How did he come up with it? He was playing with Wolfram Alpha and was just dumping equations into it… To see what happens, start with

x^2 + y^2 = 1

That’s a circle with radius 1. Then increase the power to 10

x^10 + y^10 = 1

You’ll see a square with round edges. Actually x^100 + y^100 = 1 gives a nice square plot. To my friend, that’s a good enough square. He posed the question to me for an analytical answer, because even he knows his answer wasn’t exact.

And my (worthless excuse of an) answer?

I hit upon the idea of starting with a circle. Then morphing it somehow into a square. The idea came from a super equation that can describe a cube or sphere or some other 3D object. I can’t find it anymore… I saw the equation when I was doing research on the demoscene. You vary a parameter t, and you get different 3D objects. That’s neat.

So I started with this:

(r * sin(θ))^2 + (r * cos(θ))^2 = r^2

Yup, I used polar coordinates. I was thinking of somehow wrangling the sines and cosines with ceiling and floor and rounding functions. I was trying to force something like:

ceiling(cos(θ)) * (sin(θ))^2 [<- NOOO, THIS IS WRONG]

to work… That was for y. I had a correspondingly elaborate term for x.

Then it dawned on me.

How am I going to draw a square in the polar coordinate plane when I basically only had theta to work with? Everything will be circular.

I tore my math working off my writing pad and threw it down the rubbish chute. I might also have sworn vehemently. Can’t remember…

So there you have it, 2 equations to describing a square. And 1 equation that creates a result that looks like a square, which for most purposes and intents may be regarded as a square.

Then my friend came in with the last word:

“For bonus points, can you use some trig functions to tilt it back so that the equation can have any angle?”

We have 1 upright square, and 1 square that’s tilted 45 degrees. My friend wanted to know if there’s an equation that creates a square in any rotational orientation. I don’t believe there’s one, so please don’t bother to try. It’ll just waste your brain cells. But you’re welcome to try it as an intellectual exercise.

Me? I need to get another writing pad…

Quiz: Can you describe a square with 1 equation?

I was hanging out with my friends, and somehow the topics wandered into something that prompted a mischievous grin from one of the guys.

“Eh, I have a maths problem for you.” He could probably blind someone with that playful twinkle in his eye.

Can you describe a square with just 1 equation?

“What?” My mind was already racing to solve the problem.

“Just take it as a square in the 2D Cartesian plane. The centre of the square will be at the origin (0,0) to simplify the equation.” He seemed delighted to have stumped me.

I asked if there were any boundary conditions. No. Was the equation elegant? As in fairly simple when looked at, no mangling of terms. He gave it a second, and… yes, it was elegant.

Then he said the most important piece of information so far. “The answer might anger mathematicians. It is probably one of the fundamental differences between an engineer and a mathematician.”

Our conversations left this topic. But my brain was subconsciously still working on it. Then I blurted, “I think I solved it.” I described my way of thinking, and he said that’s along the correct line of thought. Then he just gave me the answer.

Yes, I agree. The answer will probably ruffle the feathers of the math purists.

As of this writing, I have yet to come up with the analytical formula of an equation to describe a square. I will post my findings, and my friend’s answer in a week’s time. You are encouraged to come up with your own solution. Post in the comments. Better yet, write about it in your blog. Tell your friends about it. Show them how awesomely clever you are.

Can you describe a square with 1 equation?

Bonus fun: My friend tried to explain a bit more. “There’s only one equal sign.” I think he was trying to insult me or something…

Update: Find out the answer.

Squares, hexagons and distance

Most traditional board games use squares to segregate space.

Square terrain

Space is divided evenly. Lines are easy to draw. Everything is structured. Bliss.

Except that when you need to move to a diagonal square, you need to move 2 squares instead of √2 squares. Wait, a non-integer movement? That cannot be tracked!

Dungeons & Dragons 4th Edition (a tabletop RPG with physical positional tracking) state that a diagonal square movement costs the same as a perpendicular square movement. Meaning you just move 1 square to reach that diagonal square. This also has its problems.

For example, there’s a concept of push in D&D, where as long as the target being pushed is moved further away, it counts as a push. Bringing us to this situation:

Perpendicular push movement

I talked about this briefly on my other blog, but didn’t go into the math details. So the blue dot is you, the red dot is the enemy, and the brown dot is where the enemy is pushed to.

The distance between you and the enemy is (do the Pythagoras thing) 2√2 (approx 2.8284). The distance between you and the final position of the enemy is √10 (approx 3.1623). Sure √10 is greater than 2√2, so mathematically speaking, the enemy is moving away from you. But common sense is telling me otherwise, because the direction of the push emanates from you.

Anyway, to combat the shortcomings of the square terrain, there’s the hexagonal terrain.

Hexagonal terrain

Under this division of space, all adjacent spots are equidistant to your position. Well, it still has its problems. You still need 2 hexagons of movement to reach the first hexagon directly above you.

Hexagonal movement

So what’s the actual cost of movement? Let’s look at this extracted diagram:

Hexagonal movement calculation

Let h be half of the actual distance. Doing the Pythagoras thing again, we have
1^2 = h^2 + (1/2)^2
=> 1 = h^2 + 1/4
=> h^2 = 3/4
=> h = √3/2 (h is positive)

Therefore, the actual distance is 2h which is √3 (approx 1.7321). Not quite 2 hexagons, is it?

This is part of the reason why, when games are created on computers, that these limitations disappear. Because computers can do the distance calculations and tracking. You can move in any direction, for any amount of units of movement, as long as you do not hit anything.

And that is called collision detection.

The math behind 360 degree fisheye to landscape conversion

I wrote an article to convert a 360 degree fisheye image to a landscape view some time ago. I also realised I didn’t explain the math very much, mainly because I thought it’s fairly obvious. On hindsight, it doesn’t seem obvious. My apologies.

Commenter Eric pointed out a math technique called linear fractional transformation. It’s basically a function that can map lines and circles to lines or circles.

In theory, it seems applicable to our problem. When I tried working out the solution, I failed. 2 possible reasons: my math sucks, or the technique isn’t applicable to the problem. It’s probably the former…

My postulate is that, the fisheye-landscape conversion has an edge condition that maps a line to a point. Specifically, the bottom of the destination image maps to one point, the centre of the source image. Thus linear fractional transformation is probably not suitable. I’m happy to hear from you if you’ve found a way to make it work.

Let’s bring up the explanation diagram I had from before:

Fisheye to landscape explanation diagram

I have assumed a source image that’s square (width equals height) and its width has an even number of pixels. With this, let the given image be of width and height of 2l pixels. The idea is to construct an image with width of 4l pixels and height of l pixels, which is the landscape view of the source fisheye image.

The dimensions of the destination image was arbitrarily chosen. I just find that a height of l pixels (or half the height of the source image) to be convenient. The centre of the source image is assumed to be the centre of the small “planet”. This means the pixels along the horizontal and vertical bisectors of the source image will not be distorted (much) by the conversion.

Oh right, I haven’t told you about the exacts of the conversion math…

You should know that only the pixels in the inscribed circle of the source image would be in the destination image. This is due to the “uncurling” effect. The pixels not in the inscribed circle would be out of range in the destination image.

So, imagine the source image as a representation of the Cartesian plane. The centre of the image is the origin. The point A, is the eastern point of the inscribed circle. Points B, C and D are the northern, western and southern points of the inscribed circle respectively.

I’m using the Cartesian plane because the Cartesian quadrants make the math easier. Circles mean sines and cosines, so I’d rather work with angles in the typical form than do all the funny angle modifications. I’m not masochistic, you know…

What you should understand now is this: the pixels along the top of the destination image come from the pixels along the circumference of the inscribed circle on the source image.

We’ll be iterating over the destination image (remember my messy index preference?) Let’s start at the top left corner. We’ll be iterating 4l pixels to the top right corner. This is visualised as going clockwise on the source image from point A, to D, to C, to B and back to A.

So, 4l pixels is equivalent to 2 PI radians?

At the top left corner, we start with 2 PI radians (so to speak). As we iterate to the top right corner, the angle reduces to 0. Thus this formula:

theta = (4l – x)/(4l) * 2PI
where x is the Cartesian x axis.

Generally speaking, iterating from the left to right on the destination image is equivalent to going clockwise on the source image.

Now, as we iterate from the top left of the destination image to the bottom left, it’s equivalent to going from point A on the source image to the centre of the source image. Thus:

radius = l – y
where y is the Cartesian y axis.

Generally speaking, iterating from the top to bottom of the destination image is equivalent to going from edge of source image to centre of source image.

And once you understand that, the rest is just coding. I merged the code for converting Cartesian to raster coordinates together (more details here with code here). The code was deliberately left unoptimised so it’s easier to read.

For example,

theta = 2.0 * Math.PI * (double)(4.0 * l - j) / (double)(4.0 * l);

could be

theta = Math.PI * (double)(4.0 * l - j) / (double)(2.0 * l);

to save on operations. But the 2.0 * Math.PI makes it more meaningful.

The if condition

if (x >= 0 && x < (2 * l) && y >= 0 && y < (2 * l))

could have had the (2 * l) part assigned to a variable to avoid multiplication multiple times. You're welcome to use a variable perhaps named iSourceWidth for example.

And that's all I have. I hope you have fun with the code.

“The numbers don’t tally!” – a serial counting problem

Boy in shock

How many numbers are there from 7 to 26 (both inclusive)? How do you calculate your age?

Both solutions require you to count from one number to another. And if you’re quick-witted, you might have deduced that a subtraction shortens the process considerably. However, be careful of how you subtract.

For the first question, if you take 26 – 7, you get 19. But there are 20 numbers:
7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26

For the second question, you simply take the current year minus the year you were born in (let’s leave the exact months out of this). So I’m born in 1977, and as of this writing, it’s the year 2009, so I’m 2009 – 1977 = 32 years old. Which is correct. Wait, did I just tell you my age?

The army equipment

I’m going to relate to you an incident which happened when I was enlisted in the army. No it’s not a war story. It is, surprisingly, a counting problem.

I was a lowly private then, assigned to the store to help. On a particular day, the lance corporal I was helping was making sure of equipment stock. Basically ensuring that the stock number of a piece of equipment on paper, physically reflects the stock number of that piece of equipment in the store.

We took down all the (communications, I think) equipment down from the racks, and placed them neatly on the floor. Since the racks were now empty, we might as well clean them (army efficiency…). After that, the lance corporal and I started to count the equipment on hand.

It was a while later, and I was counting my part of the equipment, when the lance corporal swore. He was pacing, and gesticulating, and his face was contorting in expressions of worry I’ve never seen before.

“You ‘A’ level right? The numbers don’t tally! Tell me what’s wrong!” *

The lance corporal had counted the pieces of equipment. It tallied with what was recorded on paper. Then he sorted them by serial number (there was one on each piece of equipment). Then he matched them with the serial numbers recorded in the system. It was correct too.

And because the serial numbers were in increasing order, differing by 1, he did the subtraction trick. And found to his horror of horrors that it wasn’t the number he counted! Hence his panic.

Let’s say the serial numbers were:
SERIAL0007
SERIAL0008
SERIAL0009

SERIAL0024
SERIAL0025
SERIAL0026

The records said there were 20 pieces of this equipment on hand. But the subtraction gave him:
26 – 7 = 19!

What went wrong?

The problem was, the lance corporal didn’t count the equipment with serial number SERIAL0007.

The age problem

Let’s look at the age problem again. Say there’s a baby born in the year 2000. Which year would the baby be 1 year old? 2001. Which year would the baby be 5 years old? 2005.

How is the age calculated? Take the current year minus the birth year.

It works, because the birth year is not counted.

Back to the serial numbers

In the case of the serial numbers, each serial number had to be counted in.

Serial numbers SERIAL0007 and SERIAL0008 means there were 2 pieces of equipment, even though
8 – 7 = 1

Thus, the number of pieces of equipment for serial numbers SERIAL0007 through to SERIAL0026 should be 26 – 7 (+ 1) = 20

Conclusion

A series of numbers is easy to count the number of its members. Just use subtraction.

Just be careful to note whether the start of the series have to be counted.

=====
* In Singapore, ‘A’ level refers to the GCE ‘A’ levels, commonly taken by students at around 18 years old. If one passes this, one can proceed to the university (generally speaking). And in Singapore, having a degree means a lot.

And young men with an ‘A’ level certificate entering the army may sometimes be viewed or referred to with a slight derogatory attitude, albeit lighthearted and with a fun undertone. And with their status sometimes pronounced as “air level”.

[image by Izmabel]

The monkey and negative number of coconuts

Coconut trees

There’s this math puzzle that I recently heard from my friend. Here it goes:

The puzzle

In the not so distant past, there was this small island. And there’s this monkey… what? Yes, it’s alone. Ok, fine, he’s alone. Yes, poor thing.

So, on this island, there were many many many coconut trees. And each of them bore enough fruits to collectively and breath-of-a-hair-barely escaping the sinking of the entire island. These palms were fertile, I tell ya.

And there were them these pirates, ya know. Arrr! And they were five in all. Ok, you can stop arrr-ing now. Huh? What were these pirates doing on the island? Uh, they got stranded? How do I know? (*whispering to myself* the filthy swashbuckling buccaneers…)

Anyway, they saw them these coconuts just hanging there, and they thought they were in coconut heaven. They proceeded to gather all the coconuts they could get their hands on. Hmm? They might have some food on them. Uh, maybe they had cravings for coconut?

The monkey saw what they were doing, and went to help them. Finally, at sundown, they… what? It took maybe a day… Yes, that means the pirates arrr-ived in the morning. Alright, let me continue the story, will ya?

So at sundown, they were exhausted, and decided to divide the coconuts the next morning. And they went to bed. Or sand. Or whatever they used as makeshift beds.

During the night, one of the pirates woke up, fearing the others would betray him. And so he started dividing the pile of coconuts into 5. While he’s busy counting and dividing, the monkey came to the pile, took a coconut, opened it up and started eating. The fearful pirate, afraid of startling the monkey and making more noise, just let the monkey be. It turned out well, for he divided the pile evenly into 5. And then hid his share of the coconuts. And he went to sleep.

And another pirate, fearing the same thing, woke up just after the first pirate went to sleep. And he divided the rest of the coconuts into 5. And the monkey also took a coconut and ate it, bemused at the stealth tactics employed by the counting pirate. This second pirate was satisfied that he counted correctly and that he divided the pile evenly into 5, so he let the monkey go. Besides, he was busy hiding the coconuts and trying to be quiet.

A third pirate did the same thing, dividing the remaining pile of coconuts into 5. And the monkey did the same thing, eating a coconut while the pirate was having trouble because he didn’t have enough fingers on his left hand to help him.

And a fourth pirate did the same thing. And the fifth too.

At each quiet division of coconuts, the pile was divided evenly. And the monkey ate a coconut at each division. So, how many… Yes, the monkey ate a total of 5 coconuts. You’re so clever. So, how many coconuts were there in the original pile?

The solution (sort of…)

I am going to work backwards.

Let y be the number of coconuts left over.
Let x be the original number of coconuts.
Note that x and y must be integers.

At 5th pirate division:
He hid his pile, so we add his pile back.
What’s left would be 4 parts for the rest, so we get 5y/4 to get all the pirates’ share.
Oh yeah, we need to get the monkey to regurgitate his coconut.
Ok, maybe not…

So before the 5th pirate divided, we had
5y/4 + 1
= (5y + 4)/4

At 4th pirate division:
It’s 4 parts for the other pirates, so we do the 5/4 multiple again to get
5( (5y + 4)/4 )/4
And we add 1 from the monkey to get
5( (5y + 4)/4 )/4 + 1
= (25y + 20)/16 + 1
= (25y + 36)/16

Note the recursive nature.

At 3rd pirate division:
5( (25y + 36)/16 )/4 + 1
= (125y + 180)/64 + 1
= (125y + 244)/64

At 2nd pirate division:
5( (125y + 244)/64 )/4 + 1
= (625y + 1220)/256 + 1
= (625y + 1476)/256

At 1st pirate division:
5( (625y + 1476)/256 )/4 + 1
= (3125y + 7380)/1024 + 1
= (3125y + 8404)/1024

And so we have
(3125y + 8404)/1024 = x
=> 1024x = 3125y + 8404

Now, my first thoughts had something to do with the Chinese Remainder Theorem or the GCD or something. And I searched for the solution, because I have no idea how to start. And I came upon Diophantine equations.

And I have absolutely no idea how to solve the equation.

Now my friend did tell me that 3121 was a solution for the number of original coconuts, which would mean 1020 coconuts were left over. And something about modular arithmetic.

What is more interesting, is that he told me -4 is also a solution. I plugged it into the equation, and lo and behold! There were -4 coconuts left over.

Wait, what? So there were -4 coconuts originally, and after all the sneaking and counting of the pirates, and the monkey eating it’s, ok, his, (presumably) non-existent -1 coconut, we have -4 coconuts left over?

The only reason why that solution was confounding us, ok, me, no wait, you, arrr, whatever, is that an assumption was flawed. We can’t have negative numbers of coconuts. Not in this reality dimension anyway. Arrr.

But it’s interesting. -4 is a stable solution, in chaos theory parlance. I mean parrrlance. Arrr.

Final thoughts: Why would each pirate fear that the others would betray him, but was honest enough to divide the coconuts evenly? And how would the first pirate divide 3121 coconuts into 5 while keeping quiet (that’s a lot of coconuts)? And keeping his head straight? And keeping the monkey quiet?

This is why, sometimes, just because you can solve a math problem, doesn’t mean you should. Because it might not make sense in the first place.

P.S. This was inspired by my friend who told me about the puzzle, and the International Talk Like A Pirate Day. Arrr.

[image by akurtz]