c++ - Connected Components with Periodic Boundary Conditions -

normally find connected components on set of points, build graph points placed in 2 dimensional euclidean space edges determined thresholding. namely, if distance between 2 points closer predetermined cut-off radius, consider them neighbors. depth-first search on graph determine connected components.

the problem approach have use thresholding build graph in first place. not computer scientist, never took algorithms class. know if there algorithm can find nearest neighbors or connected components without building edges thresholding? main issue makes thresholding preferable fact box periodic. that's why googling alone didn't me much.

my code this:

// +++++ // graph // +++++  // ( note edges 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 depth-first search starting node int dfsfromnode( graph& graph, int i, stack<int>& s, vector<bool>& visited ){      int connected_comp = 0;      // add node stack     s.push( );      // while there nodes not visited     // (so long stack not empty ..)     while( !s.empty() ){          // remove top of stack (backtracking process)         s.pop();         if( !visited[i] ){             visited[i] = true;             connected_comp++;             set<int> neighbors;             neighbors = graph.edges[i];             for( auto j: neighbors ){                 = j;                 s.push( );             }         } // if node visited before, out      } // while loop check if stack empty or not      return connected_comp;  }  

edit:

to reiterate question, how can find nearest neighbors or connected components without doing thresholding in periodic boundary settings?

for finding connected components, can use kd-trees. k-d tree, (abbrev. k-dimensional tree) algorithm in split data points 2 alternating between orthogonal directions in each degrees of freedom. find following link quite useful explanation.

specifically, in case of periodic boundary conditions, can ghost/image particles outside of primary box , build kd-tree including these particles.