Поиск по координатам HashMap

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

cities.put(new Coordinates(X, Y), "City Name");

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

У меня нет проблем с получением координат щелчка мыши. Однако моя проблема заключается в том, что я не знаю, как искать через HashMap и получить ближайший город. Ни один человек не сможет отлично нажать на конкретный X и конкретную координату Y. Поэтому я должен разрешить, например, + - 15.

источник

2014-11-11 Sameer

У вас есть города, обозначенные кружком радиуса 15 в положении x, y. Я предполагаю, что существует предположение, что круги не пересекаются, иначе есть другое правило для определения уникальности. Затем ваш вопрос становится «находится ли этот пункт в этом круге», на который ранее был дан ответ (http://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle). Вероятно, есть стратегии, которые можно было бы использовать для определения потенциальных кандидатов, но я ожидаю, что они будут зависеть от ваших данных и от того, как они распределяются. – Romski

Вы можете обнаружить, что ни один из встроенных типов не подходит для вашего запроса. Я подозреваю, что один из [пространственных деревьев] (http://en.wikipedia.org/wiki/Template:CS_trees) может быть лучшим инструментом, хотя я недостаточно знаком с этой областью структур данных, чтобы сказать «да , это тот "и дать окончательный ответ. –

Существует отличная статья о vp-деревьях с образцом кода (в C++ хотя) [здесь] (http://stevehanov.ca/blog/index.php?id=130), который выглядит точно так, как будто это ваш поиск. – Oncaphillis

Разделите свою карту на сетку таким образом, чтобы левые координаты любого квадрата сетки можно было вычислить из точки в сетке.

Например, если карта было 100 х 100, и вы хотели, чтобы содержать 10 сетку квадратов 10 квадратов сетки, верхние левые координаты для любого квадрата сетки будет:

top = y - y%10; 
left = x - x%10;

Тогда ваш карта будет:

Map<Coordinates, City>

где City является объект, содержащий имя и реальные координаты города (не сетка координат).

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

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

EDIT: Это также можно решить, выполнив некоторые обманки с помощью hashcode и .equals() метода класса Coordinates, используя аналогичный принцип математики сетки.

источник

2014-11-11 02:11:44 Jason

Это будет работать, только если города отлично ортогональны сетке ('/ 10'). Но если бы это было так, представляя их как точки в континууме, было бы глупо - просто храните плитки в виде 2D-массива, где каждая плитка может содержать город. Предположительно, OP использует более мелкое координатное пространство, потому что города могут неоднозначно выстраиваться в более грубом пространстве, где вы уменьшаете разрешение сетки. –

Нет, они не обязательно должны идеально совмещаться с сеткой. Оператор «%» гарантирует, что везде, где на квадрате сетки они появляются, можно вычислить правильные координаты сетки. Конечно, если более одного города могут быть на одном и том же квадрате сетки, карта должна содержать списки городов. – Jason

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

ответ

Смежные вопросы