How to sort rectangles from left to right in multiple rows?

user_18875957 0
Viewed 74

I have a set of rectangles that im getting from a process which I draw on another image. These rectangles are stored in a list which is not sorted. So I sort then by x and then by y like this:

      rect1 = rect1.OrderBy(p => p.X).ThenBy(p => p.Y).ToList();

But its not giving the sorting I want, it starts with 0 on bottom >> 1 on top >> 2 on bottom >> 3 on top....... like in this image below :

img

How to sort this to get the first line to be 0-13 and second line to be 14 to 27

Solution:

Sorting result suggested by Dmitry worked perfectly.

enter image description here

sorting algorithm c#
1 Answers

As far as I can see, you want to sort first by Y (top line first, then 2nd line etc.) and then by X (from left to right). The problem is that rectangles are not aligned perfectly and Y can slightly vary (e.g. rectangle #19 is a bit higher than rectange #21) and we can't just naively sort by Y (#19 will be the first in such an order). So far so good we should define "on the same line" and order by "lines" and then by X within each line.

Let definition "on the same line" be

rectangles A and B are on the same line if Abs(A.Y - B.Y) < B.Height

If we can use such definition the code can be:

Code:

private static IEnumerable<Rectangle> OrderByLines(IEnumerable<Rectangle> source) {
  var line = new LinkedList<Rectangle>();

  foreach (var item in source.OrderBy(r => r.Y))
    if (line.Count == 0 || (item.Y - line.Last.Value.Y) < item.Height)
      line.AddLast(item);
    else {
      foreach (var rect in line.OrderBy(rc => rc.X))
        yield return rect;

      line.Clear();
      line.AddLast(item);
    }

    foreach (var rect in line.OrderBy(rc => rc.X))
      yield return rect;
}

then

rect1 = OrderByLines(rect1).ToList();

Demo:

Random random = new Random(123); // seed to be reproducible

int width = 30;
int height = 50;
int interline = 20;
int dy = 10;
int dx = 5;

Rectangle[] demo = Enumerable
  .Range(0, 2)
  .SelectMany(row => Enumerable
     .Range(0, 10)
     .Select(col => new Rectangle(
        col * width + random.Next(-dx, dx),
        row * (height + interline) + random.Next(-dy, dy),
        width + random.Next(-dx, dx),
        height + random.Next(-dy, dy))))
  .ToArray();

var result = OrderByLines(demo)
  .ToList();

Console.Write(string.Join(Environment.NewLine, result));

Output:

{X=4,Y=8,Width=32,Height=56}
{X=32,Y=-10,Width=25,Height=42}
{X=56,Y=2,Width=34,Height=49}
{X=86,Y=-1,Width=25,Height=56}
{X=120,Y=-5,Width=25,Height=58}
{X=146,Y=-10,Width=32,Height=40}
{X=182,Y=2,Width=31,Height=57}
{X=210,Y=-8,Width=30,Height=57}
{X=242,Y=-9,Width=30,Height=41}
{X=274,Y=-6,Width=29,Height=55}
{X=4,Y=77,Width=29,Height=43}   <- second line starts
{X=32,Y=62,Width=26,Height=47}
{X=56,Y=69,Width=32,Height=43}
{X=85,Y=70,Width=33,Height=59}
{X=116,Y=74,Width=25,Height=42}
{X=148,Y=62,Width=31,Height=41}
{X=175,Y=61,Width=32,Height=42}
{X=213,Y=79,Width=34,Height=47}
{X=243,Y=64,Width=25,Height=45}
{X=270,Y=71,Width=27,Height=52}
user_23194070
Related