Рекурсивно объединить похожие элементы в список

Question

Я хотел бы сгруппировать/объединить/объединить прямоугольники, близкие (похожие) друг к другу. Нет никакой особой причины, почему я попробовал это рекурсивно, но это казалось подходящим.

Однако у меня что-то отсутствует. Результат неправильный, и я не учитывал тот факт, что прямоугольники, объединенные позже по дороге, могут быть близки теперь к прямоугольникам, которые я считал «неизмеримыми», и помещал их в finalList

Сближение и проверка близости метод работает правильно.

public static ArrayList<Rect> mergeCloseRects(ArrayList<Rect> sourceList, ArrayList<Rect> finalList) { 

    Rect rect = sourceList.get(0).clone(); 
    sourceList.remove(0); 

    for (int i = 0; i < sourceList.size(); i++) { 

     if (rectsAreClose(rect, sourceList.get(i)) { 
      // put merged rectangle on top of the list 
      sourceList.add(0, getMergeRect(rect, sourceList.get(i))); 
      // remove rectangle that was merged with rect 
      sourceList.remove(i + 1); 
      mergeCloseRects(sourceList, finalList); 
     } 
    } 

    // if rect has no close neighbours 
    finalList.add(rect); 

    return finalList; 
} 

Входной

Выход

Как вы можете видеть прямоугольники на самом деле не объединены. Нижний список остался в списке. Зеленый контур указывает, где будет новый прямоугольник (ы).

Answer 1

Это кажется мне лучше подходит для итерации, чем рекурсия: вы, естественно, можете продолжать идти, пока не осталось ничего, что можно было бы слить. Я думаю, что ваш код должен выглядеть примерно так:

while(!getListCloseRectangles(sourceList).isEmpty()) { 
    List<Rect> rectanglesToMerge = getListCloseRectangles(sourceList); 
    sourceList.removeAll(rectanglesToMerge); 
    sourceList.add(createMergedRect(rectanglesToMerge)); 
} 

Это также позволяет для ситуации, в которой getListCloseRectangles может вернуть более чем два прямоугольника одновременно. Но он все равно будет работать нормально, если он только возвращает два элемента в списке.