How to group in Linq based on previous Value

Question

I want to group a pointcloud based on 2 conditions

1. simple on Y so I wrote pointcloudH.GroupBy(KVP => KVP.Value.Y) where KVP is an KeyValuePair<string,System.Drawing.Point>

2. and now I want to group it also by X if X == (previousX + 1) as far as I know I should us ThenBy() but what do I have to write between the brackets?

and here an example for a better illustration what I want to achieve

Sample pointcloud

(x|y) (1|1),(2|1),(4|1),(1|2),(2|3),(3|3),(4|3),(5|8),(9|10)

after step 1. it looks like this

group1 (1|1),(2|1),(4|1)
group2 (1|2)
group3 (2|3),(3|3),(4|3)
group4 (5|8)
group5 (9|10)

after step 2. it should look like this

group1 (1|1),(2|1)
group2 (4|1)
group3 (1|2)
group4 (2|3),(3|3),(4|3)
group5 (5|8)
group6 (9|10)

current code

var Hgroup = pointcloudH.OrderBy(KVP => KVP.Value.Y) // order by Y
                        .GroupBy(KVP => KVP.Value.Y) // groub by Y
                        .ThenBy(KVP => KVP.Value.X); // group by X ???

Answer 1

I don't think LINQ is the best tool for this kind of job, but it can be achieved. The important part is to think of the relation between your Point.X and the index of the relative Point in the Point.Y group. Once you realize you want to group them by Point.X - Index, you can do:

var Hgroup = pointcloudH.OrderBy(p => p.Y)
                        .GroupBy(p => p.Y)
                        .SelectMany(yGrp =>
                                    yGrp.Select((p, i) => new {RelativeIndex = p.X - i, Point = p})
                                        .GroupBy(ip => ip.RelativeIndex, ip => ip.Point)
                                        .Select(ipGrp => ipGrp.ToList()))
                        .ToList();

Note that this will probably perform worst than a regular iterative algorithm. My pointcloudH is an array, but you can just change the lambda to reflect your own list. Also, remove the ToList() if you want to defer execution. This was to ease the result inspection in the debugger.

If you want to group all points in a Point.Y group regardless of their index (ie order by Point.X as well. Add ThenBy(p => p.X) after the first OrderBy clause.

Answer 2

Your problem cannot be solved by doing 2 separate group by clauses. I have created a little sample which should work for your problem. These are the key things that are happening in the code:

• Construct 'mirror' array and insert a copy of the first item at index 0, this is used to keep track of the previous point

• Create a variable that is incremented whenever a 'chain' is broken. This is whenever the next value is not equal to the previous + 1. This way we can group by an unique key per 'chain'.

  class Program { public struct Point { public static Point Create(int x, int y) { return new Point() { X = x, Y = y }; }

      public int X { get; set; }
      public int Y { get; set; }
  
      public override string ToString()
      {
          return string.Format("({0}|{1})", X, Y);
      }
  }
  
  static void Main(string[] args)
  {
      //helper to avoid to much keystrokes :)
      var f = new Func<int, int, Point>(Point.Create);
      //compose the point array
      //(1|1),(2|1),(4|1),(1|2),(2|3),(3|3),(4|3),(5|8),(9|10)
      var points = new[] { f(1, 1), f(2, 1), f(4, 1), f(1, 2), f(2, 3), f(3, 3), f(4, 3), f(5, 8), f(9, 10) }.OrderBy(p => p.Y).ThenBy(p => p.X);;
  
      //create a 'previous point' array which is a copy of the source array with a item inserted at index 0
      var firstPoint = points.FirstOrDefault();
      var prevPoints = new[] { f(firstPoint.X - 1, firstPoint.Y) }.Union(points);
  
      //keep track of a counter which will be the second group by key. The counter is raised whenever the previous X was not equal
      //to the current - 1
      int counter = 0;
  
      //the actual group by query
      var query = from point in points.Select((x, ix) => new { current = x, prev = prevPoints.ElementAt(ix) })                        
                  group point by new { point.current.Y, prev = (point.prev.X == point.current.X - 1 ? counter : ++counter) };
  
      //method chaining equivalent
      query = points.Select((x, ix) => new { current = x, prev = prevPoints.ElementAt(ix) })
                    .GroupBy(point => new { point.current.Y, prev = (point.prev.X == point.current.X - 1 ? counter : ++counter) });
  
      //print results
      foreach (var item in query)
          Console.WriteLine(string.Join(", ", item.Select(x=> x.current)));            
  
      Console.Read();
  }
  

  }