Я ищу какой-то подход (алгоритм должен быть очень конкретным) здесь.
Проблема: Есть N прямоугольников ( r1, r2, .. rn ) разбросаны в плоскости XY.Необходимо найти оптимальное решение для кластеризации этих прямоугольников с помощью более ограниченных многоугольников.
Условие кластеризации:
- В результатах должно быть указано максимальное количество прямоугольников, охватываемых многоугольником.
- Общее количество ограниченного многоугольника должно быть минимально возможным и максимальным K .
- Каждый ограниченный многоугольник должен иметь не менее 70% площади, заполненной данными прямоугольниками.
- Все прямоугольники должны бытьне быть ограниченным.
ограничение:
- 1 миллион <= n <= миллиарды </li>
- K = 50000
Проблему можно представить как идентификацию островов (максимум 50 тыс. Островов) с более высокой плотностью прямоугольников (70% на каждом острове).Мы можем, конечно, исключить определенные прямоугольники.Но идея состоит в том, чтобы найти оптимальное решение, и единственного лучшего решения не существует.
Я пытался использовать кластеризацию K-средних, но в моем случае это не подходит, так как в моем решении проблемы может лежать в пределах 1-Значения K вместо значений KМожет быть, это требует все вместе другого измерения мышления.Надеюсь, я ясен !!
Добавление изображения, чтобы быть более ясным: 