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!

$\endgroup$
  • $\begingroup$ Do the points represent an arbitrary curve, or a function? I.e., would a curve drawn through your points satisfy a vertical-line test? $\endgroup$ – J. M. is a poor mathematician Oct 4 '10 at 3:50
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 4 '10 at 3:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ agreed 100%. (extra chars.) $\endgroup$ – Tom Stephens Oct 4 '10 at 15:27
  • $\begingroup$ It has to go through every point the user creates. As long as it does that, the curve doesn't have to be pretty. $\endgroup$ – trunksbomb Oct 11 '10 at 18:32
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 11 '10 at 4:23
  • $\begingroup$ Why not take a look at netlib.org/pppack ? $\endgroup$ – J. M. is a poor mathematician Oct 11 '10 at 9:13
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 11 '10 at 18:21
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 11 '10 at 18:23
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 11 '10 at 21:30
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – trunksbomb Oct 4 '10 at 2:43
  • $\begingroup$ 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. $\endgroup$ – Tom Stephens Oct 4 '10 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy