c++ - 具有周期性边界条件的连通分量

Question

通常为了找到一组点上的连通分量，我根据放置在二维欧几里得空间中的点构建一个图，其中的边是用阈值确定的。也就是说，如果两点之间的距离小于预定的截止半径，那么我将它们视为邻居。然后我对该图进行深度优先搜索以确定连通分量。

这种方法的问题是我必须首先使用阈值来构建图形。我不是计算机科学家，所以我从未上过算法课。我想知道是否有一种算法可以在不使用阈值构建边缘的情况下找到最近的邻居或连接的组件？使阈值如此可取的主要问题是这个框是周期性的。这就是为什么单独使用谷歌搜索对我帮助不大。

我的代码如下所示:

// +++++
// Graph
// +++++

// ( Note that edges are lines connecting nodes or vertices )

class Graph
{

public:
    Graph() {}
    ~Graph() {}
    void setNumNodes( int nds );
    int getNumNodes() { return numNodes; }
    void addEdge( int nd_idx, set<int> dest );
    map<int,set<int> > edges; // [node, destination]
    void setThreshold( double cutoff, double carpan );
    double getThreshold() { return threshold; }

private:
    int numNodes;
    double threshold;

};

void Graph::setNumNodes( int nds ){
    numNodes = nds;
}

void Graph::addEdge( int nd_idx, set<int> dest ){
    edges.insert( pair<int,set<int> >( nd_idx, dest ) );
}

void Graph::setThreshold( double cutoff, double carpan ){
    threshold = 2*R + carpan*cutoff;
}


// +++++

// Function for depth-first search from a starting node
int dfsFromNode( Graph& graph, int i, stack<int>& S, vector<bool>& visited ){

    int connected_comp = 0;

    // Add the node to the stack
    S.push( i );

    // While there are nodes that are not visited
    // (so as long as stack is not empty ..)
    while( !S.empty() ){

        // Remove the top of the stack (backtracking process)
        S.pop();
        if( !visited[i] ){
            visited[i] = true;
            connected_comp++;
            set<int> neighbors;
            neighbors = graph.edges[i];
            for( auto j: neighbors ){
                i = j;
                S.push( i );
            }
        } // if the node is visited before, get out

    } // while loop to check if the stack is empty or not

    return connected_comp;

} 

编辑:

重申一下这个问题，我如何在不对周期性边界设置进行阈值处理的情况下找到最近的邻居或连通分量？

Answer 1

要查找连通分量，您可以使用 kd-trees。 k-d 树(缩写为 k 维树)是一种算法，您可以在其中将数据点分成两个在每个自由度的正交方向之间交替的算法。我找到了 following link对解释很有用。

具体来说，在周期性边界条件的情况下，您可以只在主框外重影/成像粒子，并构建包含这些粒子的 kd 树。