Anonymous user
Closest-pair problem: Difference between revisions
→{{header|C sharp|C#}}
Line 261:
return result;
}</lang>
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.
Line 307 ⟶ 308:
<lang>Time used (Brute force) (float): 145731.8935 ms
Time used (Divide & Conquer): 1139.2111 ms</lang>
Non Linq Brute Force:
<lang csharp>
Segment Closest_BruteForce(List<PointF> points)
{
Trace.Assert(points.Count >= 2);
int count = points.Count;
// Seed the result - doesn't matter what points are used
// This just avoids having to do null checks in the main loop below
var result = new Segment(points[0], points[1]);
var bestLength = result.Length();
for (int i = 0; i < count; i++)
for (int j = i + 1; j < count; j++)
if (Segment.Length(points[i], points[j]) < bestLength)
{
result = new Segment(points[i], points[j]);
bestLength = result.Length();
}
return result;
}</lang>
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.
<lang csharp>
Segment Closest(List<PointF> points)
{
Trace.Assert(points.Count >= 2);
int count = points.Count;
points.Sort((lhs, rhs) => lhs.X.CompareTo(rhs.X));
var result = new Segment(points[0], points[1]);
var bestLength = result.Length();
for (int i = 0; i < count; i++)
{
var from = points[i];
for (int j = i + 1; j < count; j++)
{
var to = points[j];
var dx = to.X - from.X;
if (dx >= bestLength)
{
break;
}
if (Segment.Length(from, to) < bestLength)
{
result = new Segment(from, to);
bestLength = result.Length();
}
}
}
return result;
}
</lang>
=={{header|D}}==
| |||