Эффективная структура данных для представления 2D-сетки

Question

Существует 2-я сетка с произвольным размером. (Например, 1000 * 1000)

Вот картина:

данной входы четыре Интс: xywh, которая выступает за (х, у) координаты для нижней левой точки каждого прямоугольника и его ширину и высоту.

Прямоугольники, имеющие общие края или перекрывающиеся, определены как подключены.

Набор связанных прямоугольников определяется как кластер .

Число прямоугольников на каждой элементарной ячейке определяется как ее толщина.

Таким образом, проблема просит, чтобы вычислить: 1. Максимальная толщина 2. Число кластеров 3. Максимальное число элементов кластера для одного кластера 4. Максимальная площадь для одного кластера

Например, на рисунке выше максимальная толщина составляет 3 и имеется 2 кластера. Один кластер состоит из 3 прямоугольников, а его площадь - 44. Число элементов в другом кластере равно 4, а площадь равна 30. Поэтому кластер с максимальным количеством элементов кластера равен 4, а максимальная площадь кластера равна 44.

---

Мое решение довольно наивно. Я использовал массив 2-d int для представления сетки. При чтении ввода я просто увеличиваю число в соответствующих ячейках. После того, как все данные прочитаны, я использовал поиск по глубине для определения кластеров.

Проблема заключается мой алгоритм очень медленно, и вскоре становится непригодным для использования, когда дается большой ввод (например, когда размер сетки проходит более 1000 * 1000)

Так что я хотел бы знать, есть ли эффективная структура данных и алгоритм для решения этой проблемы?

Answer 1

После ввода всех введенных данных я использовал поиск по глубине для определения кластеров.

Вам не нужно это делать - вы можете выбирать кластеры при чтении ввода, как и для определения толщины.

Для каждой ячейки отслеживайте, к какому кластеру принадлежит. При повторении ячеек вашей сетки, соответствующих прямоугольнику чтения, следите за кластерами, к которым они принадлежат. Объедините все кластеры, которые вы найдете во время этого обхода, в один кластер. Вы можете сделать это эффективно в очень близком к постоянному времени с использованием структуры данных Disjoint-set.

Однако всю вашу проблему можно решить с помощью sweep line algorithm.

Answer 2

Я думаю, что вы просто описали пространственное разбиение с использованием структуры 2D AABB.

Входные решетки попадают в дерево и ориентированы произвольно. Цель дерева - сортировка.

Возможно, вам потребуется расширить возможности дерева в соответствии с вашими потребностями (например, соединения, следящие кластеры, слои/толщина).

Дерево пространственного разделения, используемое для размещения 2D AABB, может быть расширено, развернуто или закрыто листьями, чтобы эффективно сократить время доступа.

2D-физические двигатели в видеоиграх используют это, чтобы эффективно справляться со столкновениями в произвольном порядке сотен до тысяч легко на сколь угодно больших (грубо бесконечных) размерах сетки. Их обработка может быть ускорена с помощью таких технологий, как OpenCL (для процессоров и графических процессоров) или других технологий GPGPU.

См. Эту статью в Википедии по адресу AABBs.

См. Статью по статье BSPs об общей идее использования (двоичного) дерева для пространственного разбиения.

См. Эту статью в Википедии по адресу quadtrees в качестве концепции дерева более высокого порядка, которая может быть проще реализовать, может быть даже быстрее, если все это AABB, так как оно в 4 раза шире. Вы также можете сгладить деревья с более высоким порядком, хотя преимущества в большинстве случаев кажутся максимальными для квадрантов для 2D-пространства.

См. Эту статью в Википедии по адресу collision detection как способ определения соединений и кластеров.

См. Эту статью в Википедии по адресу splay trees за представление о преимуществах разрастания и расширения деревьев.

Answer 3

Мое предложение состояло в том, чтобы объединить два других полученных в настоящее время ответа: используйте некоторую пространственную структуру данных, такую ​​как дерево AABB или quadtree, чтобы сохранить все прямоугольники, которые вы обработали до сих пор, чтобы вы могли быстро найти связанные прямоугольники; а затем сохранить связанные кластеры в объединенной находке или непересекающейся структуре данных набора.

После того как вы обработали все прямоугольники, вы можете ответить на вопросы 2 и 3 в линейном времени. Вопрос 1 (макс. Толщина) немного сложнее; если вы не будете осторожны, вы можете сделать квадратное число тестов перекрытия, если все прямоугольники перекрываются. Аналогично для ответа 4.

Итак, когда вы вводите прямоугольник, который накладывается на структуру пространственных данных, лучшим решением может быть разбиение на непересекающиеся части постоянной толщины. Тогда 1 и 4 также легко ответить относительно быстро.