Accelerated Search For the Nearest Line

Optimization 1: Check Bounding Rectangle First

A obvious shortcut is, to first build a rectangle of start and endpoint (plus the maximum search width), and to check if the point p lays within this rect. If it does not, the line is too far away. This is less computation intensive. It reduces the search time to 82ms, reducing the batch run to less than two days.

Optimization 2: Introducing Quadrants

The key for the whole solution presented here is to divide the whole area in quadrants, like on a chessboard. A given point can lay only within one quadrant. A line only can match a limited number of quadrants. If the width of each quadrant is not smaller than the maximum search width, then a shortcut can be used to exclude all lines not within that distance: Then, two points with a distance less or equal to the maximum search width must lay on the same or on neighborhood quadrants. Thereby, if a points own quadrant and its 8 surrounding quadrants don't have any quadrant in common with the quadrants of a line, the line is too far away and further computation can be skipped; see Figure 3.

[Click image to view at full size]

Figure 3: Point p1 has a matching quadrant with line1. p2 does not and thereby cannot lie within the maximum search width from line1.

A CQuadrant object can be used to determine and store the quadrant-ID of a point. The quadrants boundary data has to be statically setup before usage. You must call the static member function:

void CQuadrant::SetUp(double x1, double y1, double x2, double y2, double width)

and pass the minimum and maximum coordinates of the whole graph as well as the width of one quadrant. The width is a very important property. In this stage the quadrant width at best is equal to the maximum search width (10m). The constructor of a CQuadrant object requires the coordinates of the point it should represent and thereby calculates two integers that, combined, build a ID identifying the quadrant (see Listing 2).

void CQuadrant::CQuadrant(CworldPoint &Loc)
{
    mQuadx = ((short)( (Loc.dWrldx() - mxMin) / mWorldMaxOff) );
    mQuady = ((short)( (Loc.dWrldy() - myMin) / mWorldMaxOff) );
}

As lines can have any length and thereby can pass more than one quadrant, the class CQuadSection was introduced. The constructor of CQuadSection requires the start and end coordinates of the line and holds a rectangle of the minimum and maximum quadrants. (For simplicity, in this implementation a line matches all quadrants that are within its bounding rectangle. Of course a improved implementation would check all these quadrants and see if they are really passed by the line).

To see if a point can be within the maximum search width of a pipe the function

CQuadSection::Matches(CQuadrant &Other).

is called, which just checks if one of the 9 quadrants of (and surrounding) the point is contained in the quadrants used by the line (see Listing 3).

int CQuadrant::Matches(CQuadrant &Other)
{
    return (mTopRight  .mQuadx + 1 >= Other.mQuadx  &&
            mBottomLeft.mQuadx - 1 <= Other.mQuadx  &&
            mTopRight  .mQuady + 1 >= Other.mQuady  &&
            mBottomLeft.mQuady - 1 <= Other.mQuady);
}

The quadrants for all lines can be generated once before doing the batch run. This takes about 3640ms. It leads to a reduction of the search time to about 17ms for checking for the nearest match in 1,000,000 lines, thus reducing the total runtime to less than 10 hours (see Table 1).

Optimization 3: Holding Lists for All Matches In Each Quadrant

Still, for every search we have to iterate through all 1,000,000 lines no matter how far they are away. The solution is to build a 3-dimensional container: a 2-dimensional map, representing all quadrants of the area with each item holding a list of all matches in a single quadrant, as in Listing 4. See Figure 4 for illustration.

[Click image to view at full size]

Figure 4: Illustration of 2-dimensional map, that contains the matching lines of each quadrant.

class CQuadMap
{
    // Typedef for 3-Dimensional container holding all quadrant matches
    ///////////////////////////////////////////////////////////////////////////
    // 3d  Dimension: List of all Lines that match a quadrant
    typedef std::list<CLineObj*>LinePtrVec;
    // 2nd Dimension: map of LinePtrVec  for all not empty quadrants within a line
    typedef std::map<CQuadrant::data_type, LinePtrVec>QuadLineEntrys;
    // 1st Dimension: map of QuadLineMap for all not empty rows
    typedef std::map<CQuadrant::data_type, QuadLineEntrys>QuadEntryMap;

    QuadEntryMap mPipeQuadMap;  // Data of all Lines imported by Add
 ...
};