How to find time complexity of an algorithm
You add up how many machine instructions it will execute as a function of the size of its input, and then simplify the expression to the largest (when N is very large) term and can include any simplifying constant factor.
For example, lets see how we simplify 2N + 2
machine instructions to describe this as just O(N)
.
Why do we remove the two 2
s ?
We are interested in the performance of the algorithm as N becomes large.
Consider the two terms 2N and 2.
What is the relative influence of these two terms as N becomes large? Suppose N is a million.
Then the first term is 2 million and the second term is only 2.
For this reason, we drop all but the largest terms for large N.
So, now we have gone from 2N + 2
to 2N
.
Traditionally, we are only interested in performance up to constant factors.
This means that we don't really care if there is some constant multiple of difference in performance when N is large. The unit of 2N is not well-defined in the first place anyway. So we can multiply or divide by a constant factor to get to the simplest expression.
So 2N
becomes just N
.
Since I was sure a similar form solution would exist for that variable t
case - I extended the solution given in the link.
Starting from the equation in the link:
Which we can write as
Where b = B/(2A)
and c = C/A
.
Then transforming u = t + b
we get
Where k = c - b^2
Now we can use the integral identity from the link to obtain:
So, in summary, the required steps are:
- Calculate A,B,C as in the original equation.
- Calculate
b = B/(2A)
and c = C/A
- Calculate
u = t + b
and k = c -b^2
- Plug these values into the equation above.
Best Answer
Ivan Kuckir's DeCasteljau is a brute force, but works in many cases. The problem with it is the count of iterations. The actual shape and the distance between coordinates affect to the precision of the result. And to find a precise enough answer, you have to iterate tens of times, may be more. And it may fail if there are sharp turns in curve.
Better solution is to find first derivative roots, as is described on the excellent site http://processingjs.nihongoresources.com/bezierinfo/. Please read the section Finding the extremities of the curves.
The link above has the algorithm for both quadratic and cubic curves.
The asker of question is interested in quadratic curves, so the rest of this answer may be irrelevant, because I provide codes for calculating extremities of Cubic curves.
Below are three Javascript codes of which the first (CODE 1) is the one I suggest to use.
** CODE 1 **
After testing processingjs and Raphael's solutions I find they had some restrictions and/or bugs. Then more search and found Bonsai and it's bounding box function, which is based on NISHIO Hirokazu's Python script. Both have a downside where double equality is tested using
==
. When I changed these to numerically robust comparisons, then script succeeds 100% right in all cases. I tested the script with thousands of random paths and also with all collinear cases and all succeeded:Various cubic curves
Random cubic curves
Collinear cubic curves
The code is as follows. Usually left, right, top and bottom values are the all needed, but in some cases it's fine to know the coordinates of local extreme points and corresponding t values. So I added there two variables:
tvalues
andpoints
. Remove code regarding them and you have fast and stable bounding box calculation function.CODE 2 (which fails in collinear cases):
I translated the code from http://processingjs.nihongoresources.com/bezierinfo/sketchsource.php?sketch=tightBoundsCubicBezier to Javascript. The code works fine in normal cases, but not in collinear cases where all points lie on the same line.
For reference, here is the Javascript code.
CODE 3 (works in most cases):
To handle also collinear cases, I found Raphael's solution, which is based on the same first derivative method as the CODE 2. I added also a return value
dots
, which has the extrema points, because always it's not enough to know bounding boxes min and max coordinates, but we want to know the exact extrema coordinates.EDIT: found another bug. Fails eg. in 532,333,117,305,28,93,265,42 and also many other cases.
The code is here: