如何从 2 List<Point> 中获取最近的 2 Points

Question

我有 2 个点列表：

        var listA = new List<Point>();
        listA.Add(new Point(10, 1));
        listA.Add(new Point(5, 5));
        listA.Add(new Point(15, 35));

        var listB = new List<Point>();
        listB.Add(new Point(1, 1));
        listB.Add(new Point(5, 4));
        listB.Add(new Point(35, 15));

现在我想做这样的事情：

        getClosesPoints(listA,listB, Out pointA, Out pointB);

我目前可以再次检查列表 1 点

        private int NearestPoint(Point srcPt, List<Point> lookIn)
        {
            if (lookIn.Count == 1)
                return 0;

            KeyValuePair<double, int> smallestDistance = new KeyValuePair<double, int>();

            for (int i = 0; i < lookIn.Count; i++)
            {
                double distance = Math.Sqrt(Math.Pow(srcPt.X - lookIn[i].X, 2) + Math.Pow(srcPt.Y - lookIn[i].Y, 2));

                if (i == 0)
                    smallestDistance = new KeyValuePair<double, int>(distance, i);
                else if (distance < smallestDistance.Key)
                        smallestDistance = new KeyValuePair<double, int>(distance, i);
            }

            Console.WriteLine("smallest Distance:" + smallestDistance.Key);
            return smallestDistance.Value;
        }

但我不确定如何扩展此代码以检查 2 个列表。

Answer 1

如果您 return 来自您的方法的整个键值对，您将能够使用一个简单的循环从一个点扩展到整个列表：

KeyValuePoint<double,int> best = new KeyValuePair<double,int>(double.MaxValue, -1);
int best2 = -1;
for (int i = 0 ; i != list2.Count ; i++) {
    Point pt = list2[i];
    KeyValuePoint<double,int> current = NearestPoint(pt, list1);
    if (current.Key < best.Key) {
        best = current;
        best2 = i;
    }
}

最后，best.Key距离最短，best.Value有list1中点的索引，best2有list1中点的索引list2.

Answer 2

我假设您想要在两个列表中找到最近的两个点，其中一个点在一个列表中，另一个点在另一个列表中。

您可以使用内部循环和外部循环来解决这个问题。外层循环遍历第一个列表中的所有点；对于这些点中的每一个，您都使用内部循环将其与第二个列表中的所有点进行比较。

这样你就不需要记住所有的距离；你只需要记住到目前为止找到的两个最近点之间的距离，以及到目前为止最近的点本身。

您还可以创建一个简单的小 class 来 return 最近的两点，而不是 return 通过 out 参数计算结果。为方便起见，您可以向此 class 添加一个 Distance() 函数，这样您就不需要存储实际距离。（但是，如果您经常使用此值，那么您可能希望将距离缓存在本地字段中，而不是每次都计算它。）

最后，FindClosestPoints() 方法的参数可以是 IEnumerable<Point> 而不是 List<Point>，这允许您将它用于更多的集合类型。

将所有这些放在一起得到类似这样的东西（一个可编译的控制台应用程序）：

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Demo
{
    // Class just used to return the result from FindClosestPoints()

    public sealed class ClosestPoints
    {
        public ClosestPoints(Point p1, Point p2)
        {
            _p1 = p1;
            _p2 = p2;
        }

        public Point P1 { get { return _p1; } }
        public Point P2 { get { return _p2; } }

        public double Distance()
        {
            double dx = P1.X - P2.X;
            double dy = P1.Y - P2.Y;

            return Math.Sqrt(dx*dx + dy*dy);
        }

        private readonly Point _p1;
        private readonly Point _p2;
    }

    public static class Program
    {
        public static void Main()
        {
            var listA = new List<Point>();
            listA.Add(new Point(10, 1));
            listA.Add(new Point(5, 5));
            listA.Add(new Point(15, 35));

            var listB = new List<Point>();
            listB.Add(new Point(1, 1));
            listB.Add(new Point(5, 4));
            listB.Add(new Point(35, 15));

            var answer = FindClosestPoints(listA, listB);

            Console.WriteLine("Closest points are {0} and {1}", answer.P1, answer.P2);
        }

        public static ClosestPoints FindClosestPoints(IEnumerable<Point> seq1, IEnumerable<Point> seq2)
        {
            double closest = double.MaxValue;
            ClosestPoints result = null;

            foreach (var p1 in seq1)
            {
                foreach (var p2 in seq2)
                {
                    double dx = p1.X - p2.X;
                    double dy = p1.Y - p2.Y;

                    double distance = dx*dx + dy*dy;

                    if (distance >= closest)
                        continue;

                    result = new ClosestPoints(p1, p2);
                    closest = distance;
                }
            }

            return result;
        }
    }
}

Answer 3

我们称这两组点为S1和S2。令 p1 为 S1 的迭代器，p2 为 S2 的迭代器。让 valueAt 成为一个函数，它告诉迭代器位置（如 p1 或 p2）的值。设 dist 是计算两点之间距离的函数。并且，设 dmin 为保持两点之间距离的变量。

假设这两个集合也可以包含负值，我提出以下逻辑：

sort S1 and S2
if valueAt (p1) < valueAt (p2)
{ d = dist (p1, p2 ); if ( dmin > dist ( p1, p2 ) ) { dmin = dist (p1, p2); record p1 and p2 as closest; }
increment p1;
}
if valueAt (p1) > valueAt (p2)
{ d = dist (p1, p2 ); if ( dmin > dist ( p1, p2 ) ) { dmin = dist (p1, p2); record p1 and p2 as closest; }
increment p2;
}
if valueAt (p1) == valueAt (p2)
{ record p1 and p2 as closest; }

如何从 2 List<Point> 中获取最近的 2 Points

How to get the closest 2 Points from 2 List<Point>

c#

algorithm

list

point