c# - 如何转换此分而治之代码以将一个点与点列表进行比较？

Question

我在网站上找到这段代码http://rosettacode.org/wiki/Closest-pair_problem并且我采用了 C# 版本的分而治之的方法来找到最近的一对点，但我想做的是调整它以仅用于找到离一个特定点最近的点。我在谷歌上搜索了很多，并在这个网站上搜索了一些例子，但没有一个像这样。我不完全确定要更改什么，以便它只检查列表中的一个点，而不是检查列表以找到最接近的两个点。我想让我的程序尽可能快地运行，因为它可能会搜索包含数千个点的列表以找到最接近我当前坐标点的点。

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

我在我的程序中使用这段代码来查看速度的实际差异，分而治之很容易获胜。

        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());

Answer 1

您可以将点存储在更好的数据结构中，以利用它们的位置。类似 quadtree 的东西.

您尝试使用的分而治之算法并不真正适用于此问题。