Есть ли алгоритм, который может разбивать пространство на N число разделов, заданных случайным числом N, где N <50

Question

Я читал о R-Tree, kd-tree, иерархии интервальных интервалов и т. Д. Для пространственного разделения. Я обнаружил, что эти структуры данных полезны для пространственного запроса. Хотя они выполняют разделение, но я не знаю, как получить эти разделы из структуры данных. Итак, мой вопрос сводится к «Учитывая число N и карту, содержащую число X многоугольников, могу ли я получить N число разделов, содержащих приблизительно равное количество полигонов?»

Answer 1

Ну, если вы хотите ровно N разделов, любая из общих стратегий массовой загрузки для R-Tree должна работать. Это не обязательно будет оптимальным, но вы можете заставить их производить ровно N разделов примерно равного размера.

В k-d-дереве будут объекты, которые находятся ни в левой, ни в правой части. Но вы можете использовать стратегию массовой загрузки k-d-tree и изменить ее для создания N разделов. Еще один простой, но иногда довольно эффективный способ насыпной загрузки и R-дерева.

Когда вы ограничиваете N силой 2 или даже лучше-го уровня какого-либо числа, расколы обычно будут лучше. Таким образом, разбиение 3D-набора данных на 9 страницах намного проще для реализации, чем разбиение его на 8 страниц.