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

Question

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

Разделение не должно быть точным (почти любое приближение лучше, чем обычная сетка), но алгоритм должен справляться с большим количеством точек - ок. 200 миллионов Тем не менее, желаемое количество подправок существенно меньше (около 1000).

Кто-нибудь знает какой-нибудь алгоритм, который может помочь мне с этой конкретной задачей?

Answer 1

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

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

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

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

Answer 2

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

Предположение> Количество прямоугольников четное
Допущение> Распределение точек заметно 2D (нет большого накопления в одной строке)

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

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

Answer 3

R-дерево

Answer 4

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

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

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

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

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

Answer 5

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

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

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

Answer 6

Это похоже на Кластерный анализ .

Answer 7

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

Answer 8

Хороший вопрос.

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

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