algorithm - 如何在分辨率增加时计算网格点的位置？

Question

假设我们有一些网格(参见来自 CorelDraw 的插图图片，它在“网格填充”工具中使用了相同的技术)。

_{(来源:sonic.net)}

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

我的问题如下 - 这类事情是如何计算的？假设我有一些点集实际上代表一个网格(对于简单的情况，我们甚至假设，点“边界”是静态的，不能移动。我想增加网格分辨率，例如，4 倍(这样网格点的数量实际上变成了 4 * initial_points_count).

如果我仅有的数据是初始点矩阵，我应该如何计算新点的位置？

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

谢谢。

Answer 1

对现有答案的评论:

在我看来，Mau 和 martient 的回答描述了一个用 polygon mesh 逼近已知形式的问题的解决方案。 (而且您没有已知的表格)。

Dave 提到的算法可以平滑任何形式，但不一定以预期的方式。

如果您查看您的回答，您会发现新点来自点之间的线性插值，如果这对您来说足够好，则所有解决方案都具有可比性(Dave 的除外)。

网格密度的这种增加不会使生成的网格看起来“更好”——更类似于原始形式。如果这还不够好，那么您首先必须决定您尝试用网格表示的实际形式/形状是什么(如果您可以扩展您的示例，它可能会更明显一些；这个工具是否只创建圆形网格或者它可以采用任何形状并“网状填充”它？)。

此外，您应该注意到您没有使用多边形网格，而是使用曲线网格(可能是 bezier )，这是某些答案不能直接适用于您的问题的另一个原因。

编辑:在更仔细地了解 corel 是如何做到这一点并假设您实际上知道曲线而不仅仅是点(!)之后:

• 你从一组曲线开始，在我看来你有水平和垂直曲线开始
• 如果你想增加分辨率(例如水平分辨率)，你可以取两条连续的垂直曲线并将它们通过的水平曲线的每一段在中点分开，从而创建一组定义新曲线的点；您还可以插入曲线通过点的角度

alt text http://img706.imageshack.us/img706/5693/path5818.png

以上(手绘)图片展示试图说明a) 添加以这种方式生成的新曲线(红色)。b) 添加线性插值折线(蓝色)，这更倾向于多边形网格方法(因此您可以判断这是否适合您)

注意:根据您准备网格的算法，将网格线视为曲线可能会或可能不会有任何好处(红色和蓝色解决方案之间的差异可能可以忽略不计)某些算法，对其他算法很重要)。如果算法只需要点，那么您还应该了解如何用点来近似贝塞尔曲线(通读 this 可能会有所帮助；尽管您不需要像素精度)。

为了获得最高精度/最佳结果，您应该首先增加曲线的密度，然后用线来近似它们。