Closest-pair problem: Difference between revisions

Line 264:

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.

<lang csharp>~~Segment Closest_Recursive(List<PointF> points)~~

public static Segment MyClosestDivide(List<PointF> points)

{

if (points.~~Count~~() < 4) ~~return Closest_BruteForce(points~~.ToList());

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

}

public static Segment MyClosestRec(List<PointF> pointsByX)

int split = points.Count() / 2;

{

var ordered = points.OrderBy(point => point.X);

int count = pointsByX.Count;

⚫

var ~~pointsOnLeft~~ = ~~ordered~~.Take(~~split~~).ToList();

if (count <= 4)

⚫

var ~~pointsOnRight~~ = ~~ordered~~.Skip(~~split~~).ToList();

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 leftMin = Closest_Recursive(pointsOnLeft);

{

float leftDist = leftMin.Length();

var pUpper = inBandByY[j];

var rightMin = Closest_Recursive(pointsOnRight);

float rightDist = rightMin.Length();

// Comparing each point to successivly increasing Y values

float minDist = Math.Min(leftDist, rightDist);

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

⚫

var ~~xDivider~~ = ~~pointsOnLeft~~.Last().X;

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

var closeY = pointsOnRight.TakeWhile(point => point.X - xDivider < minDist).OrderBy(point => point.Y);

break;

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

var crossingPairs = pointsOnLeft.SkipWhile(point => xDivider - point.X > minDist)

result = new Segment(pLower, pUpper);

.SelectMany(p1 => closeY.SkipWhile(i => i.Y < p1.Y - minDist)

}

.TakeWhile(i => i.Y < p1.Y + minDist)

}

.Select(p2 => new Segment( p1, p2 )));

return result;

return crossingPairs.Union( new [] { leftMin, rightMin })

}

.OrderBy(segment => segment.Length()).First();

}</lang>

</lang>

However, the difference in speed is still remarkable.

<lang csharp>var randomizer = new Random(10);

var points = Enumerable.Range( 0, 10000).Select( i => new PointF( (float)randomizer.NextDouble(), (float)randomizer.NextDouble())).ToList();