如何使用LINQ和C#找到离0,0点最近的点

Question

我有一个点列表(List)：

• 7,43
• 7,42
• 6,42
• 5,42
• 6,43
• 5,43

我想使用LINQ表达式来获取最靠近0,0的点。例如-对于这个列表，我期望得到的值是5,42。

如何使用LINQ查找距离0,0最近的点？

- Borysław Bobulski

---

请尝试对您的列表进行排序。 - animaonline

“closest” 是使用欧几里得距离定义的吗？即从 x, y 到 0,0 的距离是 sqrt(x^2 + y^2) 吗？ - vlad

最接近的定义是什么？是从（0,0）点开始的字面线性距离吗？ - David W

points = points.OrderBy(p => p.X).ThenBy(p => p.Y).ToList()。 - Mathew Thompson

@mattytommo，您认为[0,2000]比[1,0]更接近于[0,0]吗？ - Servy

@Servy 不，那只是一次猜测，这就是为什么它是一条评论。 - Mathew Thompson

Answer 1

以下代码可以在不对整个列表进行昂贵的排序的情况下找到具有最低L^2范数（二维空间中“距离”的最常见定义）的点：

var closestToOrigin = points
    .Select(p => new { Point = p, Distance2 = p.X * p.X + p.Y * p.Y })
    .Aggregate((p1, p2) => p1.Distance2 < p2.Distance2 ? p1 : p2)
    .Point;

- Rawling

---

如果我们关心性能，那么你的解决方案是不错的，但是在我的更新帖子中，你可以看到更好的解决方案。 - Hamlet Hakobyan

@Hamlet，你为什么说你的更好呢？我看到了一些权衡（匿名对象创建与第二次距离计算），但它的核心基本上是这个答案的克隆。 - Rawling

Answer 2

试试这个：

List<Point> points = new List<Point>();
// populate list
var p = points.OrderBy(p => p.X * p.X + p.Y * p.Y).First();

更快的解决方案：

var p = points.Aggregate(
            (minPoint, next) =>
                 (minPoint.X * minPoint.X + minPoint.Y * minPoint.Y)
                 < (next.X * next.X + next.Y * next.Y) ? minPoint : next);

- Hamlet Hakobyan

---

当你只想要最小值时，进行整体排序是很昂贵的。（如果微软提供了一个接受IOrderedEnumerable的First重载，那就不会有问题了！） - Rawling

实际上，按平方距离排序就可以了 :). 没有必要进行sqrt运算。此外，正如@Rawling所指出的那样 - Enumerable.Min扩展方法(http://msdn.microsoft.com/en-us/library/bb359972.aspx)比排序更高效一些。 - Ani

Answer 3

Rawling的解决方案确实更简短，但这里有一个替代方案

// project every element to get a map between it and the square of the distance
var map = pointsList                                            
    .Select(p => new { Point = p, Distance = p.x * p.x + p.y * p.y });

var closestPoint = map // get the list of points with the min distance
    .Where(m => m.Distance == map.Min(t => t.Distance)) 
    .First() // get the first item in that list (guaranteed to exist)
    .Point; // take the point

如果您需要找到与点0,0距离最近的所有元素，只需删除First并执行Select(p => p.Point)以获取点（而不是映射）即可。

- vlad

---

@Rawling 那个额外的 log(n) 真是致命的。我已经更新了我的答案。 - vlad

@Rawling已经修复了，不过我更喜欢你的解决方案。 - vlad

如果你想的话，这个可以让你得到最接近的联合点，而我的则很难/不可能适应这样做 :) - Rawling

Answer 4

作为另一种方法，你可以考虑将IEnumerable.MinBy()和IEnumerable.MaxBy()的实现添加到标准库中。 如果你已经有了它们，代码就变得非常简单：

var result = points.MinBy( p => p.X*p.X + p.Y*p.Y );

Jon Skeet提供了MinBy和MaxBy的良好实现。

他在这里讲述了它：如何使用LINQ选择具有最小或最大属性值的对象

从那里的链接已经过时，但最新版本在这里：

http://code.google.com/p/morelinq/source/browse/MoreLinq/MinBy.cs

http://code.google.com/p/morelinq/source/browse/MoreLinq/MaxBy.cs

这里是一个完整的样例。显然，这是用大锤砸坚果的做法，但我认为这些方法足够有用，可以包含在您的标准库中：

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

namespace Demo
{
    public static class EnumerableExt
    {
        public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector, IComparer<TKey> comparer)
        {
            using (IEnumerator<TSource> sourceIterator = source.GetEnumerator())
            {
                if (!sourceIterator.MoveNext())
                {
                    throw new InvalidOperationException("Sequence was empty");
                }

                TSource min = sourceIterator.Current;
                TKey minKey = selector(min);

                while (sourceIterator.MoveNext())
                {
                    TSource candidate = sourceIterator.Current;
                    TKey candidateProjected = selector(candidate);

                    if (comparer.Compare(candidateProjected, minKey) < 0)
                    {
                        min    = candidate;
                        minKey = candidateProjected;
                    }
                }

                return min;
            }
        }

        public static TSource MinBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector)
        {
            return source.MinBy(selector, Comparer<TKey>.Default);
        }
    }

    public static class Program
    {
        static void Main(string[] args)
        {
            List<Point> points = new List<Point>
            {
                new Point(7, 43),
                new Point(7, 42),
                new Point(6, 42),
                new Point(5, 42),
                new Point(6, 43),
                new Point(5, 43)
            };

            var result = points.MinBy( p => p.X*p.X + p.Y*p.Y );

            Console.WriteLine(result);
        }
    }
}

- Matthew Watson