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

Question

проблема

У меня есть массив java.awt.Rectangle с. Для тех, кто не знаком с этим классом, важной информацией является то, что они предоставляют функцию .intersects(Rectangle b).

Я хотел бы написать функцию, которая принимает этот массив Rectangle с и разбивает его на группы связанных прямоугольников.

Допустим, например, что это мои прямоугольники (конструктор принимает аргументы x, y, width, height):

Rectangle[] rects = new Rectangle[]
{
    new Rectangle(0, 0, 4, 2), //A
    new Rectangle(1, 1, 2, 4), //B
    new Rectangle(0, 4, 8, 2), //C
    new Rectangle(6, 0, 2, 2) //D
}

Быстрый рисунок показывает, что A пересекает B, а B пересекает C. D ничего не пересекает. Утомительно нарисованное произведение искусства ascii тоже делает свою работу:

┌───────┐   ╔═══╗
│A╔═══╗ │   ║ D ║
└─╫───╫─┘   ╚═══╝
  ║ B ║                 
┌─╫───╫─────────┐
│ ╚═══╝ C       │
└───────────────┘

Поэтому вывод моей функции должен быть:

new Rectangle[][]{
    new Rectangle[] {A,B,C},
    new Rectangle[] {D}
}

Код ошибки

Это была моя попытка решить проблему:

public List<Rectangle> getIntersections(ArrayList<Rectangle> list, Rectangle r)
{
    List<Rectangle> intersections = new ArrayList<Rectangle>();
    for(Rectangle rect : list)
    {

        if(r.intersects(rect))
        {
            list.remove(rect);
            intersections.add(rect);
            intersections.addAll(getIntersections(list, rect));
        }
    }
    return intersections;
}

public List<List<Rectangle>> mergeIntersectingRects(Rectangle... rectArray)
{
    List<Rectangle> allRects = new ArrayList<Rectangle>(rectArray);
    List<List<Rectangle>> groups = new ArrayList<ArrayList<Rectangle>>();
    for(Rectangle rect : allRects)
    {
        allRects.remove(rect);
        ArrayList<Rectangle> group = getIntersections(allRects, rect);
        group.add(rect);
        groups.add(group);
    }
    return groups;
}

К сожалению, здесь, кажется, происходит бесконечный цикл рекурсии. Мое необразованное предположение, что ява не любит, когда я делаю это:

for(Rectangle rect : allRects)
{
    allRects.remove(rect);
    //...
}

Может кто-нибудь пролить свет на проблему?

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

После небольшого приближения кажется, что 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).

Answer 4

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

пакет 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;
    }
}

Answer 5

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

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

Answer 6

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

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

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

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

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

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

Answer 7

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

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

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

Answer 8

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