2

我有一个 C++ 程序，它需要以下格式的输入文件：

X    Y    Z
1    1    .642
1.1  1    .482
1.2  1    .394
1.3  1    .420
1.4  1    .948

文本文件很长——大约 20,000 行左右。我现在需要将其读入我的 C++ 程序，以便对任何 (X,Y) 对进行 Z 查找。如果 (X,Y) 对与我的输入文件中的任何对不完全相同，我需要使用最接近的 X 和最接近的 Y 值。如果我有一个完整的矩阵而不仅仅是非零值，那么 X 和 Y 坐标将均匀分布。

我的问题是确定最快的方法来做到这一点。我想避免实际上通过向量搜索最接近的 X，然后通过向量搜索最接近的 Y。有没有办法在不循环和搜索的情况下完成此操作？某种哈希表可以用于查找值吗？

我是一个脚本专家和一个 c++ 新手，所以如果这看起来微不足道，我深表歉意。因此，作为参考，我需要快速的方法：

lookup(1.1,1)
    >>> .482

lookup(1.112, 1)
    >>> .482 // value corresponding to closest x and closest y

lookup(0,0)
    >>> .642 // value corresponding to closest x and closest y

如果我有完整的矩阵，这直接是可能的，例如：

    1.1  1.2  1.3  1.4  1.5
1.1
1.3
1.5      (Z values)
1.7
1.9

为了找到与 (1.5, 1.2) 相关的 Z 值，我可以简单地返回在索引 [1.5/(x_spacing), 1.2/(y_spacing)] 处找到的 Z 值。

当然，我还需要通过这个间距减去我的查找值，如果不存在确切的 (X,Y) 对，则四舍五入。然而，最重要的是，它允许我在不进行任何搜索的情况下获得适当的 Z 值。我想完成同样的事情，除了不占用巨大的完整矩阵所需的所有空间。这就是为什么文本文件只包含对应于非零 Z 值的对的原因。

您能提供的任何帮助将不胜感激。

4

1 回答 1

2

我建议将其存储在结构化树中。以四叉树为例。它将是稀疏存储以节省空间，并且搜索最近点也很容易。

C++ 中的四叉树教程在这里。

于 2013-03-13T00:13:57.927 回答