常见的算法问题

Question

假设我们有一些网格(参见CorelDraw的图解图片,它在"网格填充"工具中使用相同的技术).

替代文字http://www.sonic.net/mnitepub/pccafe/reviews/coreldraw9/meshfill.jpg

显然,这种网格由一组点表示,它们之间的线实际上是使用这组点确定的(可能以某种方式插值).该仪器还具有增加网格分辨率的按钮.

我的问题如下 - 如何计算这类事情？假设我有一些实际上代表网格的点(为了简单起见,我们甚至假设,"边界"上的点是静态的,不能移动).我想增加网格分辨率,例如,增加4倍(以便实际变成网格点的数量4 * initial_points_count).

如果我拥有的唯一数据是初始点矩阵,我应该如何计算新点的位置？

最快(甚至近似)的方法适合我,但我不知道在哪里搜索或如何开发这种算法.

谢谢.

Answer 1

我首先通过插值在所有线上添加中间点（图中的曲线很可能是某种B\xc3\xa9zier 曲线，所以我会这样对它们进行插值，或者按照 Mau 建议使用双线插值）并放置新的点介于旧点之间，分辨率提高了 3 倍。然后，我会在这些新点之间进行插值（如果精度是关键，则两种方式）并在交叉点（或中间）放置一个新点。请参阅下面的“插图”。

\n\n

Initial state  =>  Interpolate  =>  Place points  =>  Interpolate => Final state\n  x       x         x-------x        x   x   x         x   x   x      x   x   x\n                    |       |                              |    \n                    |       |        x       x         x---+---x      x   x   x\n                    |       |                              |\n  x       x         x-------x        x   x   x         x   x   x      x   x   x\n

\n