Placement of "good" control points in Bezier curves

I've been working on this problem for awhile now, and haven't been able to come up with a good solution thusfar.

The problem: I have an ordered list of three (or more) 2D points, and I want to stroke through these with a cubic Bezier curve, in such a way that it "looks good." The "looks good" part is pretty simple: I just want the wedge at the second point smoothed out (so, for example, the curve doesn't double-back on itself). So given three points, where should one place the two control points that would surround the second point in the triplet when drawing the curve.

My solution so far is as follows, but is incomplete. The idea might also help communicate the look that I'm after.

Given three points, (x1,y1), (x2,y2), (x3,y3). Take the circle inscribed by each triplet of points (if they are collinear, we just draw a straight line between them and move on). Take the line tangent to this circle at point (x2,y2) -- we will place the control points that surround (x2,y2) on this tangent line.

It's the last part that I'm stuck on. The problem I'm having is finding a way to place the two control points on this tangent line -- I have a good enough heuristic on how far from (x2,y2) on this line they should be, but of course, there are two points on this line that are that distance away. If we compute the one in the "wrong" direction, the curve loops around 开发者_如何学Con itself.

To find the center of the circle described by the three points (if any of the points have the same x value, simply reorder the points in the calculation below):

double ma = (point2.y - point1.y) / (point2.x - point1.x);
double mb = (point3.y - point2.y) / (point3.x - point2.x);
CGPoint c; // Center of a circle passing through all three points.
c.x = (((ma * mb * (point1.y - point3.y)) + (mb * (point1.x + point2.x)) - (ma * (point2.x + point3.x))) / (2 * (mb - ma)));
c.y = (((-1 / ma) * (c.x - ((point1.x + point2.x) / 2))) + ((point1.y + point2.y) / 2));

Then, to find the points on the tangent line, in this case, finding the control point for the curve going from point2 to point3:

double d = ...; // distance we want the point. Based on the distance between
                // point2 and point3.
// mc: Slope of the line perpendicular to the line between
// point2 and c.
double mc = - (c.x - point2.x) / (c.y - point2.y);
CGPoint tp; // point on the tangent line
double c = point2.y - mc * point2.x; // c == y intercept
tp.x = ???; // can't figure this out, the question is whether it should be
            // less than point2.x, or greater than?
tp.y = mc * tp.x + c;
// then, compute a point cp that is distance d from point2 going in the direction
// of tp.

---

It sounds like you might need to figure out the direction the curve is going, in order to set the tangent points so that it won't double back on itself. From what I understand, it would be simply finding out the direction from (x1, y1) to (x2, y2), and then travelling on the tangent line your heuristic distance in the direction closest to the (x1, y1) -> (x2, y2) direction, and plopping the tangent point there.

---

If you're really confident that you have a good way of choosing how far along the tangent line your points should be, and you only need to decide which side to put each one on, then I would suggest that you look once again at that circle to which the line is tangent. You've got z1,z2,z3 in that order on the circle; imagine going around the circle from z2 towards z1, but go along the tangent line instead; that's which side the control point "before z2" should be; the control point "after z2" should be on the other side.

Note that this guarantees always to put the two control points on opposite sides of z2, which is important. (Also: you probably want them to be the same distance from z2, because otherwise you'll get a discontinuity at z2 in, er, the second derivative of your curve, which is likely to look a bit suboptimal.) I bet there will still be pathological cases.

If you don't mind a fair bit of code complexity, there's a sophisticated and very effective algorithm for exactly your problem (and more) in Don Knuth's METAFONT program (whose main purpose is drawing fonts). The algorithm is due to John Hobby. You can find a detailed explanation, and working code, in METAFONT or, perhaps better, the closely related METAPOST (which generates PostScript output instead of huge bitmaps).

Pointing you at it is a bit tricky, though, because METAFONT and METAPOST are "literate programs", which means that their source code and documentation consist of a kind of hybrid of Pascal code (for METAFONT) or C code (for METAPOST) and TeX markup. There are programs that will turn this into a beautifully typeset document, but so far as I know no one has put the result on the web anywhere. So here's a link to the source code, which you may or may not find entirely incomprehensible: http://foundry.supelec.fr/gf/project/metapost/scmsvn/?action=browse&path=%2Ftrunk%2Fsource%2Ftexk%2Fweb2c%2Fmplibdir%2Fmp.w&view=markup -- in which you should search for "Choosing control points".

(The beautifully-typeset document for METAFONT is available as a properly bound book under the title "METAFONT: the program". But it costs actual money, and the code is in Pascal.)