Как я могу сгруппировать массив прямоугольников в “Острова” связанных регионов?

Хорошо, думаю, я понял. Этот алгоритм довольно неэффективен, O (n ^ 3) по расчетам, но, похоже, он работает.

Я использовал Set вместо List в getIntersections () , чтобы не подсчитывать один и тот же прямоугольник дважды (хотя я не думаю, что это действительно необходимо ). Я предполагаю, что ваш окончательный результат может быть даже Set > , но алгоритм должен быть примерно таким же. Я также везде использовал List вместо массивов, потому что я считаю массивы некрасивыми, но при необходимости их достаточно легко преобразовать обратно. Набор newRectanglesToBeAdded позволяет нам решить, нужно ли нам продолжать цикл или нет, а также удерживает нас от добавления в список, пока мы повторяем его (что так же плохо, как пытаться удалить что-то из list, пока мы повторяем его). Я не думаю, что это самое элегантное решение, но похоже, что оно работает (по крайней мере, для предоставленных вами тестовых данных).

  public static Set<Rectangle> getIntersections(List<Rectangle> list,
      Rectangle r) {
    Set<Rectangle> intersections = new HashSet<Rectangle>();
    intersections.add(r);

    Set<Rectangle> newIntersectionsToBeAdded = new HashSet<Rectangle>();

    do {
      newIntersectionsToBeAdded.clear();
      for (Rectangle r1 : list) {
        for (Rectangle r2 : intersections) {
          if (!intersections.contains(r1) && r2.intersects(r1)) {
            newIntersectionsToBeAdded.add(r1);
          }
        }
      }
      intersections.addAll(newIntersectionsToBeAdded);
    } while (!newIntersectionsToBeAdded.isEmpty());
    return intersections;
  }

  public static List<Set<Rectangle>> mergeIntersectingRects(List<Rectangle> allRects) {
    List<Set<Rectangle>> grouped = new ArrayList<Set<Rectangle>>();
    while (!allRects.isEmpty()) {
      Set<Rectangle> intersections = getIntersections(allRects, allRects.get(0));
      grouped.add(intersections);
      allRects.removeAll(intersections);
    }
    return grouped;
  }

Вы не можете удалить объект из списка, через который выполняется итерация, вне зависимости от объекта итератора, вам нужно будет найти другой способ

Основные параметры:

• Если в первую очередь используется интеграция Visual Studio, достаточно просто пометить эти файлы как «Исключить из системы управления версиями» в решениях/проектах.
• Администратор может заблокировать файл. TFS поддерживает два типа блокировок в зависимости от того, где в процессе вы хотите, чтобы разработчики получили шлепок с предупреждением: http://blogs.msdn.com/phkelley/archive/2008/11/12/everything-you-ever-wanted-to-know-about-locks.aspx

Есть несколько других способов, но я думаю, что это четкие фавориты.

Поле делегата по-прежнему является полем, а не методом - оно само по себе не принимает параметры. Параметры относятся к типу делегата , а не к полю делегата . При необходимости можно написать комментарии для параметров при делегировании типов.

/// <summary>
/// Tests something.
/// </summary>
/// <param name="test">Something that's going to be tested.</param>
delegate void Test(int test);

Func < последовательность, последовательность, последовательность > является общим делегатом для функций с тремя параметрами. Для конкретных целей всегда можно объявить собственный тип делегата, более конкретно представляющий абстрактный метод, и добавить комментарии к его параметрам.

Подключенные компоненты .

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

Я бы ожидал, что лучший алгоритм займет по крайней мере O (n ^ 2) времени, потому что учитывая n прямоугольников есть O (n ^ 2) возможных пересечений, и любой алгоритм для вычисления того, что вы хотите, должен будет рассмотреть все пересечения в какой-то пункт.

Если вам нужен алгоритм O (n log n), один из них был показан Имаи и Асано в Поиск связанных компонент и максимальной клики графа пересечений прямоугольников на плоскости .

Примечание: я все еще работаю над своим собственным алгоритмом развертки плоскости, чтобы найти набор за время O (n log n).

(это слишком долго для комментария)

Быстрый рисунок НЕ показывает, что A пересекает B: A имеет высота 4, в то время как B начинаются с позиции Y, равной 5, как они могут пересекаться!?

Вы можете проверить это, выполнив следующую команду, которая выводит «false»:

System.out.println( new Rectangle(0, 0, 2, 4).intersects( new Rectangle(1, 5, 4, 2) ) );

Тогда подпись вашего метода неполна, как и ваш пример кода .

Если вы немного проясните свою проблему и приведете рабочий, правильный пример, то у меня есть для вас очень хорошее решение.

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

Простое нахождение ребер (определение для каждой пары прямоугольников пересечения) занимает O (n ² ) времени, после чего вы можете использовать либо поиск в глубину или поиск в ширину , чтобы найти все компоненты за дополнительное время O (E), где E 2 .

В псевдокоде (простое упражнение по переводу его на Java) это может выглядеть примерно так:

# r is the list of rectangles
n = length of r (number of rectangles)

#Determine "neighbors" of each vertex
neighbors = (array of n lists, initially empty)
for i in 1 to n:
    for j in 1 to n:
        if i!=j and r[i].intersects(r[j]):
            neighbors[i].append(j)

#Now find the connected components
components = (empty list of lists)
done = (array of n "False"s)
for i in 1 to n:
    if done[i]: continue
    curComponent = (empty list)
    queue = (list containing just i)
    while queue not empty:
        r = pop(head of queue)
        for s in neighbors[r]:
            if not done[s]:
                done[s] = True
                queue.push(s)
                curComponent.push(s)
    #Everything connected to i has been found
    components.push(curComponent)

return components

Я предварительно вычисляю соседей и использую метки «готово», чтобы сохранить фактор O (n) и сделать все это O (n ² ). Фактически, этот алгоритм предназначен для общих графиков, но поскольку ваш график довольно особенный - он состоит из прямоугольников - вы можете добиться еще большего: на самом деле можно решить проблему за O (n log n) всего времени, используя деревья сегментов .

Я не знаю java foo, но думаю, проблема в том, что вы удаляете элементы из своего списка во время итерации списка. В зависимости от реализации типа контейнера могут возникнуть большие проблемы. Кто-то с большим знанием Java может подтвердить или опровергнуть это.

Этот вопрос SO , кажется, подтверждает мои подозрения.

После небольшого поиска в Google кажется, что итераторы Java поддерживают метод удаления, поэтому вместо

allRects.remove(rect);

вы должны использовать итератор, а затем использовать

rect_i.remove();

и то же самое для

list.remove(rect);

Хотя я думаю, что это все равно поможет вам проблема, поскольку вы изменяете тот же список на более низком уровне в стеке вызовов.

Моя версия:

ArrayList<Rectangle> rects = new ArrayList<Rectangle>(rectArray);
ArrayList<ArrayList<Rectangle>> groups = new ArrayList<ArrayList<Rectangle>>();
while (!rects.isEmpty)
{
    ArrayList<Rectangle> group = new ArrayList<Rectangle>();
    ArrayList<Rectangle> queue = new ArrayList<Rectangle>();
    queue.add(rects.remove(0));
    while (!queue.isEmpty)
    {
        rect_0 = queue.remove(0);
        rect_i = rects.iterator();
        while (rect_i.hasNext())
        {
            Rectangle rect_1 = rect_i.next();
            if (rect_0.intersects(rect_1))
            {
                queue.add(rect_1);
                rect_i.remove();
            }
        }
        group.add(rect_0);
    }
    groups.add(group);
}

Примечание: я думаю, что сейчас код правильный, но я написал это только из справочной документации, и я не Java-программист, так что вам, возможно, придется подправить.

Кроме того, этот тип наивного алгоритма хорош, если у вас есть небольшой список прямоугольников, которые вам нужно проверить, но если вы хотите сделать это для очень больших списков, тогда вам нужно будет использовать гораздо более эффективный алгоритм. Этот наивный алгоритм представляет собой O (n ^ 2), более умный алгоритм, который сначала лексикографически сортирует все углы прямоугольника, а затем выполняет развертку плоскости и выполняет проверку пересечения диапазона на линии развертки, что приведет к относительно простому алгоритму O (n log n).