This was the breakthrough. It is implemented in the class CQuadMap.
CQuadMap has a member mPipeQuadMap that holds such a 3-Dimensional container. The class has three important functions:
- A constructor, to which the maximum search width is passed. I use 50 meters here.
- A function Add(CLineObj &) to insert a Line (see Listing 5). This function adds a pointer of the Line passed to all its matching quadrant entries of mPipeQuadMap;
- A function Find(CWorldPoint &Pnt, CLineObj *ExcludeObj) to find the nearest line to point. (see Listing 6). This function tests only those lines that are referenced in the entries of mPipeQuadMap that represent the nine quadrants of and surrounding the given point. The parameter ExcludeObj is needed to prevent, that the line itself is returned, when we search a foreign link to the start or endpoint of a CLine object. After each call to Find(), CQuadMap can be queried for the connection point on the line and for the distance to that point.
void CQuadMap::Add(CLineObj &lineObj) { // Get List of all Qudrants touched by this line CQuadSection theQuad(lineObj.Start(), lineObj.End()); // Add this line to all matching quadrant entries for(CQuadrant::data_type x = theQuad.BottomLeft().Quadx(); x <= theQuad.TopRight().Quadx(); x++) { for(CQuadrant::data_type y = theQuad.BottomLeft().Quady(); y <= theQuad.TopRight().Quady(); y++) { CQuadrant q; q.SetQuads(x, y); mPipeQuadMap[x][y].push_back(&lineObj); sgPoints++; } } }
CLineObj *CQuadMap::Find(CWorldPoint &Point, CLineObj *ExcludeObj) { CQuadrant theQuad(Point), // The quadrant of Point Quadx; CLineObj *foundLine = NULL; mLastOff = 1.e20; // Check all surrounding 9 quadrants for(int Quad = 0; Quad < CQuadrant::NEIGHBORCOUNT; Quad++) { // Get the list holding all matches for this quadrant Quadx = theQuad.GetNeighbor(Quad); QuadEntryMap::iterator it_line = mPipeQuadMap.lower_bound(Quadx.Quadx()); if(it_line == mPipeQuadMap.end()) continue; QuadLineEntrys::iterator it_row = it_line->second.lower_bound(Quadx.Quady()); if(it_row == it_line->second.end()) continue; LinePtrVec &theMap = it_row->second; // Test all Lines in the list of this quadrant for(LinePtrVec::iterator it = theMap.begin(); it != theMap.end(); it++) { if(ExcludeObj == *it) continue; CWorldPoint pos; double d = (*it)->DistToPoint(Point, &pos); sgSearches++; if(d <= mMaxOff && (! foundLine || d < mLastOff)) { mLastPos = pos; mLastOff = d; foundLine = *it; sgMatches++; } } } return foundLine; }
After calling Add() for every line element (which takes 4760ms in the example) we now only have to check a very small fraction of all lines. In doing so the search time was reduced to about 0.007 ms -- which is about factor 36,000 compared to linear search. The batch process for all lines in the sample now needs only 21 seconds in total anymore.