Closest-pair problem: Difference between revisions

And divide-and-conquer. Notice that the code has been written for brevity and to demonstrate the algorithm, not true optimization. There are further language-specific optimizations that could be applied.

return MyClosestRec(points.OrderBy(p => p.X).ToList());

public static Segment MyClosestRec(List<PointF> pointsByX)

int count = pointsByX.Count;

if (count <= 4)

return Closest_BruteForce(pointsByX);

// left and right lists sorted by X, as order retained from full list

var leftByX = pointsByX.Take(count/2).ToList();

var leftResult = MyClosestRec(leftByX);

var rightByX = pointsByX.Skip(count/2).ToList();

var rightResult = MyClosestRec(rightByX);

var result = rightResult.Length() < leftResult.Length() ? rightResult : leftResult;

// There may be a shorter distance that crosses the divider

// Thus, extract all the points within result.Length either side

var midX = leftByX.Last().X;

var bandWidth = result.Length();

var inBandByX = pointsByX.Where(p => Math.Abs(midX - p.X) <= bandWidth);

// Sort by Y, so we can efficiently check for closer pairs

var inBandByY = inBandByX.OrderBy(p => p.Y).ToArray();

int iLast = inBandByY.Length - 1;

for (int i = 0; i < iLast; i++ )

{

var pLower = inBandByY[i];

for (int j = i + 1; j <= iLast; j++)

{

var pUpper = inBandByY[j];

// Comparing each point to successivly increasing Y values

// Thus, can terminate as soon as deltaY is greater than best result

if ((pUpper.Y - pLower.Y) >= result.Length())

break;

if (Segment.Length(pLower, pUpper) < result.Length())

result = new Segment(pLower, pUpper);

}

}

return result;

Targeted Search: Similar concept to recursive divide-and-conquer above, but I think much simpler. Also, much faster in my tests. Key optimization is that if the distance along the X axis is greater than the best total length you already have, you can terminate the inner loop early.