Найдите связанные прямоугольники из HashSet, используя java - PullRequest
Новая
       4

Найдите связанные прямоугольники из HashSet, используя java

1 голос
/ 29 января 2020

У меня есть HashSet, заполненный пользовательским прямоугольным объектом («имя», center_X, center_Y, ширина, высота). я написал метод, чтобы найти, если два прямоугольника связаны (касание / пересечение). Но я хочу получить все прямоугольники, которые являются группой. Например: если rectA связано с rectB, Rect C связано с rectB, но не rectA напрямую, все они связаны, так как rectB является общим.

Я могу найти формы, которые имеют прямую связь. Но я хочу получить группу, где фигуры с вторичной связью также включены. Я бы предположил, что рекурсия полезна в этом случае, но пока не может ее решить. Любое решение / предложение? 

public static void canItbeGroup(HashSet<RECTANGLE> ipRectangles)
{
    Deque<RECTANGLE> ipDeque = new ArrayDeque<>(ipRectangles);

    for (RECTANGLE currRectangle : ipDeque)
    {
        Set<String> tempGrpMbrShapeID = new HashSet<>();
        RECTANGLE tempRect = ipDeque.pop();
        for (RECTANGLE r : ipDeque)
        {
            if (tempRect.areShapesFriend(r))
            {
                tempGrpMbrShapeID.add(r.shapeID);
                tempGrpMbrShapeID.add(tempRect.shapeID);
            }
        }
        if (tempGrpMbrShapeID.size() > 1)
        {
            System.out.println(tempGrpMbrShapeID);
        }
    }
}

public static void main(String[] args)
{
    HashSet<RECTANGLE> rectHS = new HashSet<>();

    RECTANGLE aRect = new RECTANGLE("a", 3, 2, 2, 2);
    RECTANGLE aInnerRect = new RECTANGLE("aIn", 3, 2, 1, 1);
    RECTANGLE bRect = new RECTANGLE("b", 5, 3, 2, 2);
    RECTANGLE cRect = new RECTANGLE("c", 7, 3, 2, 2);
    RECTANGLE dRect = new RECTANGLE("d", 4, 5, 4, 2);
    RECTANGLE eRect = new RECTANGLE("e", 11, 3, 2, 2);
    RECTANGLE fRect = new RECTANGLE("f", 11, 6, 2, 2);
    RECTANGLE gRect = new RECTANGLE("g", 13, 3, 2, 2);
    RECTANGLE hRect = new RECTANGLE("h", 4, 8, 2, 2);
    RECTANGLE iRect = new RECTANGLE("i", 14, 1, 2, 2);
    RECTANGLE jRect = new RECTANGLE("j", 16, 7, 2, 2);
    RECTANGLE kRect = new RECTANGLE("k", 15, 6, 2, 2);
    RECTANGLE lRect = new RECTANGLE("l", 8, 8, 2, 2);
    RECTANGLE mRect = new RECTANGLE("m", 5, 10, 2, 2);


    rectHS.add(aRect);
    rectHS.add(bRect);
    rectHS.add(cRect);
    rectHS.add(eRect);
    rectHS.add(dRect);
    rectHS.add(fRect);
    rectHS.add(gRect);
    rectHS.add(aInnerRect);
    rectHS.add(hRect);
    rectHS.add(iRect);
    rectHS.add(jRect);
    rectHS.add(kRect);
    rectHS.add(lRect);
    rectDQ.add(aRect);
    rectDQ.add(bRect);
    rectDQ.add(cRect);
    rectDQ.add(dRect);
    rectDQ.add(eRect);

    canItbeGroup(rectHS);
}

вывод я получаю: 

[a, b, aIn],[b, c, d],[g, i],[e, g],[j, k],[c, d]

Мне понадобится группа как 

[a,b,aIn,c,d], [e,g,i], [j,k]

1 Ответ

0 голосов
/ 29 января 2020

Я не буду решать проблему для вас, но я дам вам общий подход.

  1. Создайте начальный Collection<Set<String>>. Это фактически то, что вы уже сделали, но вам нужно хранить их, чтобы объединить наборы, а не распечатывать группу, как только вы их найдете
  2. Итерировать по всем группам (i) и сравните каждую группу с любой другой группой (j)
  3. Если i содержит какой-либо элемент j, то объедините наборы (поместите все элементы j в i и удалите все элементы из j)
  4. Go обратно в 2 и повторяйте до тех пор, пока вы не выполните 1 полную итерацию, где не происходит слияния.
  5. Выполните итерацию еще раз и удалите все пустые множества.
...