Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I did search at Google and this website before asking this question, so sorry if this somehow has already been answered and I didn't notice. BTW I'm a humanities scholar and not a trained mathematician (probably if I were I wouldn't be asking this question) so sorry if anything I ask/assume is wrong and please kindly correct me if so.

I am working on a Python implementation of the Bezier merging algorithm in this paper: http://cg.cs.tsinghua.edu.cn/~shimin/pdf/cad%202001_merging.pdf and I have implemented the first constrained optimization method and now working on the second one. I realize that StackOverflow is recommended for questions about implementing maths algorithms but my question is about the underlying mathematics itself (and not how to implement it), so I'm asking here.

In the second constrained optimization method I have two ordinary (i.e. not "rational") Bezier curves $P$ and $Q$ (of degree $n$) and I need to find the squared area between the two curves, defined as:

$$ \int_0^1 (P(t)-Q(t))^2 dt $$

Now I hope I understand correctly that $ P(t)-Q(t) $ can be understood as yet another Bezier curve $D$ where the control points $D_i$ $(i=0,1,...,n)$ are simply equal to $ P_i - Q_i $.

I know that differentiating a Bezier curve (i.e. finding the hodograph) will give me another Bezier curve of one lesser degree. I hope I understand correctly that this also means that the integral of a Bezier curve will also be another Bezier curve? But here I have to do the integral of the square of a Bezier curve and am not sure how to do that. Do I understand correctly that what is in fact meant is the square of the Euclidean distance between corresponding points of $P$ and $Q$, i.e.

$$ \int_0^1 || P(t) - Q(t) || ^ 2 dt $$

because a Bezier curve involves vectors, but area is a scalar, right?

Now googling for "square area under a bezier curve" I found this: http://cagd.cs.byu.edu/~557/text/ch2.pdf which shows (under sec 2.15) that if $F$ (I changed the names to not conflict with my previous formulae) is an Bezier curve of degree $n$ defined by:

$$ F(t) = \sum_{i=0}^n F_i B_i^n (t) $$

where $B$ is the Bernstein basis function and $F_i$ are the control points, then the integral of $F$ is another Bezier curve $G$ of degree $n+1$ defined as:

$$ G(t) = \sum_{i=0}^{n+1} G_i B_i^{n+1} (t) $$

where $G_0$ is $0$ (or the origin point of whatever dimensional curve we have) and the other control points $G_i$ $(i=1,2,...,n+1)$ are found as:

$$ G_i = { \sum_{j=0}^{i-1} F_j \over n + 1 }$$

but now I have to integrate $G^2$ which I assume means $||G||^2$ and I wonder if there is an analytical way of doing so i.e. a generic formulation just like $G$ was defined in terms of $F$? If there is not, then what other way should I follow to find the integral?

Thanking you very much for your kindness and patience!

Shriramana Sharma.

share|improve this question

2 Answers 2

Well OK, I was quite surprised to not see any answers here, but I plowed on on my own account and found the following:

I was previously speaking about integrating $||G||^2$ where G is a Bezier curve of which $F$ is the derivative curve. However this is not what the paper I mentioned tells me to calculate. I am supposed to evaluate the function representing the distance between two Bezier curves, square it and then integrate it.

And if $P$ and $Q$ are two Bezier curves represented in Bernstein form, $P-Q$ can also be expressed in Bernstein form since the Bernstein basis polynomials are the same in both cases and only the coefficients thereof differ.

That is,

$$P(t) = \sum_{i=0}^n P_i B_i^n(t)$$

$$Q(t) = \sum_{i=0}^n Q_i B_i^n(t)$$

$$P(t) - Q(t) = \sum_{i=0}^n (P_i - Q_i)B_i^n(t)$$

(This assumes that both $P$ and $Q$ are of the same degree $n$, and if they are not, then the one of lesser degree should be elevated to the higher degree, and then the difference expressed in Bernstein form as above should be determined.

Now squaring $P(t)-Q(t)$ must mean squaring the magnitude of $P(t)-Q(t)$ and if we call $P(t)-Q(t)$ as $R(t)$ where $R_i = P_i - Q_i$ $(i=0,1...n)$.

$$||R||^2 = R_x(t)^2 + R_y(t)^2$$

(or if you are working in three dimensions then add an $R_z$ term too).

Now this is what I am supposed to integrate, and since

$$\int \left(f(t)+g(t) \right) dt = \int f(t) dt + \int g(t) dt$$

I have:

$$\int(||R(t)||^2)dt = \int \left ( R_x(t)^2 + R_y(t)^2 ) \right ) dt = \int R_x(t)^2 dt + \int R_y(t)^2 dt $$

Now both $R_x(t)^2$ and $R_y(t)^2$ are $2n$-th order polynomials in $t$ with real coefficients, and I can integrate that against $dt$ the usual algebraic way. (I found it very convenient to use SymPy for this.)

Now the paper called what I have thus obtained the "squared difference integral" and says that it represents the "squared area" between two Bezier curves. However, the value obtained by the above integration is not entirely in the units of the coordinate system (or powers thereof). To obtain the actual physical area delimited by the Bezier curves in the coordinate plane (or space), one has to bring in the arc length of the curves too, but how exactly, I am not sure (but it doesn't concern me for my present project).

share|improve this answer
    
I'm just guessing, but ... you might have received more answers if you had written the question more concisely. –  bubba Jan 6 '13 at 10:27

After suitable degree elevation, if necessary, $P(t)$ and $Q(t)$ are (parametric) polynomials of degree $n$, so $\Vert P(t) - Q(t) \Vert^2$ is a (normal real-valued) polynomial of degree $2n$, which can be integrated by standard techniques, as you discovered. If you need one, you can find an explicit formula for the integral using symbolic math software like Maple or Mathematica or Sage. If $n=3$, this wouldn't be too bad.

I would say that the term "squared area" is sloppy and confusing. What you are calculating is more properly called the least squares error between the two curves. The relationship to area is fuzzy, at best.

This is slightly off the subject, but, depending on your application, the least squares error might not be a suitable measure of the discrepancy between two curves. If curve $Q$ is formed simply by reparameterising curve $P$, for example, then they will have exactly the same shape, but the least-squares error will not be zero.

share|improve this answer
    
Thanks for your reply. I agree that this is not really a squared area, especially since it is not even in user coordinates. However, I am intrigued by your comment about reparametrising. Can you elaborate on that? Recently I came across another pair of curves which are visually the same but parametrically different. How could one detect that? (Or should I ask this as a separate question?) –  jamadagni Jan 6 '13 at 11:51
    
Regarding detection of curves with identical shape ... I would suggest measuring the distance between the two curves at some sample points. For cubic curves, 10 or 20 points is probably enough. I think it's quite difficult to do this rigorously/mathematically, so, if that's what you want, I suggest asking another question. –  bubba Jan 8 '13 at 8:22
    
Hi thanks for your reply. How do you advice I choose the sample points? I mean, should I solve the cubic equation to find t for a given x and then substitute it into the equation for y to determine the y, or is there a better method avoiding cuberoot? Thanks! –  jamadagni Jan 9 '13 at 17:26
1  
Take a sequence of points along one curve. They can be at equal parameter increments. At each of these points, calculate the distance to the other curve. You will have to do this numerically -- there is no closed-form solution. Take the maximum of these point-to-curve distances. This process is asymmetric, of course. If you want to make it symmetric, you can reverse the roles of the two curves, measure again, and use the maximum of these two distances. –  bubba Jan 10 '13 at 2:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.