KD树，慢树构建

Question

我正在尝试构建KD树（静态大小写）。我们假设点在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 = kd_list->size(); 

//No leaf will be built 
if (n == 0) 
{ 
    return NULL; 
} 

//Only one point: create leaf of KD Tree 
else if (n == 1) 
{ 
    //Create one leaft 
    return new KDNode(new Point2D ((*kd_list)[0])); 
} 

//At least 2 points: create one leaf, split tree into left and right subtree 
else 
{ 
    //New KD node 
    KDNode *node = NULL; 

    //Get median index 
    const unsigned int median_index = n/2; 

    //Create new KD Lists 
    KDList kd_list1, kd_list2; 

    //The depth is even, process by x coordinate 
    if (depth%2 == 0) 
    { 
    //Create new median node 
    node = new KDNode(new Point2D((*kd_list)[median_index])); 

    //Split list 
    for (unsigned int i = 0; i < n; i++) 
    { 
    //Geta actual point 
    Point2D *p = &(*kd_list)[i]; 

    //Add point to the first list: x < median.x 
    if (p->getX() < (*kd_list)[median_index].getX()) 
    { 
    kd_list1.push_back(*p); 
    } 

    //Add point to the second list: x > median.x 
    else if (p->getX() > (*kd_list)[median_index].getX()) 
    { 
    kd_list2.push_back(*p); 
    } 
    } 

    //Sort points by y for the next recursion step: slow construction of the tree??? 
    std::sort(kd_list1.begin(), kd_list1.end(), sortPoints2DByY()); 
    std::sort(kd_list2.begin(), kd_list2.end(), sortPoints2DByY()); 

    } 

    //The depth is odd, process by y coordinates 
    else 
    { 

    //Create new median node 
    node = new KDNode(new Point2D((*kd_list)[median_index])); 

    //Split list 
    for (unsigned int i = 0; i < n; i++) 
    { 
    //Geta actual point 
    Point2D *p = &(*kd_list)[i]; 

    //Add point to the first list: y < median.y 
    if (p->getY() < (*kd_list)[median_index].getY()) 
    { 
    kd_list1.push_back(*p); 
    } 

    //Add point to the second list: y < median.y 
    else if (p->getY() >(*kd_list)[median_index].getY()) 
    { 
    kd_list2.push_back(*p); 
    } 
    } 

    //Sort points by x for the next recursion step: slow construction of the tree??? 
    std::sort(kd_list1.begin(), kd_list1.end(), sortPoints2DByX()); 
    std::sort(kd_list2.begin(), kd_list2.end(), sortPoints2DByX()); 

    } 

    //Build left subtree 
    node->setLeft(buildKDTree(&kd_list1, depth +1)); 

    //Build right subtree 
    node->setRight(buildKDTree(&kd_list2, depth + 1)); 

    //Return new node 
    return node; 
} 
} 

Answer 1

不是一个真正的回答你的问题，但我会极力推荐论坛在http://ompf.org/forum/ 他们在那里为各种情况下的快速kd树构造进行了一些很好的讨论。也许你会在那里找到一些灵感。

编辑：
的OMPF论坛以来下降了，虽然直接替换目前可http://ompf2.com/

Answer 2

排序，找到中位数可能是罪魁祸首这里，因为这是O（nlogn ）而问题在O（n）时间内是可解的。您应该使用nth_element：http://www.cplusplus.com/reference/algorithm/nth_element/。这将在平均线性时间内找到中位数，之后您可以在线性时间内分解向量。在矢量

内存管理也未尝采取了很多的时间，尤其是对于大型的载体，因为每一次的矢量的大小加倍所有的元素都被移动。您可以使用向量的保留方法为新创建的节点中的向量保留足够的空间，因此它们不需要动态增加，因为使用push_back添加了新的东西。

如果您绝对需要最佳性能，则应使用较低级别的代码，而不是使用向量并保留普通数组。第n个元素或“选择”的算法是现成的，不是太难写自己：http://en.wikipedia.org/wiki/Selection_algorithm

Answer 3

优化KD树的一些提示：

• 使用线性时间中位数寻找算法，如QuickSelect。
• 避免实际使用“节点”对象。您可以使用点只有存储整棵树，ZERO附加信息。基本上只需对一组对象进行排序。根节点将处于中间。在查询时，首先放入根，然后使用堆布局的重新排列可能更适合CPU内存缓存，但构建起来会更棘手。

Answer 4

你的第一个罪魁祸首是排序找到中位数。这几乎总是K-d树构造的瓶颈，并且在这里使用更高效的算法将真正获得回报。

但是，每次将元素拆分并传递给它们时，您也正在构造一对可变大小的向量。

在这里，我推荐好ol单链表。链表的美妙之处在于你可以通过改变next指针来指向父指针而不是父指针，从而可以将元素从父母转移到孩子。

这意味着在构建过程中不需要任何堆栈开销将元素从父节点传递到子节点，只需要聚合要插入到根的初始元素列表。这也应该有奇效，但是如果你想要更快，你可以使用一个固定的分配器为链表（以及树）有效地分配节点，并有更好的连续性/缓存命中。

最后但并非最不重要的一点，如果您涉及需要K-d树的密集型计算任务，则需要一个分析器。测量你的代码，你会看到究竟是什么在罪魁祸首，并与确切的时间分布。