У меня есть 2d-точки (x, y) с координатами с плавающей точкой, когда я рисую их, мне нужно сгруппировать точки, если они расположены близко друг к другу, и их следует сгруппировать с помощью прямоугольника с фиксированным размером. И проблема в том, что эти прямоугольники не должны пересекаться, и все точки-соседи должны быть сгруппированы.
Если у вас есть бумага рядом, вы можете нарисовать большой прямоугольник, например 4 * 5 см - область, где расположены все точки. Теперь случайным образом расположите точки, и скажем, если есть точки, расстояние которых составляет 1 см - они должны быть сгруппированы в прямоугольник 2 * 3.
Я не могу найти алгоритм, как это сделать, и производительность тоже имеет значение ... Я искал вложения, кластеризацию, но мне нужно немного другое. И, кстати, если некоторые прямоугольники группировки должны быть вне общей области, чтобы соответствовать условиям, пусть это будет, это не проблема. Например. у вас есть область 4 * 5, а очки
(1,0), (2,1), (4,1), (4,3), (2,4)
тогда результат должен выглядеть как rectangles (0,0 - 3,2) & (3,1 - 6,3) and one point left (2,4), потому что все остальные точки были сгруппированы, и у этой точки сейчас нет соседей.
Координаты моих точек не целочисленные, а плавающие, и количество точек может быть несколько сотен (до 500). И я не хочу разбивать области на одни и те же прямоугольники и просто вычислять, сколько там точек, я имею в виду, например, выше, я мог бы сделать реактивные прямоугольники (0,0 - 3,2), (3,0 - 6,2) , (0,3–3,6), (3,3–6,6) и просто суммируйте баллы 2 для первого прямоугольника, 1 (!) Для второго, что означает оставить все как есть, 1 для третьего и 1 для 4-го => будет нарисован один прямоугольник, а все остальные точки => неверный результат в соответствии с заданием.
Есть идеи? По крайней мере, какие алгоритмы могут быть полезны, где искать ...
P.S. на данный момент количество групп / баллов в результате не имеет значения, т.е. другой допустимый результат для примера выше может быть (1,0-4,2) и (2,2-5,4) прямоугольников, и не осталось точек