How to draw a curve that passes through three points?

Question

Hi, I'm trying to create a curve that passes through three given points in Java (I'm drawing the curves through a class that extends JPanel). How can I make it?

Thanks!

Answer 1

You should look into something like Catmull-Rom splines, which are basically curves that pass through a number of control points (in your case your three points).

Here is an example I found after a quick google: http://www.mvps.org/directx/articles/catmull/

Hope this helps :)

Answer 2

try a google search on bezier splines. this may be a 2D solution, but should be extensible to 3D if you need it.

basically, using the three points as parameters you can get an 2nd order polynomial that fits the three points .. AND its extensible, if you have N points you get an N-1 order polynomial that parametrically generates all the points from the 1st to the last, as you 'tune' a scalar parameter, oft denoted as 's'.

edit/added:

as was pointed out (credit CapBBeard!), Beziers don't actually hit the middle points. Lagrangian interpolation does actually hit the points, but gets ugly even more quickly as the number of points grows. (something like O(n) polynomial fractions each of order N)

Answer 3

A circle will pass through three points on a plane. This page explains the geometery: http://www.mathopenref.com/const3pointcircle.html

Answer 4

I have been reading all of your answers, and the best for what I'm looking for is the Catmull-Rom splines (thanks CapBBeard). Is there any library that implements them? or do I have to implement all of it?.

The Bezier curves have the problem that JustJuff says: The control points aren't in the curve. The first I tried were the QuadCurve2D class which are Bezier Curves (I think).

@John: That's a great idea. If I could find the circle that joins all the three points that would be perfect, but... How can I just draw the arc that joins the three points when I have just made that circle? Is there anyway to use the Arc2D class to do this? I have been looking for it too but I can find nothing.

Also, I have to say that I have to know the medium point to modify the curve by dragging it.

Thanks for all of your replies!.

Answer 5

This is what I'm looking for:

http://img27.imageshack.us/img27/3692/curve.png

Answer 6

I just spent some time getting this working in a robust way. There's a few supporting functions, followed by the thing that creates an Arc2D out of three points of a circle. For my purposes, I have a start and end points, as well as an intermediate 'mid' point (though it doesn't actually have to be in the middle---its purpose is to tell me which arc of the circle I want).

Here are direct links to the source:

org.six11.util.gui.shape.ShapeFactory

org.six11.util.pen.Functions

public static Pt getCircleCenter(Pt a, Pt b, Pt c) {
  double ax = a.getX();
  double ay = a.getY();
  double bx = b.getX();
  double by = b.getY();
  double cx = c.getX();
  double cy = c.getY();

  double A = bx - ax;
  double B = by - ay;
  double C = cx - ax;
  double D = cy - ay;

  double E = A * (ax + bx) + B * (ay + by);
  double F = C * (ax + cx) + D * (ay + cy);

  double G = 2 * (A * (cy - by) - B * (cx - bx));
  if (G == 0.0)
    return null; // a, b, c must be collinear

  double px = (D * E - B * F) / G;
  double py = (A * F - C * E) / G;
  return new Pt(px, py);
}

public static double makeAnglePositive(double angleDegrees) {
  double ret = angleDegrees;
  if (angleDegrees < 0) {
    ret = 360 + angleDegrees;
  }
  return ret;
}

public static double getNearestAnglePhase(double limitDegrees, double sourceDegrees, int dir) {
  double value = sourceDegrees;
  if (dir > 0) {
    while (value < limitDegrees) {
      value += 360.0;
    }
  } else if (dir < 0) {
    while (value > limitDegrees) {
      value -= 360.0;
    }
  }
  return value;
}

public static Arc2D makeArc(Pt s, Pt mid, Pt e) {
  Pt c = Functions.getCircleCenter(s, mid, e);
  double radius = c.distance(s);

  double startAngle = Functions.makeAnglePositive(Math.toDegrees(-Math
      .atan2(s.y - c.y, s.x - c.x)));
  double midAngle = Functions.makeAnglePositive(Math.toDegrees(-Math.atan2(mid.y - c.y, mid.x
      - c.x)));
  double endAngle = Functions
      .makeAnglePositive(Math.toDegrees(-Math.atan2(e.y - c.y, e.x - c.x)));

  // Now compute the phase-adjusted angles begining from startAngle, moving positive and negative.
  double midDecreasing = Functions.getNearestAnglePhase(startAngle, midAngle, -1);
  double midIncreasing = Functions.getNearestAnglePhase(startAngle, midAngle, 1);
  double endDecreasing = Functions.getNearestAnglePhase(midDecreasing, endAngle, -1);
  double endIncreasing = Functions.getNearestAnglePhase(midIncreasing, endAngle, 1);

  // Each path from start -> mid -> end is technically, but one will wrap around the entire
  // circle, which isn't what we want. Pick the one that with the smaller angular change.
  double extent = 0;
  if (Math.abs(endDecreasing - startAngle) < Math.abs(endIncreasing - startAngle)) {
    extent = endDecreasing - startAngle;
  } else {
    extent = endIncreasing - startAngle;
  }

  return new Arc2D.Double(c.x - radius, c.y - radius, radius * 2, radius * 2, startAngle, extent,
      Arc2D.OPEN);
}