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

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

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

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

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

R-tree

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

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

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

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

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

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

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

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

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

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

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

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

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