Ближайшая точка на карте

Question

Я создаю программу, в которой вы можете нажать на карту, чтобы увидеть «крупный план» области вокруг нее, например на Картах Google.

Когда пользователь нажимает на карту, он получает координаты X и Y того места, где он щелкнул.

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

public static boolean[][] view_set=new boolean[Map.width][Map.height];
//The array of where pictures are.  The map has a width of 3313, and a height of 3329.

Программа выполняет поиск в папке, в которой изображения имеют имена, координаты X и Y которых были сняты на карте. Папка содержит следующие изображения (и не только, но я перечислю только пять):

2377,1881.jpg, 2384,1980.jpg, 2389,1923.jpg, 2425,1860.jpg, 2475,1900.jpg

Это означает, что:

view_set[2377][1881]=true;
view_set[2384][1980]=true;
view_set[2389][1923]=true;
view_set[2425][1860]=true;
view_set[2475][1900]=true;

Если пользователь нажимает на X и Y, например, 2377,1882, тогда мне нужно, чтобы программа выяснила, какое изображение ближе всего (ответ в этом случае будет 2377,1881).

Буду признателен за любую помощь, Спасибо.

Answer 1

Ваша boolean[][] не является хорошей структурой данных для этой проблемы, по крайней мере, если она не очень плотная (например, обычно точка с крупным планом доступна в окружающем квадрате 3 × 3 или, возможно, 5 × 5).

Вам нужна двумерная карта с поиском ближайшего соседа. Полезная структура данных для этой цели - QuadTree . Это дерево степени 4, используемое для представления пространственных данных. (Я описываю здесь "Region QuadTree с точечными данными".)

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

Таким образом, узел в вашем дереве является одним из них:

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

(В реализациях мы можем заменить пустые конечные узлы нулевым указателем в его родительском элементе.)

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

• Для добавления новой точки мы либо получим пустой узел - тогда мы можем поставить новую точку здесь. Если мы окажемся в узле, в котором уже есть точка, создадим четыре дочерних узла (разделив прямоугольник) и добавим обе точки в соответствующий дочерний узел. (Это может быть то же самое, затем повторите рекурсивно.)

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

• Для удаления, после нахождения точки, мы делаем ее узел пустым. Если родительский узел теперь содержит только одну точку, мы заменим его листовым узлом с одной точкой.

Поиск и добавление / удаление выполняются в O (глубина) сложности времени, где максимальная глубина ограничена log ((длина карты + ширина) / минимальное расстояние двух точек в вашей структуре) , и средняя глубина зависит от распределения точек (например, среднего расстояния до следующей точки), более или менее.

Необходимое пространство зависит от количества точек и средней глубины дерева.

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

Answer 2

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

Псевдокод:

int size = 0
Point result = default
while(result == default)
   result = searchRectangleBoundary(size++, pointClicked)

function Point searchRectangleBoundary(int size, Point centre)
{
    point p = {centre.X - size, centre.Y - size}
    for i in 0 to and including size
    {
        if(view_set[p.X + i][p.Y]) return { p.X + i, p.Y}
        if(view_set[p.X][p.Y + i]) return { p.X, p.Y + i}
        if(view_set[p.X + i][p.Y + size]) return { p.X + i, p.Y + size}
        if(view_set[p.X + size][p.Y + i]) return { p.X + size, p.Y + i}
    }
    return default
}

Обратите внимание, что я упустил проверку диапазона для краткости.

Тамэто небольшая проблема, но в зависимости от приложения это может не быть проблемой.Здесь не евклидовы расстояния, а манхэттенская метрика.Таким образом, он не обязательно находит самое близкое изображение, но изображение, самое большее квадратного корня в 2 раза больше.

Answer 3

На основании

• вашего комментария о том, что у вас есть 350-500 точек интереса,
• вашего вопроса о том, что у вас ширина карты 3313 и высота 3329
  • мой калькулятор, который сообщает мне, что он представляет ~ 11 миллионов логических значений

... вы делаете это неправильно.@ JBSnorro - довольно элегантный способ найти иголку (350 баллов) в стоге сена (11 миллионов баллов), но на самом деле, зачем вообще создавать стог сена?

Согласно моему комментарию на ваш вопроспочему бы просто не использовать класс Pair<Integer,Integer> для представления координат, сохранять их в наборе и сканировать их?Это проще, быстрее, меньше потребляет памяти и является способ более масштабируемым для больших карт (при условии, что интересные места редки ... что кажется разумным предположением, учитывая, что они представляют интерес).

.. поверьте мне, вычисление евклидова расстояния ~ 425 раз превосходит блуждание вокруг значения 11 миллионов boolean[][] в поисках интересующего 1 значения в 25 950 (особенно в анализе наихудшего случая).

---

Если вы действительно не в восторге от идеи сканировать ~ 425 значений каждый раз, то (i) вы больше ОКР, чем я (:P);(ii) вам следует проверить алгоритмы поиска ближайших соседей .

Answer 4

Я не знаю, если вы просите об этом.Если пользовательская точка P1 {x1, y1} и вы хотите вычислить ее расстояние до P2 {x2, y2}, расстояние вычисляется с помощью Pythagoras'Theorem

distance^2 = (x2-x1)^2 + (y2-y1)^2

Если вы хотите знатьближе всего, вы можете избежать вычисления квадратного корня (чем меньше расстояние, тем меньше квадрат, чтобы он служил вам одинаково).