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

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

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

В псевдокоде (простое упражнение по его переводу на 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) общего времени, используя деревья сегментов.

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

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

  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;
  }

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

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

После небольшого поиска в 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).

Если вам нужен алгоритм 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) ) );

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

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

Это решение, к которому я пришел в конце концов. Кто-нибудь может предположить его эффективность?

пакет java.util;

import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.List;

public class RectGroup extends ArrayList<Rectangle> implements List<Rectangle>
{
    public RectGroup(Rectangle... rects)
    {
            super(rects);
    }

    public RectGroup()
    {
        super();
    }

    public boolean intersects(Rectangle rect)
    {
        for(Rectangle r : this)
            if(rect.intersects(r))
                return true;

        return false;
    }

    public List<RectGroup> getDistinctGroups()
    {
        List<RectGroup> groups = new ArrayList<RectGroup>();
        // Create a list of groups to hold grouped rectangles.

        for(Rectangle newRect : this)
        {
            List<RectGroup> newGroupings = new ArrayList<RectGroup>();
            // Create a list of groups that the current rectangle intersects.

            for(RectGroup group : groups)
                if(group.intersects(newRect))
                    newGroupings.add(group);
            // Find all intersecting groups

            RectGroup newGroup = new RectGroup(newRect);
            // Create a new group

            for(List<Rectangle> oldGroup : newGroupings)
            {
                groups.remove(oldGroup);
                newGroup.addAll(oldGroup);
            }
            // And merge all the intersecting groups into it

            groups.add(newGroup);
            // Add it to the original list of groups
        }
        return groups;
    }
}

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

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

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

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