Лучший способ сгруппировать перекрывающиеся прямоугольники? Я пытался использовать OpenCV, но метод grouprectangles не работает должным образом.
Я думал о том, чтобы сделать что-то вроде этого:
L = [every rectangle]
L_next = []
while not L.empty():
for rectangle in L:
L.remove(rectangle)
for other_rectangle in L:
if rectangle overlaps with other_rectangle:
L_next += rectangle + other_rectangle
L = L_next
L_next = []
Поскольку каждый не слитый прямоугольник будет удален из следующего списка, в худшем случае у меня будет n/2 итераций внешнего цикла. Два внутренних цикла должны выполняться n и n - 1 раз, так что алгоритм должен быть примерно O(n^3) в худшем случае, предполагая, что я ничего не пропустил, и что каждый шаг занимает только O(1).
Проблемы:
1) Нужно использовать классы эквивалентности или что-то в этом роде для правильного объединения групп прямоугольников. У Boost есть что-нибудь подобное?
2) Это похоже на операцию, которая должна выполняться часто, поэтому я удивлен, что не нашел больше материала по ней. Что с этим?
3) Предполагая, что на самом деле что-то для этого не реализовано, есть ли у кого-нибудь совет улучшить мой метод?
4) Как лучше всего увидеть, если два прямоугольника перекрываются?