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

Answer 2

I think you want this, Dijkstra's algorithm. There is a c# project here.

What follows is unmodified code from that link

class Dijkstra
    {        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

Answer 3

In a graph, a set of points (x1,y1), (x2,y2), (x3,y3)...(xn,yn) should be ordered on the value of any one co ordinate because it is not the nearest point that should come next in order, but the one with nearest x or y (whichever axis is taken as reference) co-ordinate value. So, the array to pass for charting should be:

var orderedPoints=points.OrderBy(p=>p.X);

In the above image, the length of the line L1 is greater than L2. But the point P2 and not P3 should be come after P1 since P2.X<P3.X