.NET 中按距离对点列表进行排序

Question

我需要按距离对点列表进行排序。

所以对于例如

input : [[1,2],[5,10],[2,4]...]
output : [[1,2],[2,4],[5,10]...]  

（假设几何上 [1,2] 和 [2,4] 最接近，并且 [2,4] 和 [5,10] 最接近。

我需要他们对其进行排序，以便它们按距离排序，即在几何图上，点 a 最接近点 b ，点 b 最接近 c 等等。

任何想法？

编辑：代码示例

public class Point
{
   public double X {get;set;}
   public double Y {get;set;}
}


List<Point> points = new List<Point>();

假设我的点列表是按随机顺序填充的（而不是按几何距离）。所以点看起来像......

点 ~ [[1,2],[5,10],[2,4]...]

现在我的图表控件只需获取第一点和第二点并在它们之间画一条线。这意味着它不关心它的几何顺序。如果我简单地提供上面的“点”列表，它将在每个点之间绘制线条，从图表的角度来看，它看起来不正确，因为它们将是“之字形”曲折”。

为了确保图表控件绘制一条直线（而不是之字形），我必须以正确的顺序传递点，看起来像......

destination points ~ [[1,2],[2,4],[5,10]...]  

所以我的问题是如何实现这一目标。

注意：此处无法更改图表控件。

谢谢

Answer 1

该代码首先在“0”索引处获取距离 (0, 0) 最近的点，然后开始按距最后发现的点的距离对点进行排序。

C＃：

    List<Point> SortByDistance(List<Point> lst)
    {
        List<Point> output = new List<Point>();
        output.Add(lst[NearestPoint(new Point(0, 0), lst)]);
        lst.Remove(output[0]);
        int x = 0;
        for (int i = 0; i < lst.Count + x; i++)
        {
            output.Add(lst[NearestPoint(output[output.Count - 1], lst)]);
            lst.Remove(output[output.Count - 1]);
            x++;
        }
        return output;
    }

    int NearestPoint(Point srcPt, List<Point> lookIn)
    {
        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);
                }
            }
        }
        return smallestDistance.Value;
    }

VB.Net：

Function SortByDistance(ByVal lst As List(Of Point)) As List(Of Point)
    Dim out As New List(Of Point)
    out.Add(lst(NearestPoint(New Point(0, 0), lst)))
    lst.Remove(out(0))
    Dim x As Integer = 0
    For i As Integer = 0 To lst.Count - 1 + x
        out.Add(lst(NearestPoint(out(out.Count - 1), lst)))
        lst.Remove(out(out.Count - 1))
        x += 1
    Next
    Return out
End Function

Function NearestPoint(ByVal srcPt As Point, ByVal lookIn As List(Of Point)) As Integer
    Dim smallestDistance As KeyValuePair(Of Double, Integer)
    For i As Integer = 0 To lookIn.Count - 1
        Dim distance As Double = Math.Sqrt(Math.Pow(srcPt.X - lookIn(i).X, 2) + Math.Pow(srcPt.Y - lookIn(i).Y, 2))
        If i = 0 Then
            smallestDistance = New KeyValuePair(Of Double, Integer)(distance, i)
        Else
            If distance < smallestDistance.Key Then
                smallestDistance = New KeyValuePair(Of Double, Integer)(distance, i)
            End If
        End If
    Next
    Return smallestDistance.Value
End Function