Anonymous user
Closest-pair problem: Difference between revisions
→{{header|C sharp|C#}}
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>
public static Segment MyClosestDivide(List<PointF> points)
{
return
}
public static Segment MyClosestRec(List<PointF> pointsByX)
{
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 leftResult = MyClosestRec(leftByX);
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 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
▲ var xDivider = pointsOnLeft.Last().X;
if ((pUpper.Y - pLower.Y) >= result.Length())
break;
if (Segment.Length(pLower, pUpper) < result.Length())
result = new Segment(pLower, pUpper);
}
}
return result;
}
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();
| |||