Алгоритм разделения пространства
У меня есть набор точек, которые содержатся в прямоугольнике. Я хотел бы разбить прямоугольники на под прямоугольники, основываясь на плотности точек (давая количество под прямоугольников или желаемую плотность, в зависимости от того, что проще).
Разделение не должно быть точным (почти любое приближение лучше, чем обычная сетка), но алгоритм должен справляться с большим количеством точек - ок. 200 миллионов Тем не менее, желаемое количество подправок существенно меньше (около 1000).
Кто-нибудь знает какой-либо алгоритм, который может помочь мне с этой конкретной задачей?
8 ответов
Просто чтобы понять проблему. Следующее является грубым и плохо работает, но я хочу знать, если результат, что вы хотите>
Предположение> Количество прямоугольников четное
Предположение> Распределение точек заметно 2D (нет большого накопления в одной строке)
Процедура>
Разделяйте n/2 раза по каждой оси, проходя от одного конца к другому каждого ранее определенного прямоугольника, подсчитывая "пройденные" точки и сохраняя количество пройденных точек на каждой итерации. После подсчета пополам выделение прямоугольника по точкам, подсчитанным в каждом цикле.
Это то, что вы хотите достичь?
Я думаю, что вы используете стандартное дерево Kd или дерево двоичного разбиения пространства. (Вы можете посмотреть это в Википедии.)
Поскольку у вас очень много очков, вы можете разделить первые несколько уровней только приблизительно. В этом случае вы должны взять случайную выборку из ваших 200 миллионов точек - возможно, 200 тысяч из них - и разбить полный набор данных в средней точке выборки (вдоль любой оси, которая длиннее). Если вы на самом деле выбираете точки случайным образом, вероятность того, что вы пропустите огромный кластер точек, которые нужно разделить, будет приблизительно равна нулю.
Теперь у вас есть две задачи по 100 миллионов очков каждая. Разделите каждый вдоль более длинной оси. Повторяйте до тех пор, пока вы не прекратите брать подвыборки и разделите весь набор данных. После десяти итераций в ширину все будет готово.
Если у вас возникла другая проблема - вы должны поставить галочки вдоль осей X и Y и заполнить сетку вдоль них как можно лучше, вместо того, чтобы иметь неправильную декомпозицию дерева Kd- возьмите свою подвыборку точек и найдите 0/32, 1/32, ..., 32/32 процентили вдоль каждой оси. Нарисуйте линии сетки там, затем заполните полученную сетку из 1024 элементов своими точками.
Я думаю, что начну со следующего, что близко к тому, что @belisarius уже предлагал. Если у вас есть какие-либо дополнительные требования, такие как предпочтение "почти квадратных" прямоугольников, а не "длинных и тонких", вам нужно изменить этот наивный подход. Для простоты я предполагаю, что точки распределены приблизительно случайным образом.
- Разделите ваш первоначальный прямоугольник на 2 с линией, параллельной короткой стороне прямоугольника и проходящей точно через середину.
- Подсчитайте количество точек в обоих полу прямоугольниках. Если они равны (достаточно), перейдите к шагу 4. В противном случае перейдите к шагу 3.
- Основываясь на распределении точек между полу прямоугольниками, переместите линию, чтобы выровнять вещи снова. Так что, если, вероятно, первый разрез разделит точки 1/3, 2/3, переместите линию на полпути в тяжелую половину прямоугольника. Перейдите к шагу 2. (Будьте осторожны, чтобы не оказаться в ловушке, перемещая линию постепенно уменьшающимися шагами сначала в одном направлении, а затем в другом.)
- Теперь передайте каждый из полу прямоугольников рекурсивному вызову этой функции на шаге 1.
Я надеюсь, что это достаточно хорошо описывает предложение. У него есть ограничения: он будет производить количество прямоугольников, равное некоторой степени 2, поэтому отрегулируйте его, если этого недостаточно. Я сформулировал это рекурсивно, но он идеально подходит для распараллеливания. Каждое разделение создает две задачи, каждая из которых разбивает прямоугольник и создает еще две задачи.
Если вам не нравится такой подход, возможно, вы могли бы начать с обычной сетки с несколькими кратными (возможно, 10 - 100) количеством нужных вам прямоугольников. Подсчитайте количество точек в каждом из этих крошечных прямоугольников. Затем начните склеивать крошечные прямоугольники вместе, пока менее крошечный прямоугольник не содержит (приблизительно) нужное количество точек. Или, если он удовлетворяет вашим требованиям достаточно хорошо, вы можете использовать его как метод дискретизации и интегрировать его с моим первым подходом, но размещать линии разреза только вдоль границ крошечных прямоугольников. Это, вероятно, будет гораздо быстрее, поскольку вам нужно будет только посчитать точки в каждом крошечном прямоугольнике один раз.
Я действительно не думал о времени выполнения любого из них; Я предпочитаю первый подход, потому что я занимаюсь большим количеством параллельного программирования и имею кучу процессоров.
Дерево квадрантов - это древовидная структура данных, в которой каждый внутренний узел имеет ровно четыре дочерних элемента. Квадроды чаще всего используются для разбиения двумерного пространства путем рекурсивного деления его на четыре квадранта или области. Области могут быть квадратными или прямоугольными или могут иметь произвольные формы. Рафаэль Финкель и Дж. Л. Бентли назвали эту структуру данных квадродеревом в 1974 году. Подобное разбиение также известно как Q-дерево. Все формы Quadtrees имеют некоторые общие черты:
- Они разлагают пространство на адаптируемые клетки
- Каждая ячейка (или ведро) имеет максимальную вместимость. Когда максимальная вместимость достигнута, ковш раскалывается
- Каталог дерева следует пространственной декомпозиции Quadtree
Подойдет ли кластеризация K-средних или диаграмма Вороного для решения проблемы, которую вы пытаетесь решить?
Хороший вопрос.
Я думаю, что область, которую вам нужно исследовать, это "вычислительная геометрия" и проблема "k-разбиения". Здесь есть ссылка, которая может помочь вам начать здесь
Вы можете обнаружить, что сама проблема NP-сложна, что означает, что лучший алгоритм аппроксимации - лучшее, что вы получите.