2

我在 C# 中有一个空间哈希类来检测 3D 数据。每个顶点位置都有一个空间散列并Vector3存储在Dictionary<float, Vector3>浮点数是我计算的实际空间散列中。我理解空间散列的方式是将散列排序到桶中，然后获取彼此处于阈值（例如 0.0001f）内的值。我所做的大多数研究都实现了桶排序，我无法弄清楚如何用Dictionary我拥有的来实现。

所以，我的问题是，我应该如何在这样的字典中获得类似的值？到目前为止，在我看来，我需要将哈希值排序到大小为 的桶中，threshold并以某种方式维护到Vector3. 我是否以完全错误的方式接近这个？比如说，有没有更适合这个特定用例的不同泛型？

4

4 回答 4

0

实现接口

IEqualityComparer<float>

处理模糊匹配并将其传递给 Dictionary 的构造函数

http://msdn.microsoft.com/en-us/library/ms132151.aspx http://msdn.microsoft.com/en-us/library/ms132072.aspx

于 2013-03-27T16:45:20.043 回答
0

如果您想避免麻烦，请重新考虑使用空间哈希。虽然绝对可以实现，但 3D 散列函数非常复杂（如果你想要一个完美的散列，那就是）并且可以很容易地被一些智能的“足够接近”的函数替换。

所以，选择权在你：

完美哈希

或者

巧妙使用 'Close-Enough' 函数（取自 OpenGL SuperBible 的源代码，请查找 'm3dCloseEnough'）

于 2013-03-27T16:54:57.717 回答
0

该类Dictionary不允许键冲突，因此如果您希望多个向量与相同的空间散列相关联（即它们存储在同一个桶中），您需要存储向量列表而不是个体。本质上，您将自己的存储桶存储在字典中：

Dictionary<float, List<Vector3>> Buckets;

接下来，您需要确保您的空间哈希函数为需要位于同一存储桶中的每个项目返回相同的值。考虑到这一点，您最好使用整数作为空间散列。

最后，为了从字典中获取相似的项目，您将不得不使用以下步骤：

  1. 确定获取相似项目的边界框（例如<X-delta, Y-delta, Z-delta>, <X+delta, Y+delta, Z+delta>）
  2. 遍历所有可能与边界框相交的桶
    1. 对于每个相交的桶，计算桶内一个点的空间哈希，并使用字典获取桶中的项目列表
    2. 将存储桶中的项目添加到结果列表中

如果您的存储桶大小相对于您的边界框较小，则上述操作可能会产生很多不必要的工作。如果是这种情况，那么您应该考虑使用不同的数据结构，例如八叉树。

于 2013-03-27T17:12:39.690 回答
0

为了使 aDictionary工作，必须为每个项目分配一个存储桶，以便可以盲目地假设每个项目与不同存储桶中的任何项目不等效。因此，不可能Dictionary直接使用 a 来定位靠近给定点的对象，因为这些对象可能落入多个桶中。

如果您希望能够定位距离给定点严格小于半个单位的所有对象，我建议您分配整数坐标的桶组合，然后将每个点放在每个（通常是八个）桶中其坐标表示与所讨论的点相比的下一个更大或下一个较小的整数。要查找集合是否包含距离给定点严格小于半个单位的点，请在桶中查找最近的点。

根据所讨论点的密度，使用较粗的网格可能会有所帮助，在这种情况下，许多对象只需要存储在一个存储桶中。关键要求是每个点都必须存储在每个可能“最近”到它应该匹配的任何点的存储桶中。

于 2013-03-27T17:45:23.133 回答