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

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

Псевдокод:

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 раза дальше квадратного корня.

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

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

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

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

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

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

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

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

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

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

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

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

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

На основе

• ваш комментарий, в котором говорится, что у вас есть 350-500 точек интереса,
• your question that states you have a map width of 3313, and a height of 3329
  • my calculator which tells me that that represents ~11 million boolean values

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

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

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

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

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

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

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