“好”的放置贝塞尔曲线中的控制点
我已经研究这个问题有一段时间了，到目前为止还没有找到一个好的解决方案。
问题：我有一个由三个（或更多）2D 点组成的有序列表，我想用三次贝塞尔曲线来描画这些点，以使其“看起来不错”的方式。 “看起来不错”部分非常简单：我只希望第二个点处的楔形变得平滑（因此，例如，曲线不会自行折回）。因此，给定三个点，在绘制曲线时，应该将围绕三元组中第二个点的两个控制点放置在哪里。
到目前为止我的解决方案如下，但并不完整。这个想法也可能有助于传达我所追求的外观。
给定三个点：(x1,y1)、(x2,y2)、(x3,y3)。取每个三元组点内切的圆（如果它们共线，我们只需在它们之间画一条直线并继续前进）。取与该圆在点 (x2,y2) 相切的线——我们将围绕 (x2,y2) 的控制点放置在这条切线上。
这是我坚持的最后一部分。我遇到的问题是找到一种方法将两个控制点放置在这条切线上 - 我对它们在这条线上距离 (x2,y2) 应该有多远有足够好的启发，但是当然，有这条线上有两个距离相同的点。如果我们以“错误”的方向计算，曲线就会自行循环。
找到这三个点所描述的圆的中心（如果任何点具有相同的 x 值，只需在下面的计算中重新排序点）：
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));
然后，找到切线上的点，在本例中，找到从 point2 到 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.
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 on 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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
听起来您可能需要弄清楚曲线的前进方向，以便设置切点，使其不会自身折回。据我了解，这只是找出从
(x1, y1)到(x2, y2)的方向，然后沿着你的启发式距离的切线行进在最接近(x1, y1) 的方向 -> (x2, y2)方向，并在那里放置切点。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.如果您确实有信心有一个好方法来选择点沿切线的距离，并且您只需要决定将每个点放在哪一侧，那么我建议您再看一遍与该线相切的圆。圆上有 z1、z2、z3 的顺序；想象一下从 z2 到 z1 绕圆，但沿着切线走；这就是控制点“z2 之前”应该在哪一侧；控制点“z2 之后”应该在另一侧。
请注意，这保证始终将两个控制点放在 z2 的相对侧，这一点很重要。 （另外：你可能希望它们与 z2 的距离相同，因为否则你会在 z2 处得到不连续性，呃，你的曲线的二阶导数，这可能看起来有点次优。）我打赌会仍属于病理病例。
如果您不介意代码的复杂性，Don Knuth 的 METAFONT 程序（其主要目的是绘制字体）中有一个复杂且非常有效的算法可以完全解决您的问题（以及更多问题）。该算法由约翰·霍比 (John Hobby) 提出。您可以在 METAFONT 中找到详细的解释和工作代码，或者更好的是，密切相关的 METAPOST（它生成 PostScript 输出而不是巨大的位图）。
不过，指出这一点有点棘手，因为 METAFONT 和 METAPOST 是“文学程序”，这意味着它们的源代码和文档由 Pascal 代码（对于 METAFONT）或 C 代码（对于 METAPOST）和TeX 标记。有一些程序可以将其转换为精美的排版文档，但据我所知，没有人将结果发布到网络上的任何地方。因此，这里是源代码的链接，您可能会或可能不会觉得完全无法理解： http://foundry.supelec.fr/gf/project/metapost/scmsvn/?action=browse&path=% 2Ftrunk%2Fsource%2Ftexk%2Fweb2c%2Fmplibdir%2Fmp.w&view=markup——您应该在其中搜索“选择控制点”。
（排版精美的 METAFONT 文档可以作为一本装订得当的书获得，标题为“METAFONT：程序”。但它需要实际花钱，而且代码是 Pascal 语言。）
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.)