Как мне индексировать простой мир прямоугольников?

Question

Мир состоит из множества (1k-10k) прямоугольников одинакового размера, и мне нужно иметь возможность быстро определять потенциальные перекрытия при попытке добавить новый прямоугольник. Прямоугольники будут добавлены и удалены динамически. Подходят ли здесь R-деревья? Если да, есть ли хорошие библиотеки, которые я должен рассмотреть? (Я открыт для предложений на любом языке).

Answer 1

R-деревья подойдут, да.

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

Здесь есть реализация c # здесь , хотя я на это не смотрел.

Этот тип структуры данных (и ее 3D-версия называется Octrees ) часто используется в играх для управления большими наборами данных объектов, которые должны знать, находятся ли они рядом с какими-либо другими объектами для тестирования на столкновение и все другие забавные причины.

Вы сможете найти множество статей и примеров подобных структур данных на сайтах игровой индустрии, таких как gamasutra и opengl.org

Answer 2

Вы также можете посмотреть до kd-деревьев .

Я не знаю ни одной реализации, но в 3D, по крайней мере, они обычно считаются более производительными, чем Octrees. Например, вот возвращение опыта Я только что погуглил его .

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

Однако следует отметить, что kd-деревья трудно сбалансировать ...