小编Ian*_*Ian的帖子

我需要找到数据集中每个点的所有最近邻居.数据集包含约.1000万2D点.数据接近网格,但不形成精确的网格......

此选项排除(在我看来)使用KD树,其中基本假设是没有点具有相同的x坐标和y坐标.

我需要一个快速算法O(n)或更好(但实现起来并不太困难:-)))来解决这个问题...由于boost不是标准化的事实,我不想用它...

感谢您的答案或代码示例......

我正在尝试构建KD Tree(静态情况).我们假设点在x和y坐标上排序.

对于均匀的递归深度,该集合被分成两个子集,其中垂直线穿过中间x坐标.

对于奇数递归深度,该集合被分成两个子集,其中水平线穿过中间y坐标.

可以根据x/y坐标从排序集中确定中值.这一步我在每次拆分之前做的.而且我认为它导致了树的缓慢构造.

1. 你能帮我检查一下并优化代码吗？
2. 我找不到第k个最近的邻居,有人可以帮我代码吗？

非常感谢你的帮助和耐心......

请参阅示例代码:

class KDNode
{
private:
Point2D *data;
KDNode *left;
KDNode *right;
    ....
};

void KDTree::createKDTree(Points2DList *pl)
{
//Create list
KDList kd_list;

//Create KD list (all input points)
for (unsigned int i = 0; i < pl->size(); i++)
{
kd_list.push_back((*pl)[i]);
}

//Sort points by x
std::sort(kd_list.begin(), kd_list.end(), sortPoints2DByY());

//Build KD Tree
root = buildKDTree(&kd_list, 1);
}


KDNode * KDTree::buildKDTree(KDList *kd_list, const unsigned int depth)
{
//Build KD tree
const unsigned int n = …

I have the following class:

class Point2D
{
    protected:

            double x;
            double y;
    public:
            double getX() const {return this->x;}
            double getY() const {return this->y;}
   ...

};

有时我需要返回x坐标,有时是y坐标,所以我使用指向成员函数getX(),getY()的指针.但我无法返回坐标,请参阅下文.

double ( Point2D :: *getCoord) () const;

class Process
{
   ......
   public processPoint(const Point2D *point)
   {

      //Initialize pointer
      if (condition)
      {
         getCoord = &Point2D::getX;
      }
      else
      {
         getCoord = &Point2D::getY;
      }

      //Get coordinate
      double coord = point->( *getCoordinate ) (); //Compiler error

   }

}

谢谢你的帮助.