Эффективный групповой перекрывающий прямоугольник

Лучший способ группировать перекрывающиеся прямоугольники? Я попытался использовать 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) Каков наилучший способ увидеть, перекрываются ли два прямоугольника?

One Solution collect form web for “Эффективный групповой перекрывающий прямоугольник”

Я бы посмотрел на pygame.Rect.collide методы для ответа на вашу проблему. Поскольку обнаружение прямоугольных перекрытий настолько распространено в играх, я предполагаю, что их реализация довольно хороша с точки зрения вычислительной сложности.

  • Чтение Python Regex в комментариях стиля c
  • Рекурсивный генератор в C ++
  • Эффективный способ решения криптографических задач
  • Вызов библиотеки C # из python
  • Какие функции Python вызовут интерес разработчика C #?
  • Как скомпилировать код .c из Cython с gcc
  • Cython: шаблоны в оболочках класса python
  • Swig python - c ++ как использовать тип int8_t
  • Python - лучший язык программирования в мире.