0
$\begingroup$

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!

  • 0
    Do the points represent an arbitrary curve, or a function? I.e., would a curve drawn through your points satisfy a *vertical-line test*?2010-10-04
  • 0
    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.2010-10-04

3 Answers 3

1

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.

  • 0
    agreed 100%. (extra chars.)2010-10-04
  • 0
    It has to go through every point the user creates. As long as it does that, the curve doesn't have to be pretty.2010-10-11
1

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.

  • 0
    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.2010-10-11
  • 0
    Why not take a look at http://www.netlib.org/pppack/ ?2010-10-11
  • 0
    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.2010-10-11
  • 0
    I have found this, which I think fits the "usual cubic spline" that you mention in the answer to that other question: http://www.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.2010-10-11
  • 0
    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: http://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.2010-10-11
0

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.

  • 0
    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.2010-10-04
  • 0
    alright, that is not the best article. Try this:http://www.math-linux.com/spip.php?article71. There is a nice example near the bottom of the page.2010-10-04