tags:

views:

134

answers:

4

I have the following code:

foreach (Tuple<Point, Point> pair in pointsCollection)
        {
            var points = new List<Point>()
                        {
                            pair.Value1,
                            pair.Value2
                        };

        }

Within this foreach, I would like to be able to determine which pair of points has the most significant length between the coordinates for each point within the pair.

So, let's say that points are made up of the following pairs:

(1) var points = new List<Point>() { new Point(0,100), new Point(100,100) };

(2) var points = new List<Point>() { new Point(150,100), new Point(200,100) };

So I have two sets of pairs, mentioned above. They both will plot a horizontal line. I am interested in knowing what the best approach would be to find the pair of points that have the greatest distance between, them, whether it is vertically or horizontally. In the two examples above, the first pair of points has a difference of 100 between the X coordinate, so that would be the point with the most significant difference. But if I have a collection of pairs of points, where some points will plot a vertical line, some points will plot a horizontal line, what would be the best approach for retrieving the pair from the set of points whose difference, again vertically or horizontally, is the greatest among all of the points in the collection?

Thanks!

Chris

+3  A: 

Use OrderBy to create an ordering based on your criteria, then select the first one. In this case order by the maximum absolute difference between the horizontal and vertical components in descending order.

EDIT: Actually, I think you should be doing this on the Tuples themselves, right? I'll work on adapting the example to that.

First, let's add an extension for Tuple<Point,Point> to calculate it's length.

 public static class TupleExtensions
 {
      public static double Length( this Tuple<Point,Point> tuple )
      {
          var first = tuple.Item1;
          var second = tuple.Item2;
          double deltaX = first.X - second.X;
          double deltaY = first.y - second.Y;
          return Math.Sqrt( deltaX * deltaX + deltaY * deltaY );
      }
}

Now we can order the tuples by their length

var max = pointCollection.OrderByDescending( t => t.Length() )
                         .FirstOrDefault();

Note: it is faster to just iterate over the collection and keep track of the maximum rather than sorting/selecting with LINQ.

Tuple<Point,Point> max = null;
foreach (var tuple in pointCollection)
{
     if (max == null || tuple.Length() > max.Length())
     {
         max = tuple;
     }
}

Obviously, this could be refactored to an IEnumerable extension if you used it in more than one place.

tvanfosson
Thanks, but I get a compilation error:The type arguments for method 'System.Linq.Enumerable.OrderByDescending<TSource,TKey>(System.Collections.Generic.IEnumerable<TSource>, System.Func<TSource,TKey>)' cannot be inferred from the usage. Try specifying the type arguments explicitly.
Chris
Here is what I entered for the code:public static Tuple<Point, Point> FindLargestPoint(IList<Tuple<Point, Point>> pointsCollection) { var max = pointsCollection.OrderByDescending((x, y) => Math.Max(Math.Abs(x.Value1 - y.Value), Math.Abs(x.Value2 - y.Value2)) ).FirstOrDefault(); return max; }
Chris
Yes, this should be done on the Tuples themselves. Thanks for your help. I'll look out for the example.
Chris
@Chris: note that my example uses the definitions of Tuple and Point from the .NET framework classes. If these are your own classes you'll need to update the properties (and can make the method a class method rather than an extension). I'm using .NET 3.5, so that's actually what I did (Tuple isn't available til .NET 4).
tvanfosson
Sorting is a huge overkill if you only want to find the max.
forki23
@forki23 - I would agree, except that `IEnumerable.Max()` doesn't take an IComparer and the default comparable on Tuple doesn't fit the requirement. In this case to use LINQ I think you must do a sort first. Of course, you could always just iterate over the list and keep track of the maximum, but that wasn't the question.
tvanfosson
+2  A: 

You'll need a function probably using the pythagorean theorem to calculate the distances

a^2 + b^2 = c^2

Where a would be the difference in Point.X, b would be the difference in Point.Y, and c would be your distance. And once that function has been written, then you can go to LINQ and order on the results.

Here's what I did. (Note: I do not have C# 4, so it's not apples to apples

private double GetDistance(Point a, Point b)
{
    return Math.Pow(Math.Pow(Math.Abs(a.X - b.X), 2) + Math.Pow(Math.Abs(a.Y - b.Y), 2), 0.5);
}

You can turn that into an anonymous method or Func if you prefer, obviously.

var query = pointlistCollection.OrderByDescending(pair => GetDistance(pair[0], pair[1])).First();

Where pointlistCollection is a List<List<Point>>, each inner list having two items. Quick example, but it works.

List<List<Point>> pointlistCollection 
    = new List<List<Point>>()
    {
        new List<Point>() { new Point(0,0), new Point(3,4)},
        new List<Point>() { new Point(5,5), new Point (3,7)}
    };

***Here is my GetDistance function in Func form.

Func<Point, Point, double> getDistance
        = (a, b)
        => Math.Pow(Math.Pow(Math.Abs(a.X - b.X), 2) + Math.Pow(Math.Abs(a.Y - b.Y), 2), 0.5);

var query = pointlistCollection.OrderByDescending(pair => getDistance(pair[0], pair[1])).First();
Anthony Pegram
Note that if you are time constrained and all you care about is the *largest* distance then you don't need to take the square root. The largest distance is also going to have the largest squared distance.
Eric Lippert
Good point. Also note that the Math.Abs calls are superfluous since I'm squaring the difference anyway. Beyond that, my function is good for reuse when and if you ever decide to display the difference.
Anthony Pegram
A: 

tvanfosson's answer is good, however I would like to suggest a slight improvement : you don't actually need to sort the collection to find the max, you just have to enumerate the collection and keep track of the maximum value. Since it's a very common scenario, I wrote an extension method to handle it :

public static class EnumerableExtensions
{
    public static T WithMax<T, TValue>(this IEnumerable<T> source, Func<T, TValue> selector)
    {
        var max = default(TValue);
        var withMax = default(T);
        bool first = true;
        foreach (var item in source)
        {
            var value = selector(item);
            int compare = Comparer<TValue>.Default.Compare(value, max);

            if (compare > 0 || first)
            {
                max = value;
                withMax = item;
            }
            first = false;
        }
        return withMax;
    }
}

You can then do something like that :

Tuple<Point, Point> max = pointCollection.WithMax(t => t.Length());
Thomas Levesque
@downvoter, care to give an explanation ??
Thomas Levesque
A: 

As commented above: Don't sort the list in order to get a maximum.

public static double Norm(Point x, Point y)
{
  return Math.Sqrt(Math.Pow(x.X - y.X, 2) + Math.Pow(x.Y - y.Y, 2));
}

Max() needs only O(n) instead of O(n*log n)

pointsCollection.Max(t => Norm(t.Item1, t.Item2));
forki23
The question stated that he was interested in retrieving the pair with the greatest distance, not merely the value of the greatest distance.
Anthony Pegram
Sorry I was looking for something like MaxBy(). But seems it's only in F# not directly in LINQ.
forki23