Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

Accelerated Search For the Nearest Line


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++;
        }
    }
}
Listing 5

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;
}
Listing 6

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.