Accelerated Search For the Nearest Line

The Basics: Which Point Is Nearest?

For a given point p, finding the nearest point within a single straight line is a three-phase process (see Figure 2):

1. Drop a perpendicular on the (infinitely extended) line.
2. Check, if the perpendicular is between the start- and endpoints of the line.
3. If "yes," then return the connecting point of the perpendicular and the line (in cases of p1 and p2 in Figure 2); otherwise return the start- (in case of p3), or endpoint (for p4), whatever is nearest.

[Click image to view at full size]

Figure 2: Finding the nearest point within a line.

This process is implemented in the member function CLineObj::DistToPoint(...) (see Listing 1).

double CLineObj::DistToPoint(CWorldPoint &Point, CWorldPoint *ConnectPoint)

{   
    // Get coordinates of start/end
    double xa = Start().Getx();
    double ya = Start().Gety();
    double xb = End().Getx();
    double yb = End().Gety();

    // Calculate triangular data
    double dist = Start().DistTo(End());
    double xOff = xb - xa;
    double yOff = yb - ya;
    double xRaise = (dist == 0.) ? 0. : xOff / dist;
    double yRaise = (dist == 0.) ? 0. : yOff / dist;

    // Special Case: Line is a point
    if(dist == 0)
        return Point.DistTo(Start());

    // Calculate the perpendicular to a infinite line
    double p = - (xa*yb - ya*xb) / dist;
    double xy4dist = Point.Gety() * xRaise - Point.Getx() * yRaise - p;

    // Calculate Connectionpoint of perpendicular on infinite line
    double x4 = Point.Getx() + (xy4dist  * yRaise);
    double y4 = Point.Gety() - (xy4dist  * xRaise);
    if(ConnectPoint)
       ConnectPoint->Set(x4, y4);

    // Offset p4 <-> start point
    double x4off = x4 - xa;
    double y4off = y4 - ya;
    double d4 = sqrt(x4off*x4off + y4off*y4off);

    if(( (x4off > 0. != xOff > 0. || xOff == 0)  &&   // Connection point is BEFORE start of line
         (y4off > 0. != yOff > 0. || yOff == 0)) ||
          d4 > dist)                                  // Connection point is BEHIND end of line

    {
        if(fabs(x4 - xa) < fabs(x4 - xb) || // Point is nearer to start
           fabs(y4 - ya) < fabs(y4 - yb)) 
        {
            if(ConnectPoint)
              *ConnectPoint = Start();
            return Point.DistTo(Start());   // return offset to start
        }
        else                                // Point is nearer to end
        {
            if(ConnectPoint)
              *ConnectPoint = End();
            return Point.DistTo(End());     // return offset to end
        }
    }
     return fabs(xy4dist); // return length of perpendicular

To find the nearest out of 1,000,000 lines for a single point p, the function just must be called 1,000,000 times -- once for each single line. This needs about 379 milliseconds to execute on 2.8-GHz XEON. If for each of the 1,000,000 lines the nearest neighbor for their start and endpoint is needed, we need to repeat the single point search 1,000,000 * 2 times which results in a total runtime of (2,000,000 * 379ms) 8 days, which is unacceptable.