How can I convert this divide and conquer code to compare one point to a list of points?

I found this code on the website http://rosettacode.org/wiki/Closest-pair_problem and I adopted the C# version of the divide and conquer method of finding the closest pair of points but what I am trying to do is adapt it for use to only find the closest point to one specific point. I have googled quite a bit and searched this website to find examples but none quite like this. I am not entirely sure what to change so 开发者_如何学运维that it only checks the list against one point rather than checking the list to find the two closest. I'd like to make my program operate as fast as possible because it could be searching a list of several thousand Points to find the closest to my current coordinate Point.

public class Segment
{
    public Segment(PointF p1, PointF p2)
    {
        P1 = p1;
        P2 = p2;
    }

    public readonly PointF P1;
    public readonly PointF P2;

    public float Length()
    {
        return (float)Math.Sqrt(LengthSquared());
    }

    public float LengthSquared()
    {
        return (P1.X - P2.X) * (P1.X - P2.X)
            + (P1.Y - P2.Y) * (P1.Y - P2.Y);
    }
}

    public static Segment Closest_BruteForce(List<PointF> points)
    {
        int n = points.Count;
        var result = Enumerable.Range(0, n - 1)
            .SelectMany(i => Enumerable.Range(i + 1, n - (i + 1))
                .Select(j => new Segment(points[i], points[j])))
                .OrderBy(seg => seg.LengthSquared())
                .First();

        return result;
    }

    public static Segment MyClosestDivide(List<PointF> points)
    {
        return MyClosestRec(points.OrderBy(p => p.X).ToList());
    }

    private 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;

                Segment segment = new Segment(pLower, pUpper);
                if (segment.Length() < result.Length())
                    result = segment;// new Segment(pLower, pUpper);
            }
        }

        return result;
    }

I used this code in my program to see the actual difference in speed and divide and conquer easily wins.

        var randomizer = new Random(10);
        var points = Enumerable.Range(0, 10000).Select(i => new PointF((float)randomizer.NextDouble(), (float)randomizer.NextDouble())).ToList();
        Stopwatch sw = Stopwatch.StartNew();
        var r1 = Closest_BruteForce(points);
        sw.Stop();
        //Debugger.Log(1, "", string.Format("Time used (Brute force) (float): {0} ms", sw.Elapsed.TotalMilliseconds));
        richTextBox.AppendText(string.Format("Time used (Brute force) (float): {0} ms", sw.Elapsed.TotalMilliseconds));
        Stopwatch sw2 = Stopwatch.StartNew();
        var result2 = MyClosestDivide(points);
        sw2.Stop();
        //Debugger.Log(1, "", string.Format("Time used (Divide & Conquer): {0} ms", sw2.Elapsed.TotalMilliseconds));
        richTextBox.AppendText(string.Format("Time used (Divide & Conquer): {0} ms", sw2.Elapsed.TotalMilliseconds));
        //Assert.Equal(r1.Length(), result2.Length());

You can store the points in a better data structure that takes advantage of their position. Something like a quadtree.

The divide and conquer algorithm that you are trying to use doesn't really apply to this problem.

Don't use this algorithm at all, just go through the list one at a time comparing the distance to your reference point and at the end return the point that was the closest. This will be O(n).

You can probably add some extra speed ups but this should be good enough.

I can write some example code if you want.

You're mixing up two different problems. The only reason divide and conquer for the closest pair problem is faster than brute force is that it avoids comparing every point to every other point, so that it gets O(n log n) instead of O(n * n). But finding the closest point to just one point is just O(n). How can you find the closest point in a list of n points, while examining less than n points? What you're trying to do doesn't even make sense.

I can't say why your divide and conquer runs in less time than your brute force; maybe the linq implementation runs slower. But I think you'll find two things: 1) Even if, in absolute terms, your implementation of divide and conquer for 1 point runs in less time than your implementation of brute force for 1 point, they still have the same O(n). 2) If you just try a simple foreach loop and record the lowest distance squared, you'll get even better absolute time than your divide and conquer - and, it will still be O(n).

public static float LengthSquared(PointF P1, PointF P2)
{
    return (P1.X - P2.X) * (P1.X - P2.X)
        + (P1.Y - P2.Y) * (P1.Y - P2.Y);
}

If, as your question states, you want to compare 1 (known) point to a list of points to find the closest then use this code.

public static Segment Closest_BruteForce(PointF P1, List<PointF> points)
{
    PointF closest = null;
    float minDist = float.MaxValue;
    foreach(PointF P2 in points) 
    {
       if(P1 != P2) 
       {
           float temp = LengthSquared(P1, P2);
           if(temp < minDist) 
           {
               minDist = temp;
               closest = P2;
           }
       }
    }
    return new Segment(P1, closest);
}

However, if as your example shows, you want to find the closest 2 points from a list of points try the below.

public static Segment Closest_BruteForce(List<PointF> points)
{
    PointF closest1;
    PointF closest2;
    float minDist = float.MaxValue;
    for(int x=0; x<points.Count; x++)
    {
        PointF P1 = points[x];
        for(int y = x + 1; y<points.Count; y++)
        {
            PointF P2 = points[y];
            float temp = LengthSquared(P1, P2);
            if(temp < minDist) 
            {
               minDist = temp;
               closest1 = P1;
               closest2 = P2;
            }
        }
    }
    return new Segment(closest1, closest2);
}

note the code above was written in the browser and may have some syntax errors.

EDIT Odd... is this an acceptable answer or not? Down-votes without explanation, oh well.