查找是否已使用3D坐标的最快方法
使用C ++(和Qt)，我需要处理大量3D坐标。
具体来说，当我收到3D坐标(由3个双精度数组成)时，我需要在列表中检查该坐标是否已被处理。
如果没有，那么我将其处理并将其添加到列表(或者容器)中。
坐标的数量会变得非常大，因此我需要将处理后的坐标存储在容器中，以确保快速检查容器中是否已包含3D坐标。
我当时在考虑使用地图的地图，先存储x坐标，再存储y坐标，再存储z坐标，但这使使用起来非常繁琐，所以我实际上希望有一种更好的方法做我想不到的。
解决方案
回答
好吧，这取决于最重要的内容...如果三重图过于繁琐而无法使用，那么实现其他数据结构值得吗？
如果要避免三重地图解决方案的丑陋之处，只需将其包装在另一个具有三个参数的访问函数的容器类中，然后在其中隐藏所有内部混乱的地图。
如果我们更担心此事物的运行时性能，则将坐标存储在Octree中可能是个好主意。
还值得一提的是，使用浮点数或者双精度数进行此类操作时，我们应该非常注意精度-如果(0，0，0.01)坐标与(0，0，0.01000001)相同？如果是这样，则无论数据结构如何，都需要查看使用的比较函数。我猜这也取决于坐标源。
回答
我们是否期望/要求完全匹配？这些可能很难用双倍来执行。例如，如果我们已处理(1.0，1.0，1.0)，然后收到(0.9999999999999，1.0，1.0)，我们会认为它是相同的吗？如果是这样，我们将需要应用某种近似或者定义误差范围。
但是，要回答问题本身：想到的第一个方法是创建一个索引(字符串或者位串，具体取决于我们希望事物的可读性)。例如，创建字符串"(1.0,1.0,1.0)"并将其用作地图的键。这将使查找地图变得容易，使代码保持可读性(并且还使我们可以轻松地转储地图的内容以用于调试目的)，并为我们提供合理的性能。如果我们需要更快的性能，则可以使用哈希算法将三个坐标数值组合起来，而无需通过字符串。
回答
如何使用boost :: tuple作为坐标，并将tuple存储为地图的索引呢？
(我们可能还需要从此答案中进行除以除法的想法。)
回答
选择一个常数以按比例缩放坐标，以便1个单位描述一个可以接受的小方框，而最大分量的整数部分将适合32位整数；将结果的X，Y和Z分量转换为整数并将它们哈希在一起。使用它作为映射或者哈希表的哈希函数(不要作为数组索引，我们需要处理冲突)。
在比较坐标时，我们可能还需要考虑使用模糊系数，因为我们可能会得到仅稍有不同的浮点值，通常最好将它们焊接在一起以避免渲染时出现裂纹。
回答
使用3D坐标的任何唯一变换，并仅存储结果列表。
例子：
md5('X，Y，Z')是唯一的，我们只能存储结果字符串。
哈希不是一个有效的想法，但是我们可以理解。找到任何数学上唯一的变换就可以了。
回答
/维
如果我们使用简单的公共接口编写帮助程序类，则将大大减少实际的实现细节，例如使用map <map <map <> <>>>>。封装之美！
回答
就是说，我们可能能够绑定一个哈希表来很好地完成此操作。只需将三个双打散列在一起就可以得到整个点的关键。如果我们担心对称坐标的点之间有很多碰撞(例如(1、2、3)和(3、2、1)等)，只需使哈希键相对于x，y不对称和z坐标，使用位移或者类似方法。
加快处理速度的最简单方法可能是将已处理的点存储在Octree中。检查重复将接近对数。
回答
另外，通过检查点之间的距离而不是坐标的相等性来确保容忍舍入误差。
回答
例如，我们可以使用任何可哈希类型的hash_set，将每个元组转换为字符串"(x，y，z)"。 hash_set可以快速查找，但是可以很好地处理冲突。
回答
无论使用哪种存储方式，我都建议我们确定一个epsilon(将两个坐标区分开的最小浮点距离)，然后将所有坐标除以epsilon，四舍五入并存储为整数。
struct Coor {
Coor(double x, double y, double z)
: X(x), Y(y), Z(z) {}
double X, Y, Z;
}
struct coords_thesame
{
bool operator()(const Coor& c1, const Coor& c2) const {
return c1.X == c2.X && c1.Y == c2.Y && c1.Z == c2.Z;
}
};
std::hash_map<Coor, bool, hash<Coor>, coords_thesame> m_SeenCoordinates;
朝这个方向的东西可能是：
回答
未经测试，后果自负:)
struct coord_eq
{
bool operator()(const Coordinate &s1, const Coordinate &s2) const
{
return s1 == s2;
// or: return s1.x() == s2.x() && s1.y() == s2.y() && s1.z() == s2.z();
}
};
struct coord_hash
{
size_t operator()(const Coordinate &s) const
{
union {double d, unsigned long ul} c[3];
c[0].d = s.x();
c[1].d = s.y();
c[2].d = s.z();
return static_cast<size_t> ((3 * c[0].ul) ^ (5 * c[1].ul) ^ (7 * c[2].ul));
}
};
std::hash_map<Coordinate, coord_hash, coord_eq> existing_coords;
回答
假设我们已经有一个Coordinate类，则添加一个哈希函数并维护坐标的hash_set。
看起来像：
将空间分成离散的垃圾箱。可以是无限深的正方形，也可以是立方体。将处理后的坐标存储在一个简单的链接列表中，如果需要，可以在每个bin中进行排序。当我们获得新坐标时，跳到封闭的容器中，并在列表中移动以寻找新点。
回答
注意浮点比较。我们需要将值转换为整数(例如乘以1000并截断)，或者确定将两个值视为相等的接近程度。
我们可以轻松地为一级std :: map定义比较器，从而使查找变得不那么麻烦。没有理由担心。比较器定义映射的_Key模板参数的顺序。然后，它也可以用于多地图和集合集合。
#include <map>
#include <cassert>
struct Point {
double x, y, z;
};
struct PointResult {
};
PointResult point_function( const Point& p ) { return PointResult(); }
// helper: binary function for comparison of two points
struct point_compare {
bool operator()( const Point& p1, const Point& p2 ) const {
return p1.x < p2.x
|| ( p1.x == p2.x && ( p1.y < p2.y
|| ( p1.y == p2.y && p1.z < p2.z )
)
);
}
};
typedef std::map<Point, PointResult, point_compare> pointmap;
int _tmain(int argc, _TCHAR* argv[])
{
pointmap pm;
Point p1 = { 0.0, 0.0, 0.0 };
Point p2 = { 0.1, 1.0, 1.0 };
pm[ p1 ] = point_function( p1 );
pm[ p2 ] = point_function( p2 );
assert( pm.find( p2 ) != pm.end() );
return 0;
}
回答
一个例子：
使用std :: set。为定义了operator <的3d坐标定义一种类型(或者使用boost :: tuple)。添加元素时，可以将其添加到集合中，如果已添加，则进行处理。如果未添加(因为它已经存在于其中)，请不要进行处理。
回答
但是，如果我们使用的是双精度，请注意算法可能会导致不可预测的行为。 IE(1.0、1.0、1.0)与(1.0、1.0、1.000000001)相同吗？
有多种方法可以做到这一点，但我们首先必须问自己，假设和条件是什么。
因此，假设空间有限，并且知道最大精度是多少，那么我们可以形成一个函数，给定(x，y，z)会将它们转换为唯一的数字或者字符串-仅当我们知道准确性是有限的(例如，没有两个实体可以占据相同的立方厘米)。
对坐标进行编码可让我们将单个地图/哈希与O(1)一起使用。
回答
如果不是这种情况，我们始终可以按照建议使用3个嵌入式地图，也可以采用空分算法(例如上述的OcTree)，尽管平均搜索时给出O(logN)，但它们还会为我们提供其他信息可能会想要(邻居，人口等)，但是当然很难实现。
#include <set>
#include <cassert>
const double epsilon(1e-8);
class Coordinate {
public:
Coordinate(double x, double y, double z) :
x_(x), y_(y), z_(z) {}
private:
double x_;
double y_;
double z_;
friend bool operator<(const Coordinate& cl, const Coordinate& cr);
};
bool operator<(const Coordinate& cl, const Coordinate& cr) {
if (cl.x_ < cr.x_ - epsilon) return true;
if (cl.x_ > cr.x_ + epsilon) return false;
if (cl.y_ < cr.y_ - epsilon) return true;
if (cl.y_ > cr.y_ + epsilon) return false;
if (cl.z_ < cr.z_ - epsilon) return true;
return false;
}
typedef std::set<Coordinate> Coordinates;
// Not thread safe!
// Return true if real processing is done
bool Process(const Coordinate& coordinate) {
static Coordinates usedCoordinates;
// Already processed?
if (usedCoordinates.find(coordinate) != usedCoordinates.end()) {
return false;
}
usedCoordinates.insert(coordinate);
// Here goes your processing code
return true;
}
// Test it
int main() {
assert(Process(Coordinate(1, 2, 3)));
assert(Process(Coordinate(1, 3, 3)));
assert(!Process(Coordinate(1, 3, 3)));
assert(!Process(Coordinate(1+epsilon/2, 2, 3)));
}
回答
我们可以轻松地使用一组，如下所示：
回答
我们可以使用3D坐标的" std :: set"，也可以使用排序后的" std :: vector"。两者都会给我们对数时间查找。无论哪种情况，我们都需要为3D坐标类实现小于比较运算符。
何必？我们正在执行什么"处理"？除非它非常复杂，否则重新进行计算可能会更快，而不是浪费时间在巨大的地图或者哈希表中查找内容。
这是关于现代cpu的更违反直觉的事情之一。计算速度快，内存速度慢。
回答
我意识到这并不是问题的答案，而是问题。
好问题...这是有很多解决方案的问题，因为这类问题来了
在图形和科学应用程序中多次使用。
根据我们所需要的解决方案，在幕后可能会相当复杂。
更少的代码并不一定意味着更快。
"但是使用起来很繁琐" –通常，我们可以通过以下方法解决此问题
typedefs或者wrapper类(在这种情况下，强烈建议使用包装器)。
如果我们不需要以任何特别有意义的方式使用3D坐标(
例如"给我点P的X距离内的所有点")，那么我建议我们
只是找到一种方法来散列每个点，并使用一个散列图... O(n)创建，O(1)
访问(检查是否已处理)，我们做得到的没有比这更好的了。
如果我们确实需要更多空间信息，则需要一个显式使用的容器
它考虑在内。
我们选择的容器类型将取决于数据集。如果你有好的话
了解我们将获得的价值范围将有所帮助。
如果我们要在已知范围内接收分布良好的数据，请使用octree。
段落数量不匹配
