标签: kdtree

因此,NetworkX明确表示他们在n ^ 2时间内使用算法生成随机几何图形.他们说使用KD树可以实现更快的算法.我的问题是如何尝试实现此算法的KD Tree版本？我不熟悉这种数据结构,也不称自己为python专家.试图解决这个问题.感谢所有帮助,谢谢!

    def random_geometric_graph(n, radius, dim=2, pos=None):
        G=nx.Graph()
        G.name="Random Geometric Graph"
        G.add_nodes_from(range(n)) 
        if pos is None:
            # random positions
            for n in G:
                G.node[n]['pos']=[random.random() for i in range(0,dim)]
        else:
            nx.set_node_attributes(G,'pos',pos)
        # connect nodes within "radius" of each other
        # n^2 algorithm, could use a k-d tree implementation
        nodes = G.nodes(data=True)
        while nodes:
            u,du = nodes.pop()
            pu = du['pos']
            for v,dv in nodes:
                pv = dv['pos']
                d = sum(((a-b)**2 for a,b in zip(pu,pv)))
                if d <= radius**2:
                    G.add_edge(u,v)
    return …

我正在寻找一段合适的代码在我的应用程序中使用，在其中一个算法中。我找到了这个例子： http: //rosettacode.org/wiki/K-d_tree#C 但是当我将代码放入 xcode 中时，我收到错误，例如：

“使用未声明的标识符”，“预期为‘;’ 声明末尾”。我猜是缺少头文件吗？

我在 5 维空间中有大约 10 K 点。我们可以假设点在空间 (0,0,0,0,0) 和 (100,100,100,100,100) 中随机分布。显然，整个数据集可以很容易地驻留在内存中。

我想知道 k 最近邻的哪种算法运行得更快，kd-tree 或 RTree。

虽然我对这两种算法有一些非常高级的想法，但我不确定哪个会运行得更快，以及为什么。如果有的话，我愿意探索其他算法，这些算法可以快速运行。如果可能，请说明为什么算法可以运行得更快。

我使用 CGAL 的 Kd 树实现以及模糊球体作为查询对象来获取以某个点为中心的半径球体中包含的点r_max。这是这个最小的工作示例：

    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/Kd_tree.h>
    #include <CGAL/Search_traits_2.h>
    #include <CGAL/Fuzzy_sphere.h>
    #include <iostream>
    #include <fstream>

    typedef CGAL::Simple_cartesian<double>  K;
    typedef K::Point_2                      Point;
    typedef CGAL::Search_traits_2<K>        TreeTraits;
    typedef CGAL::Kd_tree<TreeTraits>       Kd_tree;
    typedef Kd_tree::Tree                   Tree;
    typedef CGAL::Fuzzy_sphere<TreeTraits>  Sphere;

    int main(int argc, char* argv[])
    {
        double r_max;
        Tree tree;

        /* ... fill the tree with points, set the value of r_max ...*/

        // Report indices for the neighbors within a sphere
        unsigned int   idc_query = tree.size()/2;           // test index
        Tree::iterator kti       = …

在我正在开发的 python 应用程序中，我有一个 3D 点数组（大小在 2 到 100000 之间），我必须找到彼此相距一定距离内的点（比如两个值之间，例如 0.1 和 0.2） . 我需要这个用于图形应用程序，并且此搜索应该非常快（对于 10000 点的样本，大约为 1/10 秒）

作为第一个实验，我尝试使用 scipy.spatial.KDTree.query_pairs 实现，对于 5000 点的样本，返回索引需要 5 秒。您知道任何可能适用于这种特定情况的方法吗？

关于应用程序的更多信息：

这些点代表原子坐标，距离搜索可用于确定原子之间的键。键不一定是固定的，但可能会在每一步发生变化，例如在氢键的情况下。

我正在 Unity 环境中进行一些视觉艺术研究。我正在尝试实现与此处解释的差分线增长非常相似的东西， 但我主要担心的是，在算法中的某个地方，每个节点都应该检查每个其他节点以查看它的接近程度，并根据所有这些构建排斥力阵列附近的粒子。

这是我的代码片段：

   public void Differentiate()
    {
        int c = nodes.Count;                                 
        Vector3[] repulsionForces = new Vector3[c];

        for (int i = 0; i < c ; i++)
        {

            // Construct nearbies
            List<DifferentialNode> nearby = new List<DifferentialNode>();
            foreach(DifferentialNode n in nodes)
            {
                float d = Vector3.Distance(n.position, nodes[i].position);
                if (d < 5)
                {
                    nearby.Add(n);
                }
            }
            // Get Forces
            Vector3 repulsionForce = nodes[i].RepulsionForce(nearby);

            // Limit Forces
            repulsionForce = Vector3.ClampMagnitude(repulsionForce, maxForce);

            // Apply Multipliers
            repulsionForce *= Repulsion;

            // Put …