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 have been tasked with creating a C++ program (with GDI+ for graphics) that takes a set of user defined points and creates polynomial curve through them. For extra credit, I have to support a parametric polynomial for any number of points. The thing is.. he didn't explain what a parametric polynomial is! So I need some help understanding how to figure one out based on a set of points.. in layman's terms, please. I've taken Calc 1, so I'm not that up-to-par on my calculus skills, just so you know what level I'm at.

Any help would be appreciated.

Thanks!

share|improve this question
    
Do the points represent an arbitrary curve, or a function? I.e., would a curve drawn through your points satisfy a vertical-line test? –  J. M. Oct 4 '10 at 3:50
    
Here's the situation: The user is presented with a screen of arbitrary height and width. The user can place as many points on the screen as he wishes. There is an option to draw a line from point to point to point.. and an option to draw a polynomial through all of the points. –  trunksbomb Oct 4 '10 at 3:56
add comment

3 Answers 3

It's not clear to me whether this is just an exercise for its own sake, or meant to serve some real purpose. If is is meant to be like a drawing program where you want a nice curve that "follows" the points that the user selects, the interpolating polynomial curve is probably not a very good idea, since it will oscillate wildly when you have many points (and most likely go way outside of the screen). In such a situation, Bézier curves should be more useful.

share|improve this answer
    
agreed 100%. (extra chars.) –  Tom Stephens Oct 4 '10 at 15:27
    
It has to go through every point the user creates. As long as it does that, the curve doesn't have to be pretty. –  trunksbomb Oct 11 '10 at 18:32
add comment

As I mentioned in the answer to this question, parametric (cubic) splines which are represented as piecewise polynomials in each coordinate $(x,y)$ are the most useful choice, when one wants to draw a curve passing through points that do not necessarily represent a function. (The problem with Bézier is that it treats the input points as a convex hull; i.e. the curve is within the set of points but does not pass through them.)


spline vs. Bezier

Comparison of a parametric spline (red) and a Bézier curve (blue).


An interpolating polynomial is bad form as well for arbitrary point sets; the Runge phenomenon is one vivid example.

share|improve this answer
    
That's great and all, and your explanation on how to get the t value is fine. I just can't figure out the cubic curve.. as in, I can't find a simple algorithm that I can put into code. –  trunksbomb Oct 11 '10 at 4:23
    
Why not take a look at netlib.org/pppack ? –  J. M. Oct 11 '10 at 9:13
    
The thing is is that he threw us into this assignment without giving us any information. He just told us a "hint" that we need to find some values t for each point. So I really have no idea even how to come up with a basic polynomial, and all these explanations are pretty far above my head. –  trunksbomb Oct 11 '10 at 18:21
    
I have found this, which I think fits the "usual cubic spline" that you mention in the answer to that other question: ehow.com/how_5942053_determine-coefficients-cubic-spline.html I think that this is what I'm looking for, but it seems like it skips a few things. For example, where does the matrix A come from? And step 6 doesn't make any sense. –  trunksbomb Oct 11 '10 at 18:23
    
OH OH OH. I went to the library and checked out a book: "Interpolating Cubic Splines" and checked it out. I've got a polynomial function that graphs points that are in order according to x.. But there is one weird side effect, as seen here: yfrog.com/ncweirdpj Notice how it jumps erratically in the first interval.. I don't know what that is. I think it could be something in my code that I didn't do right. Hmm.. but this technique yields a polynomial that hits each point in order, which isn't what I need for full credit: I need a polynomial that goes through points in ANY order. –  trunksbomb Oct 11 '10 at 21:30
add comment

I suspect that by 'parameter' your professor means that your code should accept a number supplied by the user specifying how many data points they would like to input. Then your code should write a polynomial to fit that data.

It is fairly simple to write a unique $(n-1)$-degree polynomial given $n$ data points. Start here.

share|improve this answer
    
I've read over that a couple of times, along with the Polynomial Interpolation article. I'm just not grasping that concept. It seems a bit over my head right now. I could just be looking at it wrong, though. –  trunksbomb Oct 4 '10 at 2:43
    
alright, that is not the best article. Try this:math-linux.com/spip.php?article71. There is a nice example near the bottom of the page. –  Tom Stephens Oct 4 '10 at 2:52
add comment

Your Answer

 
discard

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