Алгоритм космического распределения

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

R-Tree

Answer 4

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

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

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

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

Answer 8

Будет а Quadtree Работа?

Quadtree - это структура данных дерева, в которой каждый внутренний узел имеет ровно четыре детей. Четверти чаще всего используются для размещения двухмерного пространства путем рекурсивно подразделения его на четыре квадранта или области. Области могут быть квадратными или прямоугольными, или могут иметь произвольные формы. Эта структура данных была названа Quadtree Raphael Finkel и JL Bentley в 1974 году. Аналогичное разделение также известно как Q-дерево. Все формы Quadtres имеют некоторые общие черты:

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