CGAL users discussion list

["Kevin Xu" <>]

Hi, Sun Jian,

You can use the map container provided by STL to achieve this.

Let's take the range search (with kd-tree) for example:

KD_tree STree;  // define a kd tree for all vertices
std::map<Point,int> mVPToID;  // map vertex pos. to index
std::map<Point,int>::iterator iPTI; // an iterator for mVPToID

// construct mapping
for (all vertices in a mesh or other data structure)
{
    STree.insert (VP(i));    // add position of the ith vertex
    mVPToID.insert (std::make_pair(VP(i), ID(i))); // make a map
between pos. & id
}

// perform range searching
std::vector<Point> FP;    // store all found points (pos.)
Fuzzy_sphere fs(query_pos, dRadia, 0.0);  // a fuzzy query sphere
STree.search(std::back_inserter(FP), fs);   // do searching

// collect ids for the found points
for (int i=0; i<FP.size(); i++)
{
    if ((iPTI=mVPToID.find(FP[i])) != mVPToID.end())
    {  // find the record of FP[i] to get its id
        ID(i) = iPTI->second;   // id of the ith point is "iPTI->second"
    }
}

/// end of the routine

The routines for k-NN search, etc., are similar.

HTH.

Good luck!