容器中 n X n 搜索的性能问题

Question

我有一个几何体（顶点）的自定义数组实现。数组的每个元素都由具有 Point 的顶点表示。现在我想检查数组中顶点的每个点之间的距离。所以基本上对于大小为 n 的数组中的每个顶点，我将循环直到 n 并计算顶点与数组中所有 n 个顶点的距离。所以伪代码看起来像这样

    func MyFunc( Array iVrtxList , vrtx inpVertex )
     {
        point refPt = inpVertex->getPoint(); 
       for ( i=0 ; i < iVrtxList.size(); i++)   
       {
            if( distanceBetween(iVertexList(i).point ,rePt ) == 0 )
               return 
       }
       iVrtxList.add(inpVertex);
      }
}

所以我想避免 N X N 循环。我想到了对容器进行排序，然后只检查后续元素的距离。不过我好像漏掉了一些元素

Answer 1

我有点实现了 objective 在不使用 N X N 方法的情况下跳过重复的顶点。我使用 multimap 来跟踪顶点。密钥使用 x、y、z 值进行哈希处理，我们将其调整为精度以使其与数据集一起使用。然而，散列计算是脆弱的，因为任何导致冲突的映射都会破坏目的。以下是定义

class PointCoords
{
public:

    PointCoords(double  ix, double iy, double iz) : _x(ix), _y(iy), _z(iz) { };

    double _x;
    double _y;
    double _z;

};

class PointCoords_hash
{
public:
    size_t operator()(const PointCoords& v) const
    {
        auto f1 = std::hash<double>{}(round(v._x * 10) / 10);
        auto f2 = std::hash<double>{}(round(v._y * 10) / 10);
        auto f3 = std::hash<double>{}(round(v._z * 10) / 10);
        size_t hCode = (f1 ^ f2 ^ f3) << 1;
        return ((f1 ^ f2 ^ f3) << 1);
    };
};

class PointCoords_equal
{
public:
    bool operator()(const PointCoords& u, const PointCoords& v) const
    {
        return (equal(u._x, v._x, 1e-6) &&
            equal(u._y, v._y, 1e-6) &&
            equal(u._z, v._z, 1e-6));
    };
};
bool :equal( double d1, double d2, double err) 
{
    
    return ( fabs( d1 -d2) <= err);
}

容器中 n X n 搜索的性能问题

Performance issue with a n X n search in a container

sorting

algorithm

geometry

loops