在c#字典中获得相似值的最快方法

本文关键字：方法 相似 字典 | 更新日期: 2023-09-27 18:06:03

我在c#中有一个空间哈希类来检测3D数据。每个顶点位置都有一个空间散列，Vector3存储在Dictionary<float, Vector3>中，其中浮点数是我计算的实际空间散列。我理解空间哈希的方式是，将哈希排序到桶中，然后获得彼此在阈值(例如，0.0001f)范围内的值。我所做的大多数研究都实现了桶排序，我不知道如何使用我拥有的Dictionary来实现。

所以，我的问题是，我应该如何在这样的字典中获得类似的值?到目前为止，在我看来，我需要将哈希值排序到threshold大小的桶中，并以某种方式维护到Vector3的链接。我的思路是不是完全错了?比如说，是否存在一种更适合这个特定用例的通用类型?

在c#字典中获得相似值的最快方法

实现接口

IEqualityComparer<float>

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

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

如果您想避免麻烦，请重新考虑使用特殊散列。虽然3D哈希函数完全有可能实现，但它相当复杂(如果你想要一个完美的哈希，也就是说)，可以很容易地被一些智能的"足够接近"的函数所取代。

所以，选择是你的:

完美散列

或

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

Dictionary类不允许键冲突，所以如果你想要多个向量与相同的空间散列相关联(即它们被存储在相同的桶中)，你需要存储向量列表而不是个体。实际上，您将自己的桶存储在字典中:

Dictionary<float, List<Vector3>> Buckets;

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

最后，为了从字典中获得相似的项，您必须使用以下步骤:

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

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

为了使Dictionary工作，必须为每个项分配一个bucket，这样每个项可以被盲目地假设为不等同于任何在不同bucket中的项。因此，不可能直接使用Dictionary来定位在给定点附近的对象，因为这些对象可能会落入多个桶中。

如果你想要定位所有距离给定点不到半单位的对象，我建议你分配整数坐标的桶组合，然后将每个点放置在每个(通常是八个)桶中，其坐标代表与问题点相比的下一个较大或较小的整数。要确定集合中是否有一个点与给定点的距离严格小于半个单位，请在桶中查找最近的点。

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

相关文章：