为了在 3d 空间中的一堆平面实体中快速找到共面实体,我想创建一个从 3d 平面到位于该平面中的实体集的映射(估计最多约 1000 个平面和 100000 个实体)
我可以创建自己的自定义类来表示 3D 平面键,但基本上这个类需要(在数学上)四个 double 来唯一标识一个平面:3 个坐标用于法 vector ,一个坐标用于指定平面上的一个点。所以我们有:
struct Plane3d
{
double n_x, n_y, n_z;
double u; // (u*n_x, u*n_y, u*n_z) is a point on the plane
// some constructors etc.
}
这四个 double 每次都是从所考虑的实体计算的,因此必须考虑舍入误差和 float 比较问题。假设我已经计算出一个合适的(相对)容错度:
const double EPSILON;
但我不想逐一比较所有实体对的共面性(在 O(n^2) 时间内进行分类),而是创建一个 map 来对我的实体进行分类。
最理想的是 unordered_map(在 O(n) 时间内创建):
unordered_map<Plane3d, vector<Entity>, PlaneHash, PlaneEquality> mapping;
这需要编写两个仿函数:PlaneEquality 没问题,但是...
- 是否可以为四个 double (或什至只是一个普通的 double )编写一个考虑比较误差容限的哈希函数。
- 在规范中我读到相等仿函数仅用于区分同一桶内的相等键。有没有办法确保相同的键实际上最终在同一个桶中?
另一种选择是使用法线贴图(仍然在 O(n log n) 时间内创建)
map<Plane3d, vector<Entity>, PlaneCompare> mapping;
PlaneCompare 仿函数听起来可行,我可以使用四个 double 的字典顺序并使用 EPSILON
检查每个“小于”。但是我还有几个问题:
- 这真的有用吗?有什么陷阱吗?
- 规范说明键的相等性,比如 p1 和 p2,由测试
!PlaneCompare(p1,p2) && !PlaneCompare(p2,p1)
确定。如果我使用字典顺序,这应该等同于具有容错性的直接相等测试,但这不是更慢吗?
最佳答案
“是否可以为四个 double (或者甚至只是一个普通的 double )编写一个考虑比较误差容限的哈希函数。”
不,不是。
这听起来像是一个非常明确的陈述,我怎么能这么肯定呢?
假设您需要 0.00001 的公差。该值无关紧要,我们只是将其用作示例。这意味着对于这个哈希函数:
- hash(1.0) 必须返回与 hash(1.00001) 相同的值
这样他们就可以被认为是平等的。但这也意味着:
- hash(1.00001) 必须返回与 hash(1.00002) 相同的值
出于同样的原因,和
- hash(1.00002) 必须返回与 hash(1.00003) 相同的值
...依此类推,直到 double 的最高可能值 - 无限有效。对于小于 1 的值也是如此。
因此任何允许容错的散列函数都必须为所有值返回相同的散列值,这使其毫无用处。
附言要实际推荐一种确实有效的方法,四维四叉树(技术上类似于 sedecimtree)可能是最好的。
关于c++ - 对于由计算的 double 值组成的键,在 map 或 unordered_map 之间进行选择。,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30894138/