Как я могу группировать массив прямоугольников в "Острова" связанных областей?
Проблема
У меня есть массив java.awt.Rectangle s. Для тех, кто не знаком с этим классом, важной частью информации является то, что они предоставляют функцию .intersects(Rectangle b).
Я хотел бы написать функцию, которая принимает этот массив Rectangle s, и разбивает его на группы связанных прямоугольников.
Давайте, например, скажем, что это мои прямоугольники (конструктор принимает аргументы 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;
}
К сожалению, здесь, кажется, существует бесконечный цикл рекурсии. Моя необразованная догадка заключалась в том, что java не любит, когда я делаю это:
for(Rectangle rect : allRects)
{
allRects.remove(rect);
//...
}
Может ли кто-нибудь пролить свет на проблему?
Ответы
Ответ 1
Это решение, в котором я пошел, в конце концов. Может ли кто-нибудь угадать его эффективность?
пакет 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;
}
}
Ответ 2
Вы хотите найти связанные компоненты. То есть представьте граф, вершины которого соответствуют прямоугольникам, и где есть ребро между двумя вершинами, если соответствующие прямоугольники пересекаются. Затем вы хотите найти и label связанные компоненты этого графика.
Простое обнаружение ребер (определение для каждой пары прямоугольников, пересекаются ли они) принимает O (n 2) время, после чего вы можете использовать поиск по глубине или поиск в ширину, чтобы найти все компоненты в дополнительном 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 2). Фактически, этот алгоритм предназначен для общих графиков, но потому, что ваш график является довольно особенным - получается из прямоугольников - вы можете сделать еще лучше: на самом деле можно решить проблему в общем времени O (n log n), используя деревья сегментов.
Ответ 3
Я не в курсе java foo, но я думаю, проблема в том, что вы удаляете элементы из своего списка, итерации списка. В зависимости от реализации типа контейнера это может иметь большие проблемы. Кто-то, у кого больше знаний Java, может подтвердить или опровергнуть это.
Этот SO-вопрос, похоже, подтверждает мои подозрения.
После того, как вы немного поработали, кажется, что java-итераторы поддерживают метод remove, поэтому вместо
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).
Ответ 4
Хорошо, я думаю, что понял. Этот алгоритм довольно неэффективен, 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;
}
Ответ 5
(слишком длинный комментарий)
Быстрый рисунок НЕ показывает, что A пересекает B: A имеет высоту 4, а B начинается с Y-позиции 5, как они могут пересекаться!?
Вы можете проверить его следующим образом: :
System.out.println( new Rectangle(0, 0, 2, 4).intersects( new Rectangle(1, 5, 4, 2) ) );
Тогда ваша подпись метода неполна, поэтому ваш пример кода.
Если вы немного уточните свою проблему и дадите рабочий, правильный пример, то у меня есть очень приятное решение для вас.
Ответ 6
Если вам нужен алгоритм O (n log n), один был показан Имаи и Асано в Поиск подключенных компонентов и максимальная клика пересечения график прямоугольников в плоскости.
Примечание. Я все еще работаю над своим собственным алгоритмом развертки плоскости, чтобы найти набор в O (n log n) времени.
Ответ 7
Вы не можете удалить объект из списка, через который вы выполняете итерацию, итератора или нет, вам нужно будет найти другой способ
Ответ 8
Подключенные компоненты.
В качестве альтернативы, поскольку у вас есть только прямоугольники, вы можете создать очень эффективный алгоритм развертки строк.
Я бы ожидал, что лучший алгоритм займет не менее O( n^2 ), потому что заданные прямоугольники n есть O( n^2 ) возможные пересечения, и любой алгоритм для вычисления того, что вы хотите, должен будет рассмотреть все пересечения в какой-то точке.
