Лучшая фиксированная прямоугольная область, подходящая по точкам

Question

Я использую Карты Google и пытаюсь определить максимальное количество точек, видимых в области просмотра при заданном уровне масштабирования.

Мой наивный подход состоит в том, чтобы получить область просмотра (в координатах) и использовать ее в качестве «подходящего прямоугольника» и посмотреть, сколько точек вписывается в область. Я осмотрелся вокруг, но не смог найти никакого алгоритма для «наилучшего соответствия» случайных точек в прямоугольной области.

Кажется, это довольно распространенная проблема, поэтому я, вероятно, не знаю, какие ключевые слова использовать.

Буду признателен за любую помощь в поиске решения.

РЕДАКТИРОВАТЬ: спасибо за ответы, но я боюсь, что я не прояснил себя. Установка прямоугольника над ВСЕМИ точками - тривиальное дело (сортируйте их все, получайте мин / макс и вуаля).
То, что я хочу знать, - это максимальное количество точек, которые можно уместить под прямоугольником с ФИКСИРОВАННЫМ РАЗМЕРОМ: у меня есть все мои точки и «движущееся окно» фиксированного размера, и я хочу знать, сколько точек я могу уместить.
Извините за плохое начальное объяснение.

Приветствие.

Answer 1

Чтобы найти наиболее подходящий прямоугольник для набора точек, и при условии, что все точки в наборе должны быть внутри прямоугольника, все, что вам нужно сделать, это найти минимальное / максимальное значения в обоих измерениях.

Один из способов сделать это - отсортировать точки по их измерению X и взять первое и последнее в качестве минимального / максимального значения в этом измерении, а затем повторить процесс в измерении Y, чтобы получить это минимальное / максимальное значение.Исходя из этой информации, у вас есть все, что нужно для создания прямоугольника.

С точки зрения сложности вычислений сложность в 2 раза превышает сложность используемого алгоритма сортировки (поскольку вам нужно сортировать 2 раза) + сложностьполучение первого и последнего элементов каждого отсортированного набора, что, например, если вы используете массив, является операцией O (1).

Если вы используете сортировку слиянием и сортировку по массивам, у вас естьобщая сложность O (n log n).Если разбить на количество операций, у вас есть 2 (n log n) + 4.

Это не даст вам максимально плотного прилегания к набору прямоугольников, потому что это не гарантирует, что одна сторона прямоугольника коллинеарнапо крайней мере с 2 точками (для этого вам понадобится алгоритм вращающихся штангенциркулей, который предлагает @Bart Kiers), но это гораздо более быстрый алгоритм, поскольку вращающиеся штангенциркули по существу такие же, как я описал здесь, но затем поворачивает прямоугольникпока один из его ребер не выровняется с двумя из точек min / max.