algorithm - 生成图边的高效算法

Question

给定一组3D空间坐标大小为N且最大连接距离为d的顶点，是否有一种有效的算法来找到连接距离小于d的顶点的所有无向边；不考虑循环。简单的方法是简单地循环所有可能的对，需要 N(N-1)/2 距离计算。是否存在现有的算法来查找所有可能的边缘，其缩放复杂度小于 O(N^2)？

Answer 1

Given a set of vertices with 3D spatial coordinates of size N and a maximum connection distance d, is there an efficient algorithm to find all the undirected edges connecting the vertices with distance less than d

是的。将顶点位置插入八叉树中，然后为每个顶点搜索比 d 更近的顶点。

对于 2D 中的等效问题，您可以使用四叉树。

您可以在 https://github.com/JamesBremner/quadtree 找到 C++ 四叉树代码

用法示例:

        // construct vector of random points
        std::vector<cPoint> vp = random(count);

        // construct quadtree of points
        cCell quadtree(cPoint(0, 0), 100);
        for (auto &p : vp)
            quadtree.insert(p);

        // quadtree search
        // returns vector of all points within 2 by 2 box around point 10,10
        auto fp = quadtree.find(cCell(cPoint(10, 10), 2));

请注意，如果精确的欧​​几里得距离很重要，则需要进行后处理以删除红色区域中的任何点。

如需了解更多详情，请观看 Netflix 上的德国电视迷你剧“十亿美元密码”。