0

我一直在研究这个问题一段时间，到目前为止还没有想出一个好的解决方案。

问题：我有一个包含三个（或更多）二维点的有序列表，我想用三次贝塞尔曲线遍历这些点，使其“看起来不错”。“看起来不错”的部分非常简单：我只想平滑第二点处的楔形（因此，例如，曲线本身不会双回）。因此，给定三个点，在绘制曲线时，应该将两个控制点放置在三元组中的第二个点周围。

到目前为止，我的解决方案如下，但不完整。这个想法也可能有助于传达我所追求的外观。

给定三个点，(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.
4

2 回答 2

0

如果你真的有信心有一个很好的方法来选择你的点应该沿着切线多远，并且你只需要决定将每个点放在哪一边，那么我建议你再看一次与直线相切的圆。您在圆圈上按顺序排列了 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: the program”。但它确实要花钱，而且代码是 Pascal 格式的。）

于 2011-02-06T02:21:24.190 回答
0

听起来您可能需要弄清楚曲线前进的方向，以便设置切点，使其不会自行加倍。据我了解，它只是找出从(x1, y1)到的方向(x2, y2)，然后在切线上以最接近该(x1, y1) -> (x2, y2)方向的方向行驶您的启发式距离，然后将切点放在那里。

于 2010-09-22T17:22:32.577 回答