Задача сия мне попадалась неоднократно. В разных размерностях (от 1 до 6, причем шестимерное пространство было совсем не декартовым — оно описывало перемещения трехмерного пространства) и с разным числом точек, но всегда без точной формулировки. Хорошего решения я, кажется, не написал ни разу, каждый раз махал рукой и шел другим путем. Но мысли остались следующие.
1) без понятия «масштаб» задача не имеет смысла. То есть, прежде чем решать ее, надо задаться неким «размером окошка», «радиусом размытия точки», «шириной серой зоны» и т.п.
2) чаще всего этот размер заранее неизвестен. Если взять его с запасом, то результат будет правдоподобен, но неточен а если размер окажется слишком маленьким, то наоборот, найдется локальное скопление среди пустоты. Лучше всего, наверное, выбрать убывающую последовательность r1>r2>r3>r4… (например, для окна 2000х2000 это моут быть степени двойки от 128 до 8), найти квадрат со стороной r1, содержащий максимальное количество точек, в нем — квадрат со стороной r2, и т.д. В этом случае наш результат будет правдоподобен во всем диапазоне масштабов.
3) Искать границы квадратов с точностью до пикселя смысла нет. Если мы ищем квадрат NxN, то достаточно перебрать квадраты с шагом N/4 по каждой координате. Например, если мы ищем квадрат 128х128 на плоскости размером 2000х2000, то достаточно рассмотреть 3600 возможных положений этого квадрата (вершина имеет координаты от 0 до 1888 с шагом 32). Завести целочисленный массив такого размера. Каждая точка попадает в 16 квадратов (или меньше) — увеличить 16 ячеек на 1. Найти максимальную — она даст стартовый квадрат.
После этого в этом квадрате перебрать 25 квадратов 64х64, в максимальном из них 25 квадратов 32х32 и т.д.
Если r1 выбран слишком маленьким, а плоскость была слишком большой, то вместо массива (который был 60х60) можно воспользоваться каким-нибудь деревом (для экономии памяти и времени на инициализацию).
Не исключено, что имеет смысл просмотреть не одну последовательность квадратов, а несколько (выбрать 10 квадратов размером r1 с наибольшим весом, из всех квадратов со стороной r2, лежащих в них — 10 наибольших и т.д.) Но это будет писать сложнее, а сработает оно только если скопление выражено нечетко, а где-то есть разреженная туманность. Впрочем, в этой ситуации надо сразу уменьшать r1.
