c++ - 从数组中查找重复的 3D 顶点

Question

我有一个点数组。每个点都有位置(x, y, z) 和法 vector (xn, yn, zn) ，一共6个 double 。考虑到浮点容差，我需要在此数组中找到唯一元素并删除重复条目。

实现它的简单有效方法是什么？我想构建一些像BSP或KD-Tree这样的空间划分结构。但我认为应该有更优化的方式，比如智能哈希字典或其他东西。

所以我正在寻求建议，要走哪条路，是否有任何已经实现它的轻量级 C++ 库？

Answer 1

最简单的方法是四舍五入到最接近的 epsilon 并将点带入整数范围(将所有内容乘以 1/epsilon)。一旦它们是整数哈希就可以正常工作(std::unordered_set、std::unordered_map)。这可能会遗漏一些 2 点接近但四舍五入不同的情况。您可以通过四舍五入并考虑与任一结果的冲突来克服这个问题。

如果您使用 std::set/std::map，请注意它们具有 log(N) 访问复杂度(与具有哈希版本的常量相比)。在这一点上，你同样擅长使用 BSP 或 KD-Tree(只要你已经有一些库已经实现了它们)。