1

I'm looking for an algorthm for sorting location points (latitude and longitude) from west to east and south to north.

When sorting, the points should be sorted starting in the west and south. When two points are compared, the longitude is compared first. The greater value (more west) point is higher in the list. If the two points have the same longitude, unlikely but possible, the latitudes of the two points are compared. The lowest value (more south) is placed higher in the list.

Does this algorthm exist somewhere? Maybe in C#?

ps- these calculations will be limited to points within the continental United States. There will be no negative latitude / longitude values.

Michael Petrotta
  • 59,888
  • 27
  • 145
  • 179
DenaliHardtail
  • 27,362
  • 56
  • 154
  • 233
  • 3
    It's not clear to me why this would require anything more sophisticated than the ordinary built-in sorting functions in the .NET Framework (e.g. `List.Sort`, `Enumerable.OrderBy`.) The comparison function for the sort would presumably compare first the longitude, and then the latitude, just as you described. – mqp Apr 25 '11 at 17:33
  • Check out the second answer here: http://stackoverflow.com/questions/289010/c-list-sort-by-x-then-y . Alternatively, define your own comparison function and pass that to any standard sorting algorithm. – ProdigySim Apr 25 '11 at 17:35
  • I would know how to do it in php, or try looking at LINQ – Jess Apr 27 '11 at 03:17

2 Answers2

6
using System.Linq;

var sortedPoints = points.OrderByDescending(p => p.Longitude).ThenBy(p => p.Latitude);
Domenic
  • 110,262
  • 41
  • 219
  • 271
3

The algorithm doesn't exist out-of-the box in .NET (C# is a language and doesn't generally implement algorithms, you will typically find it in the .NET Base Class Library).

However, you could easily create a Coordinates structure/class with Latitude/Longitude properties (each as a double, I take it) and then implement IComparable<T>.

The implementation would then look something like this:

public class Coordinates : IComparable<Coordinates>
{
    public double Latitude { get; set; }
    public double Longitude { get; set; }

    public int CompareTo(Coordinates other)
    {
        // If the other instance is null, assume that
        // it is at 0,0?  You need to make that determination.
        if (other == null) return 1;

        // Compare longitude (double implements
        // IComparable<double>.
        int comparison = Longitude.CompareTo(other.Longitude);

        // If not 0, return the value.
        if (comparison <> 0) return comparison;

        // Compare latitude.  Inverse the result, as the more
        // south point (closer to 0) is greater.
        // Just return the value, if they are different, the
        // comparison value will be correct, if they are the
        // same, then comparison will be 0.
        return -Latitude.CompareTo(other.Latitude);
    }
}

Now, you can populate instances of these, place them in an array and pass it to the static Sort method on the Array class. The Sort method will use the IComparable<T> implementation to sort the array.

Or you can place them in a List<T> (probably easier, since you might not know the number of elements beforehand) and then call the Sort method on the instance; it too will use the IComparable<T> implementation to sort itself.

You also mentioned two points being the same. Since Latitude and Longitude are represented as a double, you run the risk of floating point errors. If you want to mitigate these errors, you can easily change the property to a decimal (which guarantees precision, up to a certain point); this way, you will guarantee precision, and it implements IComparable<decimal>, which means that the implementation of IComparable<Coordinates> will just work with the switch.

casperOne
  • 73,706
  • 19
  • 184
  • 253