Curve interpolation/smoothing

4 replies [Last post]
gmiecznik
Offline
Joined: 2007-11-07

Hi

It appears to me that neither Java2D nor Java3D provides a method to interpolate or smooth a curve. This problem has already been brought up (http://forums.java.net/jive/thread.jspa?threadID=35085) but the suggested solution does not lead any obvious path.

The problem is very simple - given a set of (x,y) points, interpolate in between. For example,
this is done in MS Excel when you do a scatter plot with known x-y points.

Probably Bi-cubic splines are best suited here, but nowhere could I find any examples of how to do this interpolation. Suprisingly, there are tons of Bezzier curve or spline applets, but none of addresses this obvious problem.

If you know how to do it using the existing Java resources or 3rd partly software I would greatly appreciate it.

Thank you
Gregory Miecznik

vync79
Offline
Joined: 2006-10-24

Hi,

not sure this address your issue, but you may compute any interpolated points between 2 samples of your set using the Cubic Hermite spline (one-dimensional version of bi-cubic interpolation). So you may define a certain number of additional interpolation points between your samples and draw the interpolated graph by simply drawing lines between 2 consecutive interpolated points (or eventually more advanced curved or quadric path using the GeneralPath class and the Graphics2D drawing methods applying to the GeneralPath).

If you compute enough inperpolated points and use some anti-aliased drawing, you should come very close to what you need. (if I understand correctly your needs ;-) )

If you want the equations for cubic hermite splines, check this out:
http://en.wikipedia.org/wiki/Cubic_Hermite_spline

Cheers.

Vince

gmiecznik
Offline
Joined: 2007-11-07

Thank you Vince for the reference.

Yes, Hermite splines can be used for interpolation, but getting a nice "shape" is difficult.
Consider for example drawing a circle, using a coarse grid, and interpolating in between.

MS Excel interpolates really nicely even if you have 20 points across a circle spanning
an average screen size. Try doing that with Hermite Splines! MS probably uses Bezier curves or Kochanek-Bartlets splines, but the details how they chose the control points (for Bezier) or control
parameters (for Kochanek-Bartlets) is hidden from the user.

I will look into Gnuplot to see how they solve the interpolation problem for drawing curves.

Gregory

vync79
Offline
Joined: 2006-10-24

Hi Gregory,

I don't really understand why it would be difficult to get a nice shape ? Using any kind of spline interpolation, you are able to define any number of interpolated points between two points of your data. One can go as close as needed to the continuous drawing of the inperpolation spline (which has by definition a very nice shape)
So for example, in your case of 20 points across a circle spanning, one could eventually compute the position of one interpolated point every pixel, then add all these inperolated points into GeneralPath object, set the Graphics2D RenderingHints to anti-aliased drawing and call the Graphics2D.draw(GeneralPath object). This would results in a pixel perfect interpolation of your circle that was originally defined by only 20 points on a coarse grid.

One interpolated point every pixel is even too much to get a very nice interpolated shape. One point every 5 pixels for example would already produce a nice shape.

I am a developer in medical imaging software and we use spline interpolation all the time. When a user wants to draw a region of interest around some anatomical region, he basically defines between 5 to 10 points around the area of interest and we display a nice continuous spline interpolation between those user defined points using the kind of technics described above. Noone could tell the displayed shape is actually made of number of interpolated points linked by simple straight lines.

Not sure I am clear.

Cheers.

Vince.

gmiecznik
Offline
Joined: 2007-11-07

Hi Vince,

Yap, I will probably use splines, just I have not have time coding and thinking about it
too much. I hoped I could find a quick and easy way and came across a few examples for
Bezier curves. Only one reference proved valuable.

Would you have a straightforward reference to a spline code example does just that- meaning
it ingests coarse grid of variables (preferably in 3D) and returns an interpolated value
between two grid points as a function of free parameter t?

I found a nice example at http://www.ee.ucl.ac.uk/~mflanaga/java/CubicSpline.java,
but it does not handle parametric curves, only y=y(x).

Thank you
Gregory