Создание реальной карты с помощью HashMap в Java

Question

Мне нравится создавать настоящую карту, где я могу найти автозаправочные станции в своем районе.

Я начал с создания HashMap:

ключ => Координаты

значение => Hotel

HashMap<Coordinates, Hotel> m = HashMap<Coordinates, Hotel>(); 

Это являются классы:

public class Coordinates { 

    private double lng; 
    private double lat; 

    public Coordinates(double x, double y) { 
     lat = x; 
     lng = y; 
    } 

    public double getLng() { 
     return lng; 
    } 

    public double getLat() { 
     return lat; 
    } 

    public void setLat(double l) { 
     lat = l; 
    } 

    public void setLng(double l) { 
     lng = l; 
    } 

    public boolean equals(Coordinates other) { 
     return ((lng == other.getLng()) && (lat == other.getLat())); 
    } 

    public int hashCode() { 
     int lng2 = (int) (this.lng * 100000); 
     int lat2 = (int) (this.lat * 100000); 
     //Use a prime number for security 
     return 31 * (lng2 + lat2); 
    } 

} 

public class Hotels { 

    public class Info { 
     public String text; 

     public Info(String t) { 
      text = t; 
     } 
    } 

    private Coordinates coords; 
    private Info description; 

    public Hotel(double lat, double lng, String text) { 
     this.coords = new Coordinates(lat, lng); 
     this.description = new Info(text); 
    } 

    public Coordinates getCoords() { 
     return coords; 
    } 

    public Info getInfo() { 
     return description; 
    } 

    public String getDescription() { 
     return description.text; 
    } 
} 

Задача что я предложил себе (не домашнее задание) создать функцию, которая при вызове нс все отели в радиусе, что вы заявили:

public Iterable<Hotel> search(double lat, double lng, double radius) { 
    //Code Here 
} 

Очевидно, что если я хочу использовать HashMap, я НЕ хочу, чтобы перебирать все отели. Я хочу иметь лучшую сложность в функции.

EDIT: Это карта XD

http://i.stack.imgur.com/7vF5Q.jpg

Answer 1

HashMap лучше неправильная структура данных для этого. Карты обеспечивают быстрый доступ к элементам по ключу; вы хотите собрать список предметов на основе критериев, и вы хотите, чтобы сбор был эффективным. Я предлагаю вам хранить список гостиниц по каждой координате; т.е. один список имеет гостиницы по порядку по долготе, по широте. Затем, когда вы хотите установить радиус в радиусе, вы можете начать с получения всех тех, что находятся внутри квадрата, который охватывает круг, определенный по радиусу.

Answer 2

Коллекции карт специально разработаны, чтобы вы могли получить значение для заданного ключа. Они не хорошо разработаны для поиска ключей для значений (вот что вы хотите сделать здесь).

Если ваша цель заключается в повышении эффективности поиска, то вы действительно ищете способ найти подмножество отелей для фильтрации радиуса. Я предлагаю вам подходить к нему, внедряя отдельный класс Region, который по существу является всеми координатами в некотором диапазоне. Затем вы можете перейти от региона к списку отелей, который будет искать по расстоянию. Обратите внимание, что вам также нужно будет учитывать окружающие регионы, так как ваша цель может находиться на краю одного из них.

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

Map<Region, List<Hotel>> regionMap; 

public List<Hotel> findAllHotelsWithinRadiusOfLocation(Coordinates coords, double distance) { 
    return coords.streamRegionsWithin(distance) 
     .flatMap(region -> regionMap.get(region).stream()) 
     .filter(hotel -> hotel.distanceTo(coords) <= distance) 
     .collect(Collectors.toList()); 
} 

Размер областей является компромиссом: больше будет означать меньшую карту, но больше отелей фильтр для расстояния.

Пожалуйста, задавайте вопросы, если это не имеет смысла.

Answer 3

Как уже отмечалось, хешмап не является подходящей структурой данных для этого.

Рассмотрите пространственные структуры данных, такие как k-d tree или quadtrees. Они предназначены для обработки запросов по радиусу, которые вы описываете очень эффективно. По существу они рекурсивно разбивают пространство поиска, а затем используют двоичный поиск для поиска результатов запроса.

Ссылки

• к-г дерева реализаций: http://robowiki.net/wiki/Kd-tree
• Другие пространственные индексации данных подходы: http://en.wikipedia.org/wiki/Spatial_database#Spatial_index)