linq найти прямоугольники, расположенные друг над другом

Question

Я использую linqtoxml для анализа существующего XML-файла, который в основном имеет форму

<Projects>
  <Project ProjectName="name1">
    <ObjectType1List>
      <ObjectType1 ProjectName="name1" Idx="1">
        <Location Top="104" Left="32" Height="64" Wdth="128" />
        ...
      </ObjectType1>

      <ObjectType1 ProjectName="name1" Idx="2">
        ...
      </ObjectType1>
    </ObjectType1List>

    <ObjectType2List>
      ...
    </ObjectType2List>
  </Project>

  <Project Name ="name2">
  </Project>
  ...
</Project>

Где в файле несколько проектов и около 10 типов канонических объектов внутри проекта - хотя каждый проект может иметь или не иметь все различные типы объектов. Но там, где проект содержит тип объекта, будет конечный список экземпляров этого типа объекта.

Теперь я пытаюсь найти все объекты данного типа объектов, которые расположены друг над другом (и я знаю, что меня будут интересовать только два типа объектов, и я предполагаю, что только объекты одного типа будут накладываться друг на друга). Но объекты были нарисованы и размещены вручную, поэтому я не могу предположить, что такие объекты имеют абсолютно одинаковые размеры или положение - но я предполагаю, что они будут совпадать в пределах некоторой разницы в максимальном размере aribtray, поэтому у меня возникло такое чувство сканировать и группировать объекты по нечеткому требованию в зависимости от расположения объекта в центре.

И запрос «могу ли я тоже иметь пони» заключается в том, что мне интересно видеть только один объект поверх другого. В списке данного типа объектов может быть группа объектов, расположенных друг над другом, а также группа других объектов, которые не перекрываются - я не хочу знать об этих последних объектах.

Таким образом, для файла, загруженного XDocument, я думаю о двухпроходном подходе (и я не уверен, что у меня правильный синтаксис для Top et al):

  var objects = from object in xdoc.Descendants()
    where object.Name = "ObjectType1" or object.Name = "ObjectType2" 
    select new
    {
      Project = object.Attribute("ProjectName").Value.ToString(),
      ObjectType = object.Name,
      Index = (int)object.Attribute("Idx").Value,
      Top = (int)object.Element("Location").Attribute("Top").Value,
      Left = (int)object.Element("Location").Attribute("Left").Value,
      Width = (int)object.Element("Location").Attribute("Width").Value,
      Height = (int)object.Element("Location").Attribute("Height").Value
    };


  var stacked = from object in objects
   group object by ???????

Это ??????? немного, что я не знаю, как писать. Я знаю, что хочу сгруппировать по Project и ObjectType, а затем по некоторой математической функции Top, Left, Width и Height. Это двойная проблема, так как я знаю, что я не понимаю несколько группировок в linq, и тогда сравнение объектов будет выглядеть примерно так:

abs(obj1.Left + obj1.Width/2 - obj2.Left - obj2.Width/2)<epsilon &&
abs(obj1.Top  + obj1.Height/2 - obj2.Top - obj2.Height/2)<epsilon

Так какие предложения?

Обратите внимание, что, хотя мой текущий проект - .net 3.5, у меня нет ограничений, которые бы помешали мне перейти на 4.0

Edit1

Из вопросов, поднятых в ответе Тимви. Я предполагаю, что для любого типа объекта будет множество объектов, которые будут хорошо расположены друг над другом, но не будут перекрываться с другими объектами, не входящими в одну группу. Таким образом, для объектов A, B, C, которые перекрываются, у вас будет , а не перекрытие A & B, перекрытие B & C и перекрытие A & C.

Таким образом, A всегда будет перекрывать B и C, B всегда будет перекрывать A и C, а C всегда будет перекрывать A и B. Однако могут быть объекты D, E и F, которые расположены в других местах, которые не перекрывают A, B или C (или друг друга), но может существовать третья (или более) группа объектов G, H и I, которые перекрывают друг друга.

То есть для данного проекта, данного типа объекта и объектов A, B, C (которые перекрывают друг друга), D, E и F (которые не перекрываются с любым другим объектом) и G, H и I ( которые перезаписывают себя и никаких других объектов) Я хотел бы видеть вывод, сгруппированный как:

Project
  ObjectType1List
    Group1
      A, B, C
    Group2
      G, H, I

В реальных данных может быть много таких групп для данного типа объекта.

Answer 1

Если ваши входные данные полностью состоят из непересекающихся групп прямоугольников, и внутри каждой группы каждый прямоугольник пересекается с каждым другим , то вам нужно сравнить каждый прямоугольник максимум с одним из каждогогруппа.Таким образом:

var groups = new Dictionary<Rectangle, List<Rectangle>>();
foreach (var rectangle in input)
{
    var key = groups.Keys.FirstOrDefault(k => k.IntersectsWith(rectangle));
    if (key.IsEmpty)
        groups[rectangle] = new List<Rectangle> { rectangle };
    else
        groups[key].Add(rectangle);
}

Поскольку вы упомянули, что хотите опустить группы, которые имеют только отдельные прямоугольники, вы можете просто отфильтровать их в конце:

foreach (var pair in groups.Where(kvp => kvp.Value.Count == 1).ToList())
    groups.Remove(pair.Key);

Answer 2

Я не могу помочь вам с группировкой, потому что ваш критерий группировки недостаточно четко определен.Если у вас есть три прямоугольника, где A перекрывает B, а B перекрывает C, а A не перекрывает C, что должно произойти?Вам нужно разобраться в этих вопросах, прежде чем вы сможете приступить к разработке алгоритма для него.

Однако вам не нужно писать математические вычисления, чтобы определить, пересекаются ли два прямоугольника.Вы можете просто использовать System.Drawing.Rectangle для этого:

var objects = from object in xdoc.Descendants()
    where object.Name = "ObjectType1" or object.Name = "ObjectType2" 
    select new
    {
      Project = object.Attribute("ProjectName").Value.ToString(),
      ObjectType = object.Name,
      Index = (int)object.Attribute("Idx").Value,
      Rectangle = new Rectangle(
          (int)object.Element("Location").Attribute("Top").Value,
          (int)object.Element("Location").Attribute("Left").Value,
          (int)object.Element("Location").Attribute("Width").Value,
          (int)object.Element("Location").Attribute("Height").Value
      )
    };

Тогда вы можете легко найти перекрывающиеся пары:

var overlapping = from obj1 in objects
                  from obj2 in objects
                  where obj1 != obj2 && obj1.Rectangle.IntersectsWith(obj2.Rectangle)
                  select new { One = obj1, Two = obj2 };

Конечно, это вернет каждую перекрывающуюся пару дважды, с одним и двумяместами.