Алгоритм разбиения пространства

Ответ 1

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

Успение > Число прямоугольников равно/ Предположение > Точечное распределение заметно двумерное (отсутствие большого скопления в одной строке)

Процедурa >
Bisect n/2 раза по любой оси, переходя от одного конца к другому из каждого ранее определенного прямоугольника, считая "пройденные" точки и сохраняя количество пройденных точек на каждой итерации. После подсчета, разделите прямоугольник на выбор точек, подсчитанных в каждом цикле.

Это то, чего вы хотите достичь?

Ответ 2

R-tree

Ответ 3

Я думаю, что после стандартного дерева разбиения на дерево дерева или двоичного дерева. (Вы можете посмотреть его в Википедии.)

Поскольку у вас очень много точек, вы можете захотеть только приблизительно разбить первые несколько уровней. В этом случае вы должны взять произвольную выборку из ваших 200M точек - возможно, 200 тысяч из них - и разделить полный набор данных в середине подвыборки (вдоль любой оси больше). Если вы на самом деле выбираете точки случайным образом, вероятность того, что вы пропустите огромный кластер точек, которые должны быть разделены, будет примерно равна нулю.

Теперь у вас есть две проблемы по 100 М точек. Разделите их вдоль более длинной оси. Повторяйте до тех пор, пока не прекратите принимать подвыборки и не разделите их по всему набору данных. После десяти первых итераций вы закончите.

Если у вас другая проблема - вы должны указывать отметки вдоль оси X и Y и заполнить сетку вдоль них как можно лучше, вместо того, чтобы иметь нерегулярное разложение дерева Kd - возьмите свою подвыборку точек и найдите 0/32, 1/32,..., 32/32 процентиля вдоль каждой оси. Нарисуйте там линии сетки, затем заполните полученную сетку из 1024 элементов своими точками.

Ответ 4

Я думаю, что я начну со следующего, что близко к тому, что уже было предложено уже [belisarius]. Если у вас есть какие-либо дополнительные требования, например, предпочитая прямоугольники прямоугольника "длинным и тонким", вам нужно будет изменить этот наивный подход. Для простоты я предположим, что точки примерно распределены случайным образом.

• Разделите свой начальный прямоугольник на 2 с линией, параллельной короткой стороне прямоугольника, и выполните ровно через середину.
• Подсчитайте количество точек в обоих полупрямоугольниках. Если они равны (достаточно), переходите к шагу 4. В противном случае перейдите к шагу 3.
• Основываясь на распределении точек между полупрямыми прямоугольниками, снова переместите линию на четные. Так что, если, возможно, первый разрез разделяет точки 1/3, 2/3, переместите линию на полпути в тяжелую половину прямоугольника. Переходите к этапу 2. (Будьте осторожны, чтобы не попасть в ловушку здесь, перемещая линию на все убывающие шаги сначала в одном направлении, а затем на другое.)
• Теперь передайте каждый из полупрямоугольников в рекурсивный вызов этой функции на шаге 1.

Я надеюсь, что это предложение достаточно хорошо описано. У него есть ограничения: он будет создавать ряд прямоугольников, равных некоторой мощности 2, поэтому отрегулируйте его, если это будет недостаточно. Я сформулировал его рекурсивно, но он идеально подходит для параллелизации. Каждый раскол создает две задачи, каждая из которых разбивает прямоугольник и создает еще две задачи.

Если вам не нравится этот подход, возможно, вы можете начать с обычной сетки с несколькими краткими (возможно, 10 - 100) от числа прямоугольников, которые вы хотите. Подсчитайте количество точек в каждом из этих маленьких прямоугольников. Затем начните склеивать крошечные прямоугольники, пока менее мелкий прямоугольник не будет содержать (приблизительно) правильное количество точек. Или, если он удовлетворяет вашим требованиям достаточно хорошо, вы можете использовать это как метод дискретизации и интегрировать его с моим первым подходом, но только поместите линии резки вдоль границ крошечных прямоугольников. Это, вероятно, будет намного быстрее, так как вам нужно будет только подсчитывать точки в каждом маленьком прямоугольнике.

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

Ответ 5

Я думаю, что область, которую нужно исследовать, - это "вычислительная геометрия" и проблема "k-разбиения". Там ссылка, которая может помочь вам начать здесь

Вы можете обнаружить, что сама проблема - NP-hard, что означает, что алгоритм хорошего аппроксимации - лучшее, что вы собираетесь получить.

Ответ 6

Будет K-означает кластеризацию или диаграмма Вороного быть хорошим подспорьем для проблемы, которую вы пытаетесь решить?

Ответ 7

Это выглядит как Анализ кластеров.

Ответ 8

Будет ли работать QuadTree?

Квадратура - это структура данных дерева, в которой каждый внутренний node имеет ровно четыре ребенка. Квадранты чаще всего используются для разделения двумерного пространства путем рекурсивного разделения его на четыре квадранта или области. Области могут быть квадратными или прямоугольными или могут иметь произвольные формы. Эта структура данных была названа квадтрией Рафаэлем Финкелем и Я. Бентли в 1974 году. Аналогичное разбиение также известно как Q-дерево. Все формы Quadtrees имеют общие особенности:

• Они разлагают пространство на адаптируемые ячейки
• Каждая ячейка (или ведро) имеет максимальную емкость. Когда достигается максимальная емкость, ведро разбивается на
• Каталог дерева следует за пространственным разложением Quadtree