sort list of points by distance in .NET

Question

I need to sort a list of points by distance.

So for e.g.

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

(assuming that geometrically [1,2] and [2,4] are nearest & [2,4] & [5,10] are nearest.

I need them to sort it so they are ordered by distance i.e. on the geometrical graph, point a is nearest to point b , point b is nearest to c and so on.

Any idea?

Edit: Code example

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


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

let say my points list is getting populated in random order (not by geometrical distance). So points would look something like...

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

Now my charting control just take the first & second point and draw a line between them. Which means it does not care which geometrical order is it in. If I simply supply the "points" list as above its going to draw lines between each points and from charting point of view it would not look correct as they would be "zig-zag".

To make sure the charting control draws a straight line (& and not zig-zag) I have to pass the points in the right order which would look something like ...

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

So my question is how to achieve this.

Note: Changing chart control is not an option here.

Thanks

Answer 1

The code first takes the nearest point to (0, 0) at the '0' index then start sorting the points by distance from the last spotted point..

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